Розв’язання нелінійних оптимізаційних задач розподілу ресурсів у великих блочно-структурованих системах зі зв’язуючими параметрами

Solving non-linear optimization problems with a block structure and binding parameters (variables) is realized by a combination of the approximation and decomposition approaches. The approximation method is chosen so that the decomposition of the mathematical programming problem can be performed wit...

Full description

Saved in:

Bibliographic Details
Date:	2016
Main Author:	Kirik, Olena E.
Format:	Article
Language:	Ukrainian
Published:	The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2016
Subjects:	задачі розподілу ресурсів оптимізаційні моделі апроксимуючі методи нелінійне програмування алгоритми декомпозиції
Online Access:	https://journal.iasa.kpi.ua/article/view/85428
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	System research and information technologies
Download file:

Institution

System research and information technologies

_version_	1866301829909839872
author	Kirik, Olena E.
author_facet	Kirik, Olena E.
author_sort	Kirik, Olena E.
baseUrl_str	http://journal.iasa.kpi.ua/oai
collection	OJS
datestamp_date	2018-03-30T15:27:13Z
description	Solving non-linear optimization problems with a block structure and binding parameters (variables) is realized by a combination of the approximation and decomposition approaches. The approximation method is chosen so that the decomposition of the mathematical programming problem can be performed without making any assumptions about the convexity or additive separability of objective functions and constraints. The coordinating and block sub-problems that are auxiliary in the approximation method, are solved using a finite number of steps. In the course of calculation, binding variables vary from step to step of the iterative process, providing a monotonic decrease of the value of the coordinating problem objective function; in other words, the amount of shared resources is changed in such a way that block subsystems operate more and more efficiently in terms of the efficiency of the whole system.
doi_str_mv	10.20535/SRIT.2308-8893.2016.3.07
first_indexed	2025-07-17T10:20:54Z
format	Article
fulltext	 О.Є. Кірік, 2016 72 ISSN 1681–6048 System Research & Information Technologies, 2016, № 3 TIДC МЕТОДИ ОПТИМІЗАЦІЇ, ОПТИМАЛЬНЕ УПРАВЛІННЯ І ТЕОРІЯ ІГОР УДК 519.8 DOI: 10.20535/SRIT.2308-8893.2016.3.07 РОЗВ’ЯЗАННЯ НЕЛІНІЙНИХ ОПТИМІЗАЦІЙНИХ ЗАДАЧ РОЗПОДІЛУ РЕСУРСІВ У ВЕЛИКИХ БЛОЧНО- СТРУКТУРОВАНИХ СИСТЕМАХ ЗІ ЗВ’ЯЗУЮЧИМИ ПАРАМЕТРАМИ О.Є. КІРІК Анотація. Розв’язання нелінійних оптимізаційних задач блочної структури зі зв’язуючими параметрами (змінними) реалізується шляхом комбінації апрок- симаційного та декомпозиційного підходів. Апроксимаційний метод обрано таким чином, щоб декомпозицію задачі математичного програмування можна виконувати без будь-яких припущень щодо опуклості або адитивної сепара- бельності функцій критерію та обмежень. Координуюча та блочні підзадачі, що є допоміжними в апроксимаційному методі, розв’язуються за скінченну кі- лькість кроків. У ході обчислень зв’язуючі параметри змінюються від кроку до кроку ітераційного процесу, забезпечуючи монотонне зменшення значення ці- льової функції координуючої задачі, тобто кількість загальних ресурсів зміню- ється таким чином, аби блочні підсистеми працювали дедалі ефективніше з точки зору ефективності роботи всієї системи. Ключові слова: задачі розподілу ресурсів, оптимізаційні моделі, апрокси- муючі методи, нелінійне програмування, алгоритми декомпозиції. ВСТУП До нелінійних оптимізаційних задач блочної структури зі зв’язуючими змінними зводиться численна кількість практичних проблем планування та управління. У задачах управління виробництвом та запасами блочні струк- тури виникають, коли основну частину технологічних параметрів можна подати у вигляді підмножин, що не перетинаються, а показники інтенсивно- сті використання решти параметрів є зв’язуючими змінними. До блочних задач зводяться також різні динамічні моделі управління виробництвом. За- галом, якщо складна система містить декілька підсистем, функціонування яких описується індивідуальними наборами змінних, але можливості діяль- ності кожної підсистеми залежать до того ж від деяких загальносистемних параметрів або напрямів, то виникають задачі блочної структури зі зв’язуючими змінними. Ефективним підходом до розв’язання оптимізаційних блочних задач є використання прийомів декомпозиції, тобто застосування оптимізаційних Розв’язання нелінійних оптимізаційних задач розподілу ресурсів у великих … Системні дослідження та інформаційні технології, 2016, № 3 73 методів до спеціальним чином побудованої координуючої задачі та набору підзадач для окремих блоків [1, 2]. При цьому істотною умовою є опуклість та адитивна сепарабельність функцій, що визначають критерій та обмежен- ня, а складові цільової функції координуючої задачі у загальному випадку визначені на обмежених множинах і іноді потребують певних процедур регуляризації вихідної задачі [3]. Процедури розв’язання координуючих за- дач на основі різних методів оптимізації та властивості функцій координую- чих задач досліджувалися у багатьох працях, зокрема [4–6] У праці [7] запропоновано підхід до розв’язання задач блочної структу- ри зі зв’язуючими обмеженнями у вигляді триступеневої ітераційної схеми, де на верхньому рівні вихідна задача змінюється послідовністю апроксиму- ючих задач з адитивно-сепарабельними цільовими функціями та лінійними обмеженнями, а на другому рівні розв’язуються координуючі задачі, які фор- муються за рахунок інформації, отриманої на найнижчому рівні під час розв’язання блочних підзадач. Аналогічну схему можна запропонувати і для нелінійних задач зі зв’язуючими змінними. Але на відміну від задач зі зв’язуючими обмежен- нями в цьому випадку потрібно застосовувати прямий, а не двоїстий метод декомпозиції. Мета роботи — побудова та аналіз методу розв’язання нелінійних за- дач блочної структури зі зв’язуючими змінними із застосуванням комбінації апроксимуючого методу нелінійної оптимізації та прямої схеми декомпозиції. Оскільки декомпозиції в цьому випадку підлягають спеціальним чином побудовані задачі, які мають потрібні для розбиття властивості, то немає необхідності ставити вимоги сепарабельності до вихідної задачі. Це розши- рює класи задач, що можуть бути розв’язані із застосуванням спеціальних прийомів. АПРОКСИМУЮЧІ МЕТОДИ УМОВНОЇ ОПТИМІЗАЦІЇ Як показано у працях [7, 8], зручним способом замінити нелінійну задачу задачею квадратичного програмування з адитивно-сепарабельними цільо- вими функціями є застосування методу лінеаризації Б.М. Пшеничного [9]. Основна ідея цього методу полягає у заміні нелінійної задачі послідовністю лінеаризованих задач, доповнених квадратичним штрафом за великі відхи- лення аргумента. Метод лінеаризації є методом першого порядку. Але його ефективність може бути підвищена застосуванням деяких спеціальних при- йомів [10], а для певних класів задач, зокрема, нелінійних задач з лінійними обмеженнями, вдається досягти швидкості збіжності, зіставної зі швидкістю методів послідовного квадратичного програмування. Нехай маємо нелінійну задачу гладкої умовної оптимізації },...,1,0)(:{),(min 0 Mx mixfRxMxf i n   . (1) Якщо є обмеження-рівності, то заміняємо їх еквівалентною парою від- повідних нерівностей. Загальну схему апроксимуючих методів умовної оптимізації можна по- дати у вигляді ітераційного процесу ,...,1,0,1  kpхх k k k k (2) О.Є. Кірік ISSN 1681–6048 System Research & Information Technologies, 2016, № 3 74 де 0k , а )( kk xpp  , nk Rp  — розв’язок допоміжної апроксимуючої задачі з лінійними обмеженнями:        mipxfxfppDpxfxf k i k ik kk p ,...,1,),()(:, 2 1 ),()(min 00 . (3) Для визначення крокового множника k у всіх методах можна викори- стовувати релаксацію вздовж вектора спуску kp недиференційованої штрафної функції ,0),()(),( 0  xFxfxf де })(,),(,0{max)( 1 xfxfxF m . У методі лінеаризації Б.М. Пшеничного EDk  — це одинична nn -матриця; квадратичний доданок у цільовій функції апроксимуючої задачі відіграє роль штрафної функції, а k обчислюється як найбільше зі значень ,1,0,2   tt , за якого виконується нерівність 2 ),(),( kkkk pxfpxf  ,  1,0 . (4) Коефіцієнт штрафу 0 мажорує множники Лагранжа k задачі (3): ,1,0, 1    k m i k i , (5) причому виконання умови (5) гарантує, що нерівність (4) виконується після скінченної кількості ділень одиниці навпіл. Під час формування апроксимуючої задачі до неї можна включати ли- ше найбільш істотні обмеження, причому правила зменшення кількості об- межень викладено у праці [9]. БЛОЧНІ ЗАДАЧІ ЗІ ЗВ’ЯЗУЮЧИМИ ЗМІННИМИ Якщо вихідна задача (1) має вигляд блочної зі зв’язуючими змінними, то апроксимуючу задачу (3) з Q блоками у матричному вигляді можна сфор- мулюватити таким чином: ,min)()( 1 1     Q i ii pFpF 01   iQiii bpBpA , Qi ,...,2,1 , (6) де 2 2 1 ,)( iiiii ppcpF  , in i Rc  , in i Rp  , im i Rb  ; iA і iB — матриці розмірностей відповідно )( ii nm  і )( 1 Qi nm ; 1 1  Qn Q Rp — вектор зв’язуючих змінних; nn Q i i    1 1 , mm Q i i  1 . Розв’язання нелінійних оптимізаційних задач розподілу ресурсів у великих … Системні дослідження та інформаційні технології, 2016, № 3 75 Беремо до уваги, що апроксимуюча задача (6) змінюється від кроку до кроку процесу (2), але випускаємо індекси, що є номерами кроку k , аби не обтяжувати формули додатковими позначеннями. Основна ідея методу розділення змінних [1], що застосовується для розв’язання задач зі зв’язуючими змінними, полягає у тому, що фіксуються зв’язуючі змінні 1Qp і розв’язується задача стосовно решти змінних, яка внаслідок блочної структури розпадається на незалежні підзадачі меншого розміру, причому екстремуми цільових функцій цих підзадач залежать від фіксованих змінних як від параметрів. Підставляючи їх у неявному вигляді у вихідну задачу, отримують координуючу задачу, що залежить лише від фіксованих змінних. Загалом лише для обмежених класів функцій можна отримати явний вигляд координуючої задачі. Нехай точка 1Qp є допустимою, тобто },...,2,1,0:{ 111 QibpBpApp iQiiiQQ   . За фіксованого 11   QQ pp задача (6) розпадається на Q задач )(min ii pF , 01   iQiii bpBpA , Qi ,...,2,1 . (7) Це означає, що задачу (6) можна замінити знаходженням мінімуму функції )()()( 11 1 11      QQ Q i QiQ pFpp , (8) де }0:)({min)( 11   iQiiiii p Qi bpBpApFp i , Qi ,...,2,1 , (9) на множині допустимих точок 1Qp . Функції (9) є неявними і в загальному випадку їх оцінка в деякій точці 1Qp потребує розв’язання задач (7). Однак ці задачі меншої розмірності, ніж вихідна задача (6) , і розв’язуються неза- лежно, що може виявитися зручним для розрахунків. У схемах декомпозиції задача )(min 1 Qp , (10) що є еквівалентною вихідній, називається координуючою задачею. Задачі (7) будемо називати блочними підзадачами. Нехай }0:{)( 11   iQiiiiQi bpBpAppM , Qi ,...,2,1 — допус- тимі області задач (7). Якщо розглядати iM як опуклі багатогранні багато- значні відображення, то з блочних підзадач можна отримати інформацію щодо субградієнтів функції (8). Оскільки цільові функції задач (7) є опукли- ми і власними, то )( 1 Qi p є опуклими функціями і, використовуючи тео- рему про обчислення субдиференціала через відображення, локально спря- жене до багатозначного [11], отримуємо О.Є. Кірік ISSN 1681–6048 System Research & Information Technologies, 2016, № 3 76 }0)(,0,0:{)( 11      iiQiiiiiiiiiiQi ubpBpAuuApcuBp , Qi ,...,2,1 . Тут iu — вектор множників Лагранжа i -ї блочної підзадачі. Оскільки є можливість оцінити значення i та їх субградієнтів, то для розв’язання задачі (10) можна обрати який-небудь метод опуклого програ- мування. Але для отримання алгоритму, що збігається за скінченну кількість кроків, потрібно гарантувати виконання деяких додаткових умов. Нехай за деякого фіксованого 11   QQ pp задачі (7) розв’язані та знай- дені оптимальні значення )( 1Qi pp . Позначимо через )( 1 Qii pJJ мно- жину номерів активних обмежень i - ї задачі (7) у точці 1Qp , тобто тих об- межень, які в цій точці виконуються як рівності: 0)( 11   iii JQJQiJ bpBppA , Qi ,...,2,1 . Тут через iJA , iJB позначено матриці, що складаються з рядків, номери яких входять у множини iJ . Їм відповідають складові векторів iJb та iJu вільних членів і множників Лагранжа відповідних задач. Надалі будемо використовувати такі означення. Точка 1Qp називається регулярною, якщо виконуються такі умови: всі блочні підзадачі (7) за фіксованого 11   QQ pp є розв’язними, рядки мат- риць iJA — лінійно незалежними; множники Лагранжа, що відповідають активним обмеженням, — строго додатними 0 iJu . У разі невеликого відхилення 1Qp від 1Qp набори активних обме- жень та знаки множників Лагранжа блочних підзадач можуть залишитися незмінними. Підмножина множини змін 1Qp , що складається з регулярних точок, яким відповідає одна й та сама матриця активних обмежень iJA зі строго додатними множниками Лагранжа iJu , називається регулярною областю для функції )( 1 Qi p . Теорема 1. У кожній регулярній області функції )( 1 Qi p є квадра- тичними. Доведення. У регулярній точці 1Qp множники Лагранжа визначають- ся однозначно і )( 1 Qi p складається з єдиного вектора градієнта функції )()( 11     QiiQi puBp . Необхідні умови екстремуму для i -ї блочної підзадачі (7) у цій точці виконуються у такій формі: 0  ii JJii uApc , 01   iii JQJiJ bpBpA , 0 iJu . Розв’язання нелінійних оптимізаційних задач розподілу ресурсів у великих … Системні дослідження та інформаційні технології, 2016, № 3 77 Звідси ii JJii uAcp  , (11) )()( 1 1 iiiiii JQJiJJJJ bpBcAAAu    . (12) Формула (12) виведена за припущення, що iJA є матрицею активних обмежень блочної підзадачі, тому для тих 1Qp , для яких ця умова викону- ється, градієнт функції i є лінійною функцією від 1Qp : )()()()( 1 1 1 1 iJJJJJQJJJJiJQi cAbAABpBAABuBp iiiiiiiiii      . Сама ж функція i у цій регулярній області є квадратичною:     11 1 1 ,)( 2 1 )( QQJJJJQi ppBAABp iiii iiiiii JQiJJJJJ bpcAbAAB    1 1 ),()( , де iJb — це деяка константа, яку можна знайти з означення функції i (формула (9)):   iJJJJiJJJJJ cbAAAcAAAAEb iiiiiiiii ,)(])([ 2 1 121 21)( 2 1 iiii JJJJ bAAA  . Теорему доведено. Кожна регулярна область для )( 1 Qp є перетином регулярних об- ластей функцій )( 1 Qi p , Qi ,...,2,1 . Тому неперервна функція )( 1 Qp складається із фрагментів квадратичних функцій, причому в місцях з’єднання цих функцій можливі розриви її похідних. Через можливий роз- рив градієнта скінченнокрокові градієнтні методи для мінімізації )( 1 Qp не можуть бути застосовані. Оскільки задача (6) є допоміжною в апрокси- муючому методі, то бажано отримати її розв’язок за скінченну кількість кроків. Тому замість мінімізації неявної функції )( 1 Qp будемо проводити послідовну мінімізацію спеціальним чином побудованих квадратичних функцій. МЕТОД РОЗВ’ЯЗАННЯ ТА КРИТЕРІЙ ОПТИМАЛЬНОСТІ Якщо є багатогранна множина, що описується системою нерівностей, то гранню цієї множини називається підмножина, яка описується набором з обмежень, що задовольняються як рівності. Нехай },,...,,{ 121  QQ ppppp — довільна точка, що належить мно- жині означень задачі (6), тобто 01   iQiii bpBpA , Qi ,...,2,1 . Якщо О.Є. Кірік ISSN 1681–6048 System Research & Information Technologies, 2016, № 3 78 )( pJJ ii  — множина номерів обмежень i - ї задачі (7), що в точці p задо- вольняються як рівності, то цю систему рівностей можна записати у вигляді 01   iii JQJiJ bpBpA , Qi ,...,2,1 . (13) Надалі припускаємо, що виконується така умова невиродженості і для наборів індексів )( pJJ ii  , що породжуються довільною допустимою точ- кою p , вектори, які є рядками матриці активних обмежень iJA , є лінійно незалежними. Випишемо задачу мінімізації функції )( pF на грані (13) допустимої множини задачі (6) )(min pF , 01   iii JQJiJ bpBpA , Qi ,...,2,1 . (14) Зафіксуємо 11   QQ pp . При цьому задача (14) розпадеться на Q задач )(min ii pF , 01   iii JQJiJ bpBpA , Qi ,...,2,1 . (15) Позначимо: }0:)({min)( 11   iQiiiii p QJ bpBpApFp i i , Qi ,...,2,1 . Визначимо розв’язок задач (15) у явному вигляді, використовуючи не- обхідні умови екстремуму )()())(( 1 11 iiiiiiiii JQJJJJiJJJJi bpBAAAcAAAAEp    , (16) Qi ,...,2,1 ,     11 1 1 ,)( 2 1 )( QQJJJJQJ ppBAABp iiiii (17) iiiiii JQiJJJJJ bpcAbAAB    1 1 ),()( , Qi ,...,2,1 . Задачу мінімізації функції )()()( 11 1 11      QQ Q i QJQJ pFpp i (18) назвемо локальною координуючою задачею, а операцію обчислення ip за формулами (16) — допоміжною операцією. Розв’язання задач (14) мінімізації цільової функції на грані еквівалент- но розв’язанню відповідної локальної координуючої задачі з подальшим ви- конанням допоміжної операції. Опишемо ідею заміни координуючої задачі набором локальних коор- динуючих задач. Обираємо довільну допустиму точку 1Qp . За фіксованого 11   QQ pp розв’язуємо блочні підзадачі (7). Виділяємо серед обмежень Розв’язання нелінійних оптимізаційних задач розподілу ресурсів у великих … Системні дослідження та інформаційні технології, 2016, № 3 79 цих задач ті, що в оптимальних точках )( 1Qi pp задовольняються як рівно- сті. Активні обмеження визначають певну грань багатогранної множини, що описується обмеженнями задачі (6). Будуємо локальну координуючу за- дачу, що відповідає мінімізації цільової функції задачі (6) на цій грані. Розв’язуємо цю задачу методом спряжених градієнтів [9]. Якщо до кожної з отриманих у процесі розв’язання точок застосувати допоміжноу операцію (16), отримаємо послідовність точок },,...,,{ 121  QQ ppppp , що належить виділеній. грані. На кожному кроці виконується перевірка для контролю ви- ходу на грань допустимої множини, аби не допустити виходу за межі допус- тимої області. Якщо в деякий точці вздовж обраного напрямку одне з неак- тивних обмежень перетворюється в нуль, то додаємо його до активного набору і будуємо нову допоміжну координуючу задачу для розширеного активного набору, після чого продовжуємо застосовувати метод спряжених градієнтів. Метод спряжених градієнтів мінімізує конкретну квадратичну функцію за скінченну кількість ітерацій. Оскільки кількість граней є також скінчен- ною, то після скінченної кількості кроків отримаємо точку мінімуму лока- льної координуючої задачі. Координуюча задача (10) є еквівалентною вихідній задачі (6), а кожна локальнана координуюча задача — еквівалентною задачі типу (14), що за умови збереження допустимості 1Qp має більш вузьку порівняно із зада- чею (6) допустиму область. Тому точка мінімуму локальної координуючої задачі може не бути розв’язком координуючої задачі (10). Тоді, вважаючи отриману точку початковою, треба повторити процедуру спочатку, почина- ючи з розв’язку блочних підзадач. Теорема 2. Необхідні та достатні умови того, що точка 1Qp є розв’язком координуючої задачі (10), полягають у тому, що ця точка є розв’язком локальної координуючої задачі )(min 1 QJ p і виконано умови 0 iJu , Qi ,...,2,1 . (19) Доведення. Відповідно до принципів побудови координуючої та ло- кальних координуючих задач умови (19) гарантують збіжність цільових функцій цих задач у точці 1Qp . У процесі пошуку оптимальної точки багаторазово розв’язуються бло- чні підзадачі (7). Якщо розв’язувати задачі двоїсті до блочних, то можемо застосувати метод спряжених градієнтів для задач з простими обмеженнями, а змінні ip знаходити за формулами (11). Алгоритм розв’язання координуючої задачі 1. Обираємо за початкове наближення довільну допустиму точку 1Qp . 2. Розв’язуємо задачі двоїсті до блочних підзадач (7)          iiQiiiiiii ubpBcAuuAA ,, 2 1 max 1 , 0iu , Qi ,...,2,1 . О.Є. Кірік ISSN 1681–6048 System Research & Information Technologies, 2016, № 3 80 3. Знаючи множники Лагранжа iu , обчислюємо iiiQi uAcpp   )( 1 і знаходимо множини індексів активних обмежень )( 1Qi pJ , Qi ,...,2,1 . 4. Використовуючи формули (17), (18), будуємо та розв’язуємо локальну координуючу задачу )(min 1 QJ p методом спряжених градієнтів. На кожному кроці виконуємо перевірку для збереження допустимості розв’язку. Для цього підставляємо вираз 11 11    k k kk spp QQ , де k Q p 1 — чергова отримана точка; 1ks — напрямок зсуву за методом спряжених градієнтів на кроці k у ті обмеження блочних підзадач, індекси яких не входять до множин активних обмежень. Знаходи- мо найменше зі значень k , за якого неактивні обмеження дорівнюються до нуля. Порівнюємо це значення з довжиною кроку спряжених градієнтів k . Якщо kk  , то 11 11    k k kk spp QQ і процес розв’язання локальної коор- динуючої задачі потрібно продовжувати. Якщо ж ця нерівність не викону- ється, то 11 11    k k kk spp QQ і процес застосування методу спряжених гра- дієнтів до цієї локальної координуючої задачі є закінченим. В останньому випадку розширюємо множину iJ , додаючи до неї номер того обмеження, на якому дотягнуто мінімальне значення k . Повторюємо крок 4. Нехай в результаті мінімізації отримано оптимальну точку локальної координуючої задачі 1Qp . Обчислюємо )()( 1 1 iiiiii JQJiJJJJ bpBcAAAu    , Qi ,...,2,1 . Якщо всі 0 iJu , то точка 1Qp є розв’язком координуючої задачі (10), а },,...,,{ 121  QQ ppppp , де ii JJii uAcp  ( Qi ,...,2,1 ), є розв’язком вихідної задачі. Якщо ж умова 0 iJu , Qi ,...,2,1 не виконується , то повертаємося до кроку 2 алгоритму , вважаючи точку 1Qp новим наближенням і визначаючи нову множину номерів активних обмежень )( 1 QpJJ , що отримується за результатом розв’язання блочних підзадач за фіксованого 11   QQ pp . Обґрунтування збіжності Нехай iJ , Qi ,...,2,1 — вихідні множини індексів активних обмежень і в процесі розв’язання локальної координуючої задачі з цільовою функцією )( 1 QJ p ітераційний процес привів у таку точку 1 ~ Qp , у якій одне з обме- жень, що не входило раніше до множини активних 01   iii JQJiJ bpBpA , Qi ,...,2,1 , (20) перетворюються у рівність. Якщо це обмеження має номер j і належить до l -ї локальної задачі, то, починаючи з точки 1 ~ Qp , розширюємо індексну Розв’язання нелінійних оптимізаційних задач розподілу ресурсів у великих … Системні дослідження та інформаційні технології, 2016, № 3 81 множину }{ ~ jJJ ll  і розв’язуємо нову локальну координуючу задачу з цільовою функцією )( 1 QJ p . Теорема 3. У разі розширення індексної множини }{ ~ jJJ ll  зна- чення цільових функцій локальних координуючих задач у точці переходу збігаються. Доведення. Випишемо обмеження, що в точці 1 ~ Qp перетворюється в рівність. 0~ 1   j lQ j ll j l bpBpA , lJj . (21) Верхнім індексом j позначено рядки матриць lA і lB і відповідний елемент вектора lb . Оскільки точку 1 ~ Qp отримано в процесі мінімізації функції )( 1 QJ p , то за алгоритмом допустиме значення lp , що належить грані (20), отримує- мо за формулою (16) )()())(( 1 11 lllllllll JQJJJJlJJJJl bpBAAAcAAAAEp    . Підставивши цей вираз у формулу (21), знаходимо вираз для 1 ~ Qp і яв- ні вирази для )( 1 QJ p та )( 1~  QJ p . Використовуючи рекурентні форму- ли для обертання матриць [12], можна показати, що виконується рівність )~()~( 11   QJQJ pp . Наведений алгоритм будує таку послідовність точок }{ 1 k Qp  , що, при- наймні у тих з них, у яких досягаються мінімуми локальних координуючих задач, значення цільової функції координуючої задачі )( 1 Qp монотонно спадає. Дійсно, оскільки в початковій точці 0 1Qp як набори індексів 0 iJ для побудови локальної координуючої задачі використовуються набори актив- них обмежень, то в цій точці цільові функції локальної координуючої та ко- ординуючої задач збігаються: )()( 0 1 0 10   QQJ pp . Метод спряжених гра- дієнтів здійснює монотонну мінімізацію квадратичної функції. Якщо він не приводить до точки мінімуму локальної координуючої задачі, то розширю- ється одна з множин 0 iJ і відбувається перехід до нової локальної коорди- нуючої задачі, причому значення двох локальних координуючих задач, що розв’язуються послідовно, у точці переходу збігаються. Відповідно до припущення щодо лінійної незалежності векторів обме- жень через скінченну кількість кроків, що не перевищує розмірність вектора p , процес розширення індексних множин припиниться і досягається точка мінімуму локальної координуючої задачі. Тобто кількість кроків алгоритму, у результаті яких буде отримано точку мінімуму локальної координуючої задачі, не перевищує n . О.Є. Кірік ISSN 1681–6048 System Research & Information Technologies, 2016, № 3 82 Нехай точку l Qp 1 отримано в результаті розв’язання задачі )(min 1 QJ pl . Якщо ця точка не є розв’язком координуючої задачі (10), то виконується нерівність   ),,...,,()( 1211 l Q l Q lll QJ ppppFpl )()),(,...),(),(( 1111211 l Q l Q l QQ l Q l Q ppppppppF   , оскільки l ip , знайдені за формулами (16) для індексних множин l iJ , є допу- стимими, а )( 1 l Qi pp  — оптимальні точки блочних підзадач за фіксованих l Qp 1 . Є очевидним, що )()( 1 0 1 l QQ pp   . Обираючи новою початковою точкою l Qp 1 , повторюємо цю процедуру і отримуємо точку мінімуму локальної координуючої задачі, у якій значення )( 1 Qp строго менше за значення цієї функції в точках мінімуму раніше побудованих локальних координуючих задач. Таким чином, значення функ- ції )( 1 Qp уздовж послідовності точок мінімуму локальних координуючих задач монотонно спадає. Це означає, що якщо розглядати дві точки мініму- му різних локальних координуючих задач l Qp 1 і k Qp 1 , kl  , то множини індексів активних обмежень у таких точках є різними. Якби )()( 11 k Qi l Qi pJpJ   , Qi ,...,2,1 , то )()( 11 k Q l Q pp   , а відповідно до побудови процесу )()( 11 k Q l Q pp   , kl  . З іншого боку, всі множини індексів активних обмежень є підмножи- нами скінченної множини номерів усіх обмежень задачі (6) і тому кількість таких підмножин є скінченною. Це означає, що процес повинен завершитися після скінченної кількості в точці мінімуму координуючої задачі, бо якщо отримана точка не є розв’язком координуючої задачі, процес може бути продовжений. Це означає, що є справедливою така теорема. Теорема 4. Якщо в точках мінімуму локальних координуючих задач виконуються умови регулярності, то процедура буде знаходити оптималь- ний розв’язок за скінченну кількість ітерацій. Припустімо тепер, що точка 1Qp , отримана як розв’язок чергової ло- кальної квадратичної задачі і така, що не є розв’язком координуючої задачі, не є регулярною. Це означає, що серед компонентів векторів Лагранжа u ( Qi ,...,2,1 ) є від’ємні. Якби це було не так, точка 1Qp була б розв’язком координуючої задачі. Нехай 0j iu , },...,2,1{ Qi , iJj . Побудуємо нову індексну множину }/{ ~~ jJJ ii  шляхом відкидання з множини iJ індексу j . Побудуємо ло- кальну координуючу задачу для цієї скороченої індексної множини і припу- стимо, що знайдено розв’язок цієї нової задачі 1 ~~ Qp . Локальні координуючі Розв’язання нелінійних оптимізаційних задач розподілу ресурсів у великих … Системні дослідження та інформаційні технології, 2016, № 3 83 задачі, побудовані для множин iJ і iJ ~~ , є еквівалентними відповідно за- дачам },...,2,1,0:)(min{ 1 QibpBpApF iii JQJiJ   (22) та },...,2,1,0:)({min ~~1~~~~ QibpBpApF iii JQJiJ   . (23) Оскільки допустима множина задачі (22) є більш вузькою порівняно з допустимою множиною задачі (23), то ) ~~, ~~,..., ~~, ~~(),,...,,( 121121   QQQQ ppppFppppF , де ip і ip ~~ знаходимо за формулою (16) для множин iJ і iJ ~~ відповідно. Остання нерівність може бути переписана у вигляді ) ~~()( 1~~1   QJQJ pp . Треба показати, що точки 1Qp і 1 ~~ Qp не збігаються, інакше процес не зсунувся б з точки 1Qp . Теорема 5. Нехай обмеження локальної координуючої задачі (23) утво- рені з обмежень іншої локальної координуючої задачі (22) шляхом видален- ня рівняння, для якого 0j iu , },...,2,1{ Qi , iJj . (24) Тоді точки мінімуму цих задач не збігаються. Доведення. Нехай в рівнянні (24) li  , тобто 0j lu , а точка мінімуму задачі (22) ),,...,,( 121  QQ ppppp є оптимальною точкою і для задачі (23). Випишемо необхідні умови екстремуму для цих задач [11]. Вони мають ви- гляд відповідно 0)( 1     Q i JiiJ uApF , (25) 0)( 11   iii JQJQiJ bpBppA , Qi ,...,2,1 та 0)( 1 ~~~~     Q i J iiJ wApF , (26) 0)( ~~1~~1~~   iii JQJQiJ bpBppA , Qi ,...,2,1 . Тут iJu та iJ w~~ — вектори множників Лагранжа задач (22) і (23). Віднімаючи нерівності (25) і (26), дістаємо 0))(()( 11 ~~ 1 ~~             t i t i Q i jt Jt t i j l j l Q i J Q i J AwuAuwAuA i iiJiiJ , О.Є. Кірік ISSN 1681–6048 System Research & Information Technologies, 2016, № 3 84 що є неможливим, оскільки 0j lu , а матриці iJA є невиродженими. Це і доводить твердження теореми. Таким чином, процедура відкидання індексу з множини активних об- межень дозволяє продовжувати процес мінімізації і не порушує його моно- тонності. Це означає, що і в цьому випадку розв’язок буде знайдено за скін- ченну кількість кроків. ВИСНОВКИ Запропонований метод розв’язання нелінійної задачі блочної структури зі зв’язуючими змінними є поєднанням апроксимаційного методу першого порядку та прямого методу декомпозиції. Декомпозиційний прийом полягає у тому, що для задач блочної струк- тури зі зв’язуючими змінними загальні ресурси змінюються від кроку до кроку таким чином, аби блочні підсистеми (набори блочних підзадач) пра- цювали дедалі ефективніше з точки зору ефективності роботи всієї системи. На відміну від задачі зі зв’язуючими обмеженнями [7], де швидкість збіжності при розв’язанні двоїстої координуючої задачі залежить від пове- дінки її цільової функції в околі оптимальної точки, у разі застосування прямої схеми декомпозиції розв’язок координуючої задачі завжди отри- мується за скінченну кількість кроків, що є важливим з огляду на те, що координуюча задача у запропонованій триступеневій схемі повинна розв’язуватися багаторазово як допоміжна в апроксимаційному процесі най- вищого рівня. Загалом швидкість збіжності для розв’язання вихідної задачі (1) зале- жить від функцій, що визначають її критерій і обмеження, та обраного ме- тоду апроксимації. Для задач із сепарабельними функціями можна викорис- товувати апроксимуючі методи більш високого порядку, беручи у виразі (3) як матрицю kD деякі наближення до матриці других похідних або функцію Лагранжа задачі (1), як це робиться у методах послідовного квадратичного програмування. Очевидно, що у такому випадку отримаємо швидкість збіж- ності вищу, ніж у методах першого порядку і побудова таких процедур мо- же стати перспективним напрямом для подальших досліджень. ЛІТЕРАТУРА 1. Лэсдон Л.C. Оптимизация больших систем / Л.C. Лэсдон. — М.: Наука, 1975. — 432 с. 2. Цурков В.И. Декомпозиция в задачах большой размерности / В.И. Цурков. — М.: Наука, 1981. — 352 с. 3. Лаптин Ю.П. Некоторые вопросы решения блочных нелинейных задач опти- мизации со связывающими переменными / Ю.П. Лаптин, Н.Г. Журбенко // Кибернетика и системный анализ. — 2006. — № 2. — C. 47–55. 4. Shefi R. Rate of Convergence Analysis of Decomposition Methods Based on the Proximal Method of Multipliers for Convex Minimization / R. Shefi, M. Te- boulle // SIAM J. Optim. — 014. — 24, Issue 1. — P. 269–297. DOI: 10.1137/1309.10774. Розв’язання нелінійних оптимізаційних задач розподілу ресурсів у великих … Системні дослідження та інформаційні технології, 2016, № 3 85 5. Andersson H. A new decomposition algorithm for a liquefied natural gas inventory routing problem / H. Andersson, M. Christiansen, G. Desaulniers // International Journal of Production Research. — 2016. — 54, Issue 2. — P. 564–578. DOI: 10.1080/00207543.2015.1037024 6. Лаптин Ю.П. Точные штрафные функции и выпуклые продолжения функций в схемах декомпозиции по переменным / Ю.П. Лаптин // Кибернетика и сис- темный анализ. — 2016. — 52, № 1. — C. 93–104. 7. Кірік О.Є. Підхід до розв’язання нелінійних оптимізаційних задач блочної структури зі зв’язуючими обмеженнями / О.Є. Кірік // Наукові вісті НТУУ «КПІ». — К., 2015. — № 5. — С. 32–38. 8. Кірік О.Є. Алгоритми лінеаризації та спряжених градієнтів для нелінійних за- дач розподілу потоків / О.Є. Кірік // Наукові вісті НТУУ «КПІ». — К., 2007. — № 3. — С. 67–73. 9. Пшеничный Б.Н. Численные методы в экстремальных задачах / Б.Н. Пшенич- ный, Ю.М. Данилин. — М.: Наука, 1975. — 319 с. 10. Александрова В.М. Оптимізаційні моделі та алгоритми для мережевих задач розподілу ресурсів / В.М. Александрова, О.Є. Кірік // Наукові вісті НТУУ «КПІ». — 2014. — № 4. — C. 39–45. 11. Пшеничный В.Н. Выпуклый анализ и экстремальные задачи / В.Н. Пшенич- ный. — М.: Наука, 1980. — 320 с. 12. Фаддеев Д.К. Вычислительные методы линейной алгебры / Д.К. Фаддеев, В.Н. Фаддеева. — М.: Физматгиз, 1960. — 656 с. Надійшла 06.04.2016
id	journaliasakpiua-article-85428
institution	System research and information technologies
keywords_txt_mv	keywords
language	Ukrainian
last_indexed	2025-07-17T10:20:54Z
publishDate	2016
publisher	The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
record_format	ojs
resource_txt_mv	journaliasakpiua/b2/c5ca4106b66573b5e716a4d470d9f1b2.pdf
spelling	journaliasakpiua-article-854282018-03-30T15:27:13Z Solving resource distribution nonlinear optimization problems in large block-structured systems with binding parameters Решение нелинейных оптимизационных задач распределения ресурсов в больших блочно-структурированных системах со связывающими параметрами Розв’язання нелінійних оптимізаційних задач розподілу ресурсів у великих блочно-структурованих системах зі зв’язуючими параметрами Kirik, Olena E. resource distribution problems optimization models approximation methods nonlinear programming decomposition algorithms задачи распределения ресурсов оптимизационные модели аппроксимирующие методы нелинейное программирование алгоритмы декомпозиции задачі розподілу ресурсів оптимізаційні моделі апроксимуючі методи нелінійне програмування алгоритми декомпозиції Solving non-linear optimization problems with a block structure and binding parameters (variables) is realized by a combination of the approximation and decomposition approaches. The approximation method is chosen so that the decomposition of the mathematical programming problem can be performed without making any assumptions about the convexity or additive separability of objective functions and constraints. The coordinating and block sub-problems that are auxiliary in the approximation method, are solved using a finite number of steps. In the course of calculation, binding variables vary from step to step of the iterative process, providing a monotonic decrease of the value of the coordinating problem objective function; in other words, the amount of shared resources is changed in such a way that block subsystems operate more and more efficiently in terms of the efficiency of the whole system. Решение нелинейных оптимизационных задач блочной структуры со связывающими параметрами (переменными) реализуется путем комбинации аппроксимационного и декомпозиционного подходов. Аппроксимационный метод выбран таким образом, чтобы декомпозицию задачи математического программирования можно было выполнять без каких-либо предположений относительно выпуклости или аддитивной сепарабельности функций критерия и ограничений. Координирующая и блочные подзадачи, служащие вспомогательными в аппроксимационном методе, решаются за конечное число шагов. В ходе вычислений связывающие переменные изменяются от шага к шагу итерационного процесса, обеспечивая монотонное уменьшение значения целевой функции координирующей задачи, т.е. количество общих ресурсов изменяется таким образом, чтобы блочные подсистемы работали все эффективнее с точки зрения эффективности работы всей системы. Розв’язання нелінійних оптимізаційних задач блочної структури зі зв’язуючими параметрами (змінними) реалізується шляхом комбінації апроксимаційного та декомпозиційного підходів. Апроксимаційний метод обрано таким чином, щоб декомпозицію задачі математичного програмування можна виконувати без будь-яких припущень щодо опуклості або адитивної сепарабельності функцій критерію та обмежень. Координуюча та блочні підзадачі, що є допоміжними в апроксимаційному методі, розв’язуються за скінченну кількість кроків. У ході обчислень зв’язуючі параметри змінюються від кроку до кроку ітераційного процесу, забезпечуючи монотонне зменшення значення цільової функції координуючої задачі, тобто кількість загальних ресурсів змінюється таким чином, аби блочні підсистеми працювали дедалі ефективніше з точки зору ефективності роботи всієї системи. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2016-09-26 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/85428 10.20535/SRIT.2308-8893.2016.3.07 System research and information technologies; No. 3 (2016); 72-85 Системные исследования и информационные технологии; № 3 (2016); 72-85 Системні дослідження та інформаційні технології; № 3 (2016); 72-85 2308-8893 1681-6048 uk https://journal.iasa.kpi.ua/article/view/85428/81111 Copyright (c) 2021 System research and information technologies
spellingShingle	задачі розподілу ресурсів оптимізаційні моделі апроксимуючі методи нелінійне програмування алгоритми декомпозиції Kirik, Olena E. Розв’язання нелінійних оптимізаційних задач розподілу ресурсів у великих блочно-структурованих системах зі зв’язуючими параметрами
title	Розв’язання нелінійних оптимізаційних задач розподілу ресурсів у великих блочно-структурованих системах зі зв’язуючими параметрами
title_alt	Solving resource distribution nonlinear optimization problems in large block-structured systems with binding parameters Решение нелинейных оптимизационных задач распределения ресурсов в больших блочно-структурированных системах со связывающими параметрами
title_full	Розв’язання нелінійних оптимізаційних задач розподілу ресурсів у великих блочно-структурованих системах зі зв’язуючими параметрами
title_fullStr	Розв’язання нелінійних оптимізаційних задач розподілу ресурсів у великих блочно-структурованих системах зі зв’язуючими параметрами
title_full_unstemmed	Розв’язання нелінійних оптимізаційних задач розподілу ресурсів у великих блочно-структурованих системах зі зв’язуючими параметрами
title_short	Розв’язання нелінійних оптимізаційних задач розподілу ресурсів у великих блочно-структурованих системах зі зв’язуючими параметрами
title_sort	розв’язання нелінійних оптимізаційних задач розподілу ресурсів у великих блочно-структурованих системах зі зв’язуючими параметрами
topic	задачі розподілу ресурсів оптимізаційні моделі апроксимуючі методи нелінійне програмування алгоритми декомпозиції
topic_facet	resource distribution problems optimization models approximation methods nonlinear programming decomposition algorithms задачи распределения ресурсов оптимизационные модели аппроксимирующие методы нелинейное программирование алгоритмы декомпозиции задачі розподілу ресурсів оптимізаційні моделі апроксимуючі методи нелінійне програмування алгоритми декомпозиції
url	https://journal.iasa.kpi.ua/article/view/85428
work_keys_str_mv	AT kirikolenae solvingresourcedistributionnonlinearoptimizationproblemsinlargeblockstructuredsystemswithbindingparameters AT kirikolenae rešenienelinejnyhoptimizacionnyhzadačraspredeleniâresursovvbolʹšihbločnostrukturirovannyhsistemahsosvâzyvaûŝimiparametrami AT kirikolenae rozvâzannânelíníjnihoptimízacíjnihzadačrozpodíluresursívuvelikihbločnostrukturovanihsistemahzízvâzuûčimiparametrami

Розв’язання нелінійних оптимізаційних задач розподілу ресурсів у великих блочно-структурованих системах зі зв’язуючими параметрами

Institution

Similar Items