Алгоритми ітераційного квадратичного програмування для задач оптимального розподілу потоків

The quadratic programming problem which serves as an auxiliary one in the solution of nonlinear flow distribution problems is reduced to an unconstrained dual problem with a continuously-differentiable piecewise quadratic objective function. Instead of maximization of this implicit function, consecu...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2008
1. Verfasser:	Кірік, О.Є.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України 2008
Schlagworte:	Методи оптимізації, оптимальне управління і теорія ігор
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/14603
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Алгоритми ітераційного квадратичного програмування для задач оптимального розподілу потоків / О.Є. Кірік // Систем. дослідж. та інформ. технології. — 2008. — № 4. — С. 101-113. — Бібліогр.: 14 назв. —укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-14603
record_format	dspace
spelling	irk-123456789-146032013-02-13T03:03:47Z Алгоритми ітераційного квадратичного програмування для задач оптимального розподілу потоків Кірік, О.Є. Методи оптимізації, оптимальне управління і теорія ігор The quadratic programming problem which serves as an auxiliary one in the solution of nonlinear flow distribution problems is reduced to an unconstrained dual problem with a continuously-differentiable piecewise quadratic objective function. Instead of maximization of this implicit function, consecutive maximization of the specific quadratic functions is developed. These functions are constructed in such a way that at the end of the iterative procedure, the coincidence of the obtained solution with the maximum point of the dual problem can be arhieved. Рассмотрена задача квадратичного программирования, которая служит вспомогательной при решении нелинейных задач распределения потоков. Она сводится к безусловной двойственной задаче с непрерывно дифференцируемой кусочно-квадратичной целевой функцией. Вместо максимизации этой неявной функции проводится последовательная максимизация конкретных квадратичных функций, построенных таким образом, чтобы в конце итерационной процедуры добиться совпадения полученного решения с точкой максимума двойственной задачи. Розглянуто задачу квадратичного програмування, що служить допоміжною при розв’язанні нелінійних задач розподілу потоків. Вона зводиться до безумовної двоїстої задачі з неперервно диференційованою кусково-квадратичною цільовою функцією. Замість максимізації цієї неявної функції проводиться послідовна максимізація конкретних квадратичних функцій, побудованих таким чином, аби в кінці ітераційної процедури домогтися співпадіння отриманого розв’язку з точкою максимуму двоїстої задачі. 2008 Article Алгоритми ітераційного квадратичного програмування для задач оптимального розподілу потоків / О.Є. Кірік // Систем. дослідж. та інформ. технології. — 2008. — № 4. — С. 101-113. — Бібліогр.: 14 назв. —укр. 1681–6048 http://dspace.nbuv.gov.ua/handle/123456789/14603 519.8 uk Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Методи оптимізації, оптимальне управління і теорія ігор Методи оптимізації, оптимальне управління і теорія ігор
spellingShingle	Методи оптимізації, оптимальне управління і теорія ігор Методи оптимізації, оптимальне управління і теорія ігор Кірік, О.Є. Алгоритми ітераційного квадратичного програмування для задач оптимального розподілу потоків
description	The quadratic programming problem which serves as an auxiliary one in the solution of nonlinear flow distribution problems is reduced to an unconstrained dual problem with a continuously-differentiable piecewise quadratic objective function. Instead of maximization of this implicit function, consecutive maximization of the specific quadratic functions is developed. These functions are constructed in such a way that at the end of the iterative procedure, the coincidence of the obtained solution with the maximum point of the dual problem can be arhieved.
format	Article
author	Кірік, О.Є.
author_facet	Кірік, О.Є.
author_sort	Кірік, О.Є.
title	Алгоритми ітераційного квадратичного програмування для задач оптимального розподілу потоків
title_short	Алгоритми ітераційного квадратичного програмування для задач оптимального розподілу потоків
title_full	Алгоритми ітераційного квадратичного програмування для задач оптимального розподілу потоків
title_fullStr	Алгоритми ітераційного квадратичного програмування для задач оптимального розподілу потоків
title_full_unstemmed	Алгоритми ітераційного квадратичного програмування для задач оптимального розподілу потоків
title_sort	алгоритми ітераційного квадратичного програмування для задач оптимального розподілу потоків
publisher	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
publishDate	2008
topic_facet	Методи оптимізації, оптимальне управління і теорія ігор
url	http://dspace.nbuv.gov.ua/handle/123456789/14603
citation_txt	Алгоритми ітераційного квадратичного програмування для задач оптимального розподілу потоків / О.Є. Кірік // Систем. дослідж. та інформ. технології. — 2008. — № 4. — С. 101-113. — Бібліогр.: 14 назв. —укр.
work_keys_str_mv	AT kíríkoê algoritmiíteracíjnogokvadratičnogoprogramuvannâdlâzadačoptimalʹnogorozpodílupotokív
first_indexed	2025-07-02T16:09:20Z
last_indexed	2025-07-02T16:09:20Z
_version_	1836552092140961792
fulltext	 О.Є. Кірік, 2008 Системні дослідження та інформаційні технології, 2008, № 1 101 УДК 519.8 АЛГОРИТМИ ІТЕРАЦІЙНОГО КВАДРАТИЧНОГО ПРОГРАМУВАННЯ ДЛЯ ЗАДАЧ ОПТИМАЛЬНОГО РОЗПОДІЛУ ПОТОКІВ О.Є. КІРІК Розглянуто задачу квадратичного програмування, що служить допоміжною при розв’язанні нелінійних задач розподілу потоків. Вона зводиться до безу- мовної двоїстої задачі з неперервно диференційованою кусково-квадратичною цільовою функцією. Замість максимізації цієї неявної функції проводиться по- слідовна максимізація конкретних квадратичних функцій, побудованих таким чином, аби в кінці ітераційної процедури домогтися співпадіння отриманого розв’язку з точкою максимуму двоїстої задачі. ВСТУП При зростаючих потребах суспільства в енергетичних ресурсах стає необ- хідною наявність відповідних інформаційних ресурсів, які б забезпечували якісний, швидкий та зручний розрахунок мереж. Одна з центральних задач дослідження мереж — оптимальний розподіл потоків — має самостійне значення, але може розглядатися і в комплексі більш загальних задач, на- приклад, пов’язаних із проектуванням мереж або розрахунком їх парамет- рів. На відміну від лінійних транспортних задач, задачі оптимізації енерге- тичних систем можуть мати різноманітні нелінійні цільові функції, що обу- мовлює широкий вибір методів їх розрахунків. Одними з найперспективні- ших методів нелінійного програмування вважаються методи послідовного квадратичного програмування (SQP). Їх ще називають методами ітераційно- го квадратичного програмування або рекурсивного квадратичного програ- мування. Засновані на роботах [1–3] методи SQP дозволяють достатньо точ- но імітувати метод Ньютона для оптимізації за наявності обмежень, як це зроблено в оптимізації без обмежень. На кожній основній ітерації здійсню- ється квадратична апроксимація функції Лагранжа основної задачі та буду- ється задача квадратичного програмування, розв’язок якої використовується для формування напрямку в процедурі лінійного пошуку. К. Шитковський [4, 5] успішно реалізував та провів тестові розрахунки за методами SQP і отримав всебічну перевагу порівняно з іншими методами по ефективності, точності та проценту успішного розв’язання задач для великої кількості тес- тових прикладів. Стаття, що пропонується вашій увазі, є продовженням досліджень, роз- початих у роботах [6, 7], присвячених розв’язанню нелінійних задач розпо- ділу потоків із застосуванням методу лінеаризації Б.М. Пшеничного та його модифікацій [8, 9]. Ці методи знайшли світове визнання і мають дуже широ- кий спектр застосувань. В методах Б.М. Пшеничного відбувається заміна О.Є. Кірік ISSN 1681–6048 System Research & Information Technologies, 2008, № 1 102 розв’язання нелінійної задачі розв’язанням послідовності квадратичних за- дач, цільові функції яких є квадратичною апроксимацією цільової функції вихідної задачі або її лінійною апроксимацією з додаванням квадратичного штрафу за великі ухилення аргументу. Відмітимо, що завдяки особливостям структури задач розподілу пото- ків, а саме наявності лінійних обмежень, квадратична апроксимація функції Лагранжа для цих задач співпадає з квадратичною апроксимацією їх цільо- вих функцій. Це означає, що при виборі відповідного методу обчислення крокового множника на основній ітерації алгоритму можна говорити про близькість оцінок ефективності методів Б.М. Пшеничного та SQP для тако- го класу задач. Отже, загальний підхід до нелінійних задач оптимізації за наявності обмежень полягає в заміні вихідної задачі з обмеженнями на іншу, яка розв’язується простіше і може служити основою для побудови деяких ітера- ційних процесів. Найчастіше нелінійну задачу заміняють набором певним чином побудованих задач квадратичного програмування. Оскільки успішне здійснення такої заміни є неможливим без ефективного розв’язання цих до- поміжних задач, постійний інтерес викликають ефективні методи квадрати- чного програмування. При розв’язанні допоміжних квадратичних задач звичайно переходять до двоїстих задач без обмежень. В класичних задачах розподілу потоків іс- нують два типи обмежень: обмеження-рівності, які є аналогом рівнянь Кірх- гофа, та технологічні обмеження на пропускну спроможність мережі. У де- яких роботах [10] звільнення від обмежень відбувається шляхом побудови штрафної функції з простими обмеженнями, а обмеження-рівності виклю- чаються через виділення базису, як в алгоритмах лінійного програмування. Нижче ми пропонуємо перехід до допоміжної задачі без обмежень здійсню- вати шляхом залучення у функцію Лагранжа обмежень-рівностей з подаль- шою її мінімізацією на множині простих обмежень. МАТЕМАТИЧНА МОДЕЛЬ Розглянемо енергетичну систему, яка має структуру мережі. Моделлю кон- фігурації такої системи є граф [11]. Споживачі та розподільчі станції розта- шовані у вершинах (вузлах) графа, транспортні ділянки відповідають його дугам. Задається така інформація: об’єм подачі речовини (газу, нафти, води) в систему, потреби споживачів, довжина ділянок розподільчої системи та технологічні обмеження на її пропускну спроможність. Потрібно розподіли- ти потоки вздовж мережі таким чином, щоб задовольнити всіх споживачів із найменшими загальними витратами на доставку. Відмітимо, що основні співвідношення математичної моделі задачі ро- зподілу потоків навмисне обираються з достатньо загальних міркувань, аби охопити єдиним підходом різноманітні розподільчі системи. Нехай граф ( )VNG ,= містить n вершин (множина N ) та m дуг (множина V ). Кожній дузі Vv∈ співставлена упорядкована пара вершин ( )ji, , Nji ∈, , які є її початком і кінцем. Для кожної вершини i відоме Алгоритми ітераційного квадратичного програмування для задач оптимального розподілу … Системні дослідження та інформаційні технології, 2008, № 1 103 споживання id , а кожній дузі графа v приписаний деякий потік vx , обме- жений знизу і зверху величинами − vr та + vr , та функція вартості протікання потоку ( )vv xF вздовж дуги. Задача знаходження розподілу потоків мінімальної вартості може бути сформульована таким чином: ( ) ( ) min 1 →≡∑ = m v vv xFxF , (1) dAx = , (2) +− ≤≤ rxr , (3) де ( )mxxxx ,...,, 21= — вектор невідомих дугових потоків; =d ),...,,( 21 nddd= — вектор споживання у вузлах; A ( )mn× — матриця інциденцій вузли–дуги. Кожен стовпець v цієї матриці відповідає дузі ),( jiv = , Nji ∈, та містить тільки два ненульових елементи: +1 у рядку i та –1 у рядку j . Виконання співвідношень (2) гарантує задоволення всіх споживачів. Умова сумісності рівнянь (2) отримується їх додаванням і є умовою збалансованості системи. ∑ = = n i id 1 0 . (4) Будемо вважати, що функція ( )⋅F — двічі неперервно диференційована і ( ) 0>″ vv xF для всіх Vv∈ . За умови існування розв’язку остання умова гарантує його єдиність. Цільова функція задачі (1) – (3) може бути представлена, наприклад, в інтегральному вигляді [12] ( ) ( )∑ ∫ = = m v x v v dttfxF 1 0 . (5) Тоді vf — функція, що відображає умовну вартість протікання потоку vx вздовж дуги v , а мінімізація (5) при обмеженнях (2),(3) дає найкращий з точки зору витрат на транспортування розподіл потоків вздовж мережі. Перейдемо до розв’язання цієї задачі. АЛГОРИТМИ ОПТИМІЗАЦІЇ Якщо 0x — початкове наближення до розв’язку нелінійної задачі (1) – (3), то для реалізації ітераційного процесу k k kk pxx α+=+1 , 10 ≤α< k (6) у кожній точці kx знаходимо напрям зсуву ( ) mkk Rxpp ∈= як розв’язок при фіксованому mk Rxx ∈= допоміжної квадратичної задачі: О.Є. Кірік ISSN 1681–6048 System Research & Information Technologies, 2008, № 1 104 ( ) min,, 2 1 →+≡ pcDpppW , (7) dAp ~ = , (8) +− ≤≤ rpr ~~ . (9) Тут ( )xFc ′= — градієнт функції ( )xF ; ( )xFD ′′= — матриця її других похідних (або одинична матриця у випадку методу лінеаризації); Axdd −= ~ , xrr −= −−~ , xrr −= ++~ , px, — скалярний добуток. Припускаємо, що розв’язок допоміжних задач (7) – (9) існує для всіх точок процесу (6). Критерій завершення процесу — це виконання умови 0=p . Побудуємо задачу, двоїсту до (7) – (9). Нехай nEu∈ — вектор двоїстих змінних, які відповідають обмеженням (8). Випишемо функцію Лагранжа ( ) dApupcDppupL ~,,, 2 1, −++= . Згідно із теорією двоїстості [8] розв’язання задачі (7) – (9) еквівалентне максимізації вгнутої неперервно диференційованої функції ( )uH nEu∈ max , (10) де ( ) ( )upLuH rpr ,min ~~ +− ≤≤− = . (11) Більшість методів оптимізації вимагає для своєї реалізації знання не тільки значення функції, але й її похідних. Згідно із теоремою про похідну від функції мінімуму [13] функція ( )uH має неперервну похідну, яку можна обчислити для довільної точки u . Ця похідна дорівнює значенню похідної від ( )upL , по u , взятому у точці мінімуму ( )up∗ ( ) ( ) duApuH ~ −=′ ∗ . Для максимізації гладкої вгнутої функції (10) може бути застосований довільний метод безумовної оптимізації, зокрема метод спряжених градієн- тів [8]. Алгоритм спряжених градієнтів для вгнутої функції. Наведемо ос- новні формули для пошуку максимуму вгнутої функції ( )uH , nEu∈ , врахо- вуючи, що ця процедура еквівалентна пошуку мінімуму опуклої функції ( )uH− . Процес починається з початкової точки 0u . Послідовні наближення ku до оптимальної точки одержуються за рекурентними формулами k k kk zuu β+=+1 , де Алгоритми ітераційного квадратичного програмування для задач оптимального розподілу … Системні дослідження та інформаційні технології, 2008, № 1 105 ( )00 uHz ′= , ( ) ( ) ( ) ( ) ( ) 1 11 1 , , − −− − ′ ′−′′ +′= k kk kkk kk z zuH uHuHuH uHz , 0>k . (12) Вибір множника kβ на кожному k кроці здійснюється з вимоги ( ) ( )kkk k k zuHzuH ββ β +=+ ≥0 max , (13) ,...2,1,0=k При максимізації неквадратичних функцій метод спряжених градієнтів із скінченного стає ітераційним. У такому випадку після )1( +n -ї ітерації процедури циклічно повторюються із заміною 0u на 1+nu , а обчислення за- кінчуються, коли градієнт ( )uH ′ обертається в нуль з певною точністю. Дослідження структури двоїстої задачі. Поглянемо тепер, як, викори- стовуючи необхідні умови екстремуму [13], можна конкретизувати вигляд функції ( )uH . Мінімум у виразі (11) з урахуванням простих двосторонніх обмежень (9) досягається у точці ( ) mEup ∈ з компонентами ( )upi       ≤ << ≥ = −− +− ++ ,~~якщо,~ ~~~якщо,~ ,~~якщо,~ ii ii ii rur ruru rur p i ii i i , (14) mi ,...,2,1= . Тут ( )uAcDu T ii += −1~ , а 1− iD — i -та строка матриці 1−D . Ця формула зв’язку двоїстих змінних з вихідними дозволяє представи- ти цільову функцію задачі (10) у такому вигляді: ( ) ( ) ( ) uduDhuhuH ,~, 2 1 −−= , (15) де ( ) ( ) ( ) ( )( )Tm upupupuh ...,, 21= . Замість максимізації неявної функції ( )H u будемо проводити послідов- ну максимізацію конкретних квадратичних функцій, побудованих таким чи- ном, аби в кінці ітераційної процедури домогтися співпадіння отриманого розв’язку з точкою максимуму функції ( )uH . Позначимо { }+− ≤≤= rprpM ~~: множину точок, що утворюються на- борами простих обмежень задачі (7)–(9). Як було показано вище, розв’язання цієї задачі можна замінити розв’язанням двоїстої задачі ( )upL Mpu ,minmax 0 ∈≥ , розмірність якої визначається числом обмежень-рівностей. Нехай ( )up — результат розв’язання при фіксованому uu = задачі О.Є. Кірік ISSN 1681–6048 System Research & Information Technologies, 2008, № 1 106 ( ) min, →upL , (16) +≤ rp ~ , (17) −−≤− rp ~ , (18) а ( ) 0≥+ uλ та ( ) 0≥− uλ — вектори множників Лагранжа цієї задачі, що від- повідають обмеженням (17) та (18). Якщо Mp∈ — довільна допустима точка, то серед обмежень (17),(18) можна виділити ті, що задовольняються як рівності. Означення 1. Нехай є множина точок, що описується системою нерів- ностей. Гранню цієї множини назвемо підмножину, яка визначається набо- ром обмежень, що задовольняються як рівності. Покладемо ( ) { }++ == ii rpIipJ ~: , ( ) { }−− == ii rpIipJ ~: , де iI — i -та строка одиничної матриці I . Структура множини M гарантує виконання умови невиродженості: для наборів індексів ( ) ( ) ( )pJpJpJ −+=  , що породжуються довільною допустимою точкою p , вектори iI , ( )pJi∈ є лінійно незалежними, оскіль- ки жодна компонента вектора p не може одночасно досягати своєї верхньої та нижньої межі. Введемо означення регулярності. Означення 2. Нехай при фіксованому u задачі (16) – (18) розв’язані, знайдені оптимальні точки ( )upp = та множини індексів активних обме- жень ( )pJ + та ( )pJ − . Точка u називається регулярною, якщо множники Лагранжа, що від- повідають активним обмеженням, є строго додатними ( ) 0>+ uiλ , ( )pJi +∈ ; ( ) 0>− uiλ , ( )pJi −∈ . Означення 3. Нехай для регулярної точки u визначені набори актив- них обмежень +J та −J . Підмножина множини регулярних точок u , що на- лежать околу u , якому відповідає даний фіксований набір активних обме- жень та незмінні знаки множників Лагранжа ( ) 0>+ uiλ , +∈ Ji ; ( ) 0>− uiλ , −∈ Ji , називається регулярною областю для функції ( )uH . Систему активних обмежень можна записати у вигляді JJ rpI = , де JI — одинична матриця з вилученими рядками, що відповідають неактив- ним обмеженням; Jr — вектор, який складається з відповідних компонент верхніх та нижніх границь вектора p . Лема. У кожній регулярній області функція ( )uH є квадратичною. Доведення. Функція ( )upL , є строго опуклою по p та диференційова- ною по u . Мінімум ( )upL , досягається в єдиній точці ( )up . Для регулярної точки u необхідні умови екстремуму задачі Алгоритми ітераційного квадратичного програмування для задач оптимального розподілу … Системні дослідження та інформаційні технології, 2008, № 1 107 ( )upL Mp ,min ∈ (19) можуть бути виписані у такій формі: 0=λ+++ J T J T IuADpc , JJ rpI = , 0>λ J , де Jλ — вектор, який складається з компонент векторів +λ та −λ , що відпо- відають активним компонентам вектора p . Звідси ( )( ) JJ T J DrEDcuAEIDp 11 −− −+−−= , (20) ( )J T JJ DrcuAE ++−=λ , (21) де ( ) J T JJ T JJ IIIIE 1− = . Використовуючи вираз для градієнта ( ) ( ) duApuH ~ −=′ та формулу (20), отримаємо, що для тих u , при яких матрицею активних обмежень за- дачі (16)–(18) є JI ( ) ( ) uduuAEIADuH J T JJ ,, 2 1 1 −−−= − , (22) де ( ) dDrEDcEIDd JJJJ ~11 ++−= −− . Таким чином, ми визначили вигляд функції ( )uH всередині регулярної області. В цілому функція ( )uH — вгнута, гладка, кусково-квадратична, причому перехід від однієї квадратичної складової до іншої здійснюється під час переходу від однієї регулярної області до іншої. Функція ( )uH є не- перервною, але в місцях переходів можливі розриви її похідних. У процесі максимізації ( )uH доцільно використовувати її конкретний вигляд в областях регулярності. Максимізація квадратичної функції в регулярній області. Відповід- но до означення 3, кожна регулярна область для функції ( )uH визначається співвідношеннями JJ rpI = , 0>λ J . (23) Всередині області вигляд функції ( )uH може бути конкретизований за допомогою формули (22). Для максимізації цієї конкретної квадратичної функції можна застосо- вувати метод спряжених градієнтів для квадратичних функцій, що збігаєть- ся за скінченне число кроків. Однак цей процес не повинен виводити за ме- жі регулярної області, де функція ( )uH має інший вигляд. Якщо в деякій точці вздовж обраного напрямку одне з неактивних обмежень обертається на рівність або один з множників Лагранжа, які відповідають активним об- меженням, стає рівним нулю, то це може служити ознакою виходу на межу регулярної області. Для відповідного контролю можуть використовуватися формули залежності p та λ від u (20), (21). О.Є. Кірік ISSN 1681–6048 System Research & Information Technologies, 2008, № 1 108 Процедура виходу з нерегулярної точки. В нерегулярних точках від- бувається гладке поєднання різних квадратичних функцій, що утворюють функцію ( )uH . Для виходу з нерегулярної точки робимо крок у напрямку, в якому значення функції ( )uH строго зростає. Оскільки функція ( )uH є ди- ференційованою, то можемо зробити крок в напрямку градієнта ( )uH ′ , або крок алгоритму спряжених градієнтів (12). Цей метод також вимагає знання тільки перших похідних функції, а збігається, взагалі кажучи, за менше чис- ло ітерацій, ніж метод найскорішого спуску. При цьому для вибору кроку необхідно реалізувати процедуру одновимірного пошуку (13). Алгоритм розв’язання кусково-квадратичної задачі. Обираємо як початкову довільну точку 0u . Перевіряємо, чи є точка 0u регулярною. Для цього розв’язуємо задачі, двоїсті до (16)–(18) при 0uu = : ( ) max, →λλ −+W , (24) 0≥λ+ , 0≥λ− , де ( ) ( ) ( ) −−+−−−−= −+−−+−+−−+ λλλλλλλλ ,, 2 1, 11 uAcDDW T ( )uerr −+− −−++ ,, λλ , ( ) ( ) duuAcuAcDue TT ~,, 2 1 1 −++−= − . Знаходимо двоїсті змінні ( )0ui +λ , ( )0ui −λ , ( mi ,...,2,1= ), оптимальні розв’язки ( )−+− −++−= λλ01 uAcDp T і множини індексів ( )pJ + та ( )pJ − . Перевіряємо, чи є множники Лагранжа, що відповідають активним об- меженням, строго додатними. Можливі два випадки. 1. Точка 0u є регулярною. Розв’язуємо задачу квадратичного програ- мування ( ) ( ) max,, 2 1 1 →−−−≡ − uduuAEIADuH J T JJ методом спряжених градієнтів для квадратичних функцій [8]. Метод збіга- ється за скінченне число кроків. Для контролю за приналежністю точок u регулярній області на кожно- му кроці робимо таку перевірку. Обчислюємо ( )( ) ( )         = − +++− −= +− −− + mi sEID rDrEDcuAEID k Ji iJJi kT Ji ik ,...,2,1,min 11 11 1α . Алгоритми ітераційного квадратичного програмування для задач оптимального розподілу … Системні дослідження та інформаційні технології, 2008, № 1 109 Мінімум береться по тих −+ ∉∉ JiJi , , для яких ( ) 011 <− +− k Ji sEID . ( ) ( ) ( ) ( )         = ++ −=α ++ mi sE DrEcuAE k iiJ JiJ kT iJ ik ,...,2,1,min 1`1 . Мінімум береться по тих −+ ∈∈ JiJi , , для яких ( ) 01 <+k iiJ sE . Тут ku — чергова точка, яку отримуємо в процесі реалізації алгоритму спряжених градієнтів; 1+ks — вектор зсуву з цієї точки. { }111 ,min~ +++ = kkk ααα . Якщо 1+kα — відповідна довжина кроку спряжених градієнтів і вико- нується умова 11 ~ ++ < kk αα , то 1 1 1 + ++=+ k k k suu k α , і процес продовжується. Якщо ж 11 ~ ++ ≥ kk αα , то 1 1 ~1 + ++=+ k k k suu k α , і процес застосування методу спряжених градієнтів закінчено. У цьому випадку отриману точку обираємо початковою і далі працюємо з новою точкою так само, як з вихідною 0u . 2. Точка 0u є нерегулярною. Застосовуємо процедуру виходу з нерегу- лярної точки. Критерієм оптимальності служить виконання умови ( ) 0=′ uH . Зробимо зауваження щодо організації обчислень. Зауваження 1. Константи ( ) ( ) duuAcuAcDue TT ~,, 2 1 1 −++−= − можна опустити, оскільки їх відкидання не змінює оптимальної точки. Зауваження 2. Цільова функція задачі (24) є адитивно-сепарабельною. Це означає, що розв’язання цієї задачі легко замінити розв’язанням m дво- вимірних квадратичних задач: ( ) ( ) ( ) max~~ 2 1 2 →+++−−− −−++−+ iiiiiiii ii ruru D λλλλ , 0≥+ iλ , 0≥− iλ , mi ,...,2,1= . У формулюванні цих задач використані введені раніше позначення ( )uAcDu T ii += −1~ , а iiD — діагональні елементи матриці D . Обґрунтування збіжності. Наведений вище алгоритм визначає таку послідовність { }ku допустимих точок двоїстої задачі (10), вздовж якої зна- чення функції ( )uH монотонно зростає. Розглянемо тільки ті точки цієї пос- лідовності, які лежать у регулярних областях та є початковими для даної процедури. О.Є. Кірік ISSN 1681–6048 System Research & Information Technologies, 2008, № 1 110 Нехай ku та mu , km > — точки, які служать вихідними для процеду- ри спряжених градієнтів у різних регулярних областях. Тоді множини номе- рів активних обмежень в цих областях є різними, тому що якби ( )( ) ( )( )mk upJupJ ++ = , ( )( ) ( )( )mk upJupJ −− = , (25) то ( ) ( )mk uHuH = . Але відповідно до побудови процесу ( ) ( )mk uHuH < при km > , так що рівностей (25) бути не може. З другого боку, всі множини ( )( )kupJ + , ( )( )kupJ − є підмножинами скінченних множин простих обмежень, і тому число таких підмножин є скінченним. Максимізація квадратичної функції в регулярній області відбу- вається за скінченне число кроків. Отже, після цього ми прийдемо в область, яка містить точку максимуму функції ( )uH , бо інакше процес перебору ре- гулярних областей можна було би продовжити. Якщо ж всі точки побудованої послідовності }{ ku є нерегулярними, то даний метод є просто реалізацією методу спряжених градієнтів (12),(13). Збіжність цього методу для вгнутих диференційованих функцій доведена у роботі [8]. Таким чином, дана процедура за скінченне число кроків приводить в окіл точки максимуму функції ( )uH . Швидкість збіжності методу залежить від поведінки функції ( )uH в околі точки максимуму. Якщо ця точка є ре- гулярною, то, виходячи з неперервної залежності p , +λ та −λ від u , умови регулярності будуть виконуватися і в деякому її околі. Максимізація ( )uH в околі точки максимуму буде здійснюватися методом спряжених градієнтів для квадратичних функцій, що не вимагає процедури одновимірного пошу- ку. Якщо ж точка максимуму є нерегулярною, то вона буде досягатися зі швидкістю процесу (12),(13). Теорема. Якщо точка максимуму u цільової функції двоїстої задачі (10) є регулярною, то метод збігається за скінченне число кроків. Якщо ж у точці u умови регулярності не виконуються, то процес збігається до точки u зі швидкістю методу спряжених градієнтів. ОБЧИСЛЮВАЛЬНІ АСПЕКТИ Одне з важливих питань, від якого залежить ефективність алгоритмів — це спосіб збереження та обробки даних. Реальні енергетичні мережі містять дуже велику кількість об’єктів, але кожен з них пов’язаний з обмеженою групою інших об’єктів. Це означає, що матриця інциденцій мережі при своїх значних розмірах є дуже розрідженою і має специфічну структуру. Яким би чином не задавалася інформація про мережу — графічно (рис. 1) або таблично (рис. 2) — в ході обчислень доцільно працювати тіль- ки з ненульовими елементами. Оскільки матриця інциденцій, крім нульових, містить тільки одиничні елементи, при операціях з нею можна взагалі ви- ключити процедури множення. Алгоритми ітераційного квадратичного програмування для задач оптимального розподілу … Системні дослідження та інформаційні технології, 2008, № 1 111 Інформація про структуру мережі може зберігатися у вигляді двох век- торів ( )mbbbb ,...,, 21= та ( )meeee ,...,, 21= , розмірність яких дорівнює кіль- кості дуг мережі. Індекс компоненти масиву відповідає номеру дуги. У пер- шому з масивів зберігаються номери вершин, звідки ці дуги виходять, у другому — номери вершин, куди вони входять. Якщо A — матриця інци- денцій цієї мережі, а x — довільний вектор, то для кожної строки ni ,...,2,1= ∑∑ −= r r s si xxxA , причому в суму включаються тільки ті номери s та r , для яких ibr = та ies = . Рис. 1. Модельний приклад мережі: вузлові параметри — назва вузла, споживання у вузлі; дугові параметри — [нижня межа пропускної спроможності потоку < верх- ня межа пропускної спроможності потоку: довжина дуги ]: обчислена величина потоку Рис. 2. Табличне представлення мережі О.Є. Кірік ISSN 1681–6048 System Research & Information Technologies, 2008, № 1 112 Аналогічно для кожного mj ,...,2,1= rs T j xxxA −= , де jbr = , jes = . ( ) J T JJ T JJ IIIIE 1− = — це матриця проектування на деяку грань, яка ви- значається набором простих обмежень. У формулюванні алгоритму вона була всюди формально виписана. Але слід зауважити, що, виходячи з її кон- кретної структури, наведені в алгоритмах формули можуть бути суттєво спрощені. Оскільки JT JJ III = є одиничною матрицею розмірності J , то JE є одиничною матрицею, в якій рядки, що відповідають неактивним об- меженням, просто замінені нульовими рядками. При обчисленні добутку цієї матриці на довільний вектор не треба виконувати операцію множення. Достатньо просто замінити відповідні елементи цього вектора на нульові. ( )    ∉ ∈ = .якщо,0 ,якщо, Ji Jiz zE i iJ ВИСНОВКИ Досліджено задачу квадратичного програмування, що служить допоміжною при розв’язанні нелінійних задач розподілу потоків. Вона зводиться до двоїстої задачі без обмежень з кусково-квадратичною неперервно- диференційованою цільовою функцією, для розв’язання якої пропонується алгоритм, що є поєднанням процедур спряжених градієнтів для квадратич- них та вгнутих функцій. Природно виникає питання, чи не вигідніше було би в процесі розв’язання допоміжної квадратичної задачі переходити до двоїстої, вклю- чаючи в функцію Лагранжа всі обмеження. У цьому випадку теоретично ми завжди отримуємо розв’язок за скінченне число кроків. Такий підхід доста- тньо ретельно досліджувався у роботі [14]. Хоча за трудомісткістю загальної ітерації такі методи простіші, їх ефективність нівелюється за рахунок знач- ного збільшення розмірності та чуттєвості алгоритмів до накопичення похи- бок обчислень. У тестовому прикладі (см. рис. 1) задача розподілу потоків містить 9 обмежень-рівностей та 12 простих двосторонніх обмежень. Якщо вводити у функцію Лагранжа всі обмеження, то розмірність двоїстої допоміжної задачі буде дорівнювати 33. Якщо ж скористатися описаним вище алгоритмом, то на кожному основному кроці потрібно розв’язувати одну квадратичну зада- чу без обмежень розмірності 9-ти та дванадцять простих двовимірних задач. У процесі реалізації побудованого алгоритму відбуваються розрахунки за процедурою спряжених градієнтів для квадратичних та нелінійних вгну- тих функцій, причому заздалегідь невідомо, скільки кроків буде зроблено за кожним з цих методів. Звичайно, вони відрізняються трудомісткістю. Але й у найгіршому випадку, коли всі точки процесу є нерегулярними, це буде просто реалізацією методу спряжених градієнтів для вгнутих функцій, що Алгоритми ітераційного квадратичного програмування для задач оптимального розподілу … Системні дослідження та інформаційні технології, 2008, № 1 113 вимагає процедури одновимірного пошуку на кожному кроці. За сприятли- вих обставин ми отримуємо розв’язок за скінченне число кроків. Оскільки на відміну від багатьох інших методів, методи Б.М. Пше- ничного добре справляються з нелінійними обмеженнями-рівностями, за- пропонований вище підхід доцільно розповсюдити на випадок потокових задач з нелінійними обмеженнями, що можуть розглядатися як варіант уза- гальнених рівнянь Кірхгофа. Це послужить основою для нового напрямку досліджень. ЛІТЕРАТУРА 1. Biggs M.C. Constrained Minimization Using Recursive Quadratic Programming // Towards Global Optimization (L.C.W. Dixon and G.P. Szergo, eds.). — North- Holland. — 1975. — P. 341–349. 2. Han S.P.A. Globally Convergent Method for Nonlinear Programming // J. Optimiza- tion Theory and Applications. — 1977. — 22. — P. 297. 3. Powell M.J.D. Variable Metric Methods for Constrained Optimization. Mathematical Programming: The State of the Art (A. Bachem, M. Grotschel and B. Korte, eds.). — Springer Verlag. — 1983. — Р. 288–311. 4. Hock W., Schittkowski K. A Comparative Performance Evaluation of 27 Nonlinear Programming Codes // Computing. — 1983. — 30. — P. 335. 5. Schittkowski K. NLQPL: A FORTRAN-Subroutine Solving Constrained Nonlinear Programming Problems // Annals of Operations Research. 1985. — 5. — P. 485– 500. 6. Кірік О.Є. Розв’язання нелінійної задачі оптимального газорозподілу // Наук. вісті НТУУ «КПІ». — 2000. — № 5. — С. 30–34. 7. Кірік О.Є. Застосування модифікованого методу лінеаризації для розв’язання нелінійних задач розподілу потоків // Системні дослідження та інформаційні технології. — 2004. — № 3. — С. 40–49. 8. Пшеничный Б.Н., Данилин Ю.М. Численные методы в экстремальных зада- чах. — М.: Наука, 1975. — 319 с. 9. Пшеничный Б.Н. Метод линеаризации. — М.: Наука, 1983. — 136 с. 10. Sun J.,Yang X., Chen X. Quadratic cost flow and the conjugate gradient method // Eur. J. Oper. Res. — 2005. — 164, № 1. — P. 104–114. 11. Оре О. Графы и их применение. — М.: Мир, 1965. — 174 с. 12. Кирик Е.Е., Пшеничный Б.Н. Теория и методы расчета сетей // Обозрение при- кладной и промышленной математики. — М.: Науч. изд-во «ТВП», 1995. — Вып. 1. — С. 49–69. 13. Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи. — М.: Наука, 1980. — 320 с. 14. Кірік О.Є. Алгоритми лінеаризації та спряжених градієнтів для нелінійних задач розподілу потоків // Наук. вісті НТУУ «КПІ». — 2007. — № 3. — С. 67–73. Надійшла 13.12.2007 АЛГОРИТМИ ІТЕРАЦІЙНОГО КВАДРАТИЧНОГО ПРОГРАМУВАННЯ ДЛЯ ЗАДАЧ ОПТИМАЛЬНОГО РОЗПОДІЛУ ПОТОКІВ О.Є. Кірік ВСТУП МАТЕМАТИЧНА МОДЕЛЬ АЛГОРИТМИ ОПТИМІЗАЦІЇ ОБЧИСЛЮВАЛЬНІ АСПЕКТИ ВИСНОВКИ Рис. 1. Модельний приклад мережі: вузлові параметри — назва вузла, споживання у вузлі; дугові параметри — [нижня межа пропускної спроможності потоку < верхня межа пропускної спроможності потоку: довжина дуги ]: обчислена величина потоку Рис. 2. Табличне представлення мережі

Алгоритми ітераційного квадратичного програмування для задач оптимального розподілу потоків

Institution

Ähnliche Einträge