www.wikidata.uk-ua.nina.az

Метод внутрішньої точки Методи внутрішніх точок їх також називають бар єрними методами або ІРМ це певний клас алгоритмів

Метод внутрішньої точки

Методи внутрішніх точок (їх також називають бар'єрними методами або ІРМ) — це певний клас алгоритмів, що вирішують задачі лінійної та нелінійної опуклої оптимізації.

Джон фон Нейман запропонував внутрішній точковий метод лінійного програмування, який не був ні методом поліноміального часу, ні ефективним методом на практиці. Насправді він виявився повільнішим, ніж широко використовуваний симплекс-метод. У 1984 р. Нарендра Кармаркар розробив метод лінійного програмування, який називається алгоритмом Кармаркара, який працює за поліноміальний час і також є дуже ефективним на практиці. Це дало змогу вирішити задачі лінійного програмування, що вийшли за межі можливостей симплексного методу. На відміну від симплексного методу, він досягає найкращого рішення шляхом обходу внутрішніх областей допустимих рішень. Метод може бути узагальнений до випуклого програмування на основі самокоректної бар'єрної функції, що використовується для кодування опуклого набору.

Будь-яка проблема оптимізації опуклості може бути перетворена на мінімізацію (або максимізацію) лінійної функції над опуклою множиною шляхом перетворення її у форму епіграфа. Ідея кодування множини допустимих ріщень за допомогою бар'єру та проектування бар'єрних методів була вивчена Антонієм В. Юрієм Нестеровим та Аркадієм Немировським, вони придумали особливий клас таких бар'єрів, який можна використовувати для кодування будь-якої опуклої множини. Вони гарантують, що кількість ітерацій алгоритму обмежена поліномом у розмірності та точності рішення.

Прорив Кармаркара активізував вивчення методів внутрішніх точок та бар'єрних проблем, показавши, що можна створити алгоритм лінійного програмування, який характеризується поліноміальною складністю і, крім того, конкурентоспроможним із симплексним методом. Вже еліпсоїдний метод Хачіяна був алгоритмом поліноміального часу; проте це було занадто повільно, щоб представляти практичний інтерес.

Клас первинних-подвійних методів, що слідують за внутрішніми точками, вважається найбільш успішним. Алгоритм прогнозування-коректор Мехротри дає основу для більшості реалізацій цього класу методів.

Первинний-подвійний метод внутрішньої точки для нелінійної оптимізації ред.

Ідея первинно-подвійного методу легко продемонструвати для обмеженої нелінійної оптимізації. Для простоти розглянемо варіант нерівності нелінійної задачі оптимізації:
мінімізувати функцію за умови де

Логарифмічна бар'єрна функція, пов'язана з (1),

Тут  — невеликий позитивний скаляр, який іноді називають «параметром бар'єру». Оскільки збігається до нуля, то мінімум повинен переходити до рішення (1).

Градієнт бар'єрної функції дорівнює

де  — градієнт вихідної функції , а  — градієнт .

На додаток до оригінальної («первинної») змінної ми вводимо подвійну змінну, натхненну множником Лагранжа

(4) іноді називають умовою «збуреної взаємодоповнюваності» за її схожість з «комплементарною слабкістю» в умовах KKT.

Ми намагаємося знайти ті , для яких градієнт бар'єрної функції дорівнює нулю.

Застосовуючи (4) до (3), отримуємо рівняння для градієнта:

де матриця  — якобіан обмежень .

Інтуїція позаду (5) полягає в тому, що градієнт повинен лежати в підпросторі, що охоплюється градієнтами обмежень. «Збурену взаємодоповнюваність» з малим (4) можна розуміти як умову, що рішення повинно лежати біля межі , або що проєкція градієнта на компонент обмеження нормально повинна бути майже нульовою.

Застосовуючи метод Ньютона до (4) і (5), ми отримуємо рівняння для оновлення :

Де матриця Гессея , є діагональною матрицею і is a diagonal matrix with

Через (1), (4) умова

повинна застосовуватися на кожному кроці. Це можна зробити, вибравши відповідне

Див. також ред.

Посилання ред.

  1. Dantzig, George (1963). Linear Programming and Extensions. doi:10.7249/r366. Процитовано 24 грудня 2019. 
  2. Boyd, Stephen; Vandenberghe, Lieven (8 березня 2004). Convex Optimization. Cambridge University Press. ISBN 978-0-521-83378-3. 
  3. Wright, Margaret H. (21 вересня 2004). The interior-point revolution in optimization: History, recent developments, and lasting consequences. Bulletin of the American Mathematical Society 42 (01). с. 39–57. ISSN 0273-0979. doi:10.1090/s0273-0979-04-01040-7. Процитовано 24 грудня 2019. 
  4. Potra, Florian A.; Wright, Stephen J. (2000-12). Interior-point methods. Journal of Computational and Applied Mathematics 124 (1-2). с. 281–302. ISSN 0377-0427. doi:10.1016/s0377-0427(00)00433-7. Процитовано 24 грудня 2019. 
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Metodi vnutrishnih tochok yih takozh nazivayut bar yernimi metodami abo IRM ce pevnij klas algoritmiv sho virishuyut zadachi linijnoyi ta nelinijnoyi opukloyi optimizaciyi Dzhon fon Nejman 1 zaproponuvav vnutrishnij tochkovij metod linijnogo programuvannya yakij ne buv ni metodom polinomialnogo chasu ni efektivnim metodom na praktici Naspravdi vin viyavivsya povilnishim nizh shiroko vikoristovuvanij simpleks metod U 1984 r Narendra Karmarkar rozrobiv metod linijnogo programuvannya yakij nazivayetsya algoritmom Karmarkara yakij pracyuye za polinomialnij chas i takozh ye duzhe efektivnim na praktici Ce dalo zmogu virishiti zadachi linijnogo programuvannya sho vijshli za mezhi mozhlivostej simpleksnogo metodu Na vidminu vid simpleksnogo metodu vin dosyagaye najkrashogo rishennya shlyahom obhodu vnutrishnih oblastej dopustimih rishen Metod mozhe buti uzagalnenij do vipuklogo programuvannya na osnovi samokorektnoyi bar yernoyi funkciyi sho vikoristovuyetsya dlya koduvannya opuklogo naboru Bud yaka problema optimizaciyi opuklosti mozhe buti peretvorena na minimizaciyu abo maksimizaciyu linijnoyi funkciyi nad opukloyu mnozhinoyu shlyahom peretvorennya yiyi u formu epigrafa 2 Ideya koduvannya mnozhini dopustimih rishen za dopomogoyu bar yeru ta proektuvannya bar yernih metodiv bula vivchena Antoniyem V Yuriyem Nesterovim ta Arkadiyem Nemirovskim voni pridumali osoblivij klas takih bar yeriv yakij mozhna vikoristovuvati dlya koduvannya bud yakoyi opukloyi mnozhini Voni garantuyut sho kilkist iteracij algoritmu obmezhena polinomom u rozmirnosti ta tochnosti rishennya 3 Proriv Karmarkara aktivizuvav vivchennya metodiv vnutrishnih tochok ta bar yernih problem pokazavshi sho mozhna stvoriti algoritm linijnogo programuvannya yakij harakterizuyetsya polinomialnoyu skladnistyu i krim togo konkurentospromozhnim iz simpleksnim metodom Vzhe elipsoyidnij metod Hachiyana buv algoritmom polinomialnogo chasu prote ce bulo zanadto povilno shob predstavlyati praktichnij interes Klas pervinnih podvijnih metodiv sho sliduyut za vnutrishnimi tochkami vvazhayetsya najbilsh uspishnim Algoritm prognozuvannya korektor Mehrotri daye osnovu dlya bilshosti realizacij cogo klasu metodiv 4 Pervinnij podvijnij metod vnutrishnoyi tochki dlya nelinijnoyi optimizaciyi red Ideya pervinno podvijnogo metodu legko prodemonstruvati dlya obmezhenoyi nelinijnoyi optimizaciyi Dlya prostoti rozglyanemo variant nerivnosti nelinijnoyi zadachi optimizaciyi minimizuvati funkciyu f x displaystyle displaystyle f x nbsp za umovi c i x 0 for i 1 m x R n displaystyle displaystyle c i x geq 0 text for i 1 ldots m x in mathbb R n nbsp def R n R c i R n R 1 displaystyle displaystyle f mathbb R n to mathbb R c i mathbb R n rightarrow mathbb R quad 1 nbsp Logarifmichna bar yerna funkciya pov yazana z 1 B x m f x m i 1 m log c i x 2 displaystyle displaystyle B x mu f x mu sum i 1 m log c i x quad 2 nbsp Tut m displaystyle mu nbsp nevelikij pozitivnij skalyar yakij inodi nazivayut parametrom bar yeru Oskilki m displaystyle mu nbsp zbigayetsya do nulya to minimum B x m displaystyle displaystyle B x mu nbsp povinen perehoditi do rishennya 1 Gradiyent bar yernoyi funkciyi dorivnyuyeg b g m i 1 m 1 c i x c i x 3 displaystyle displaystyle g b g mu sum i 1 m frac 1 c i x nabla c i x quad 3 nbsp de g displaystyle g nbsp gradiyent vihidnoyi funkciyi f x displaystyle f x nbsp a c i displaystyle nabla c i nbsp gradiyent c i displaystyle c i nbsp Na dodatok do originalnoyi pervinnoyi zminnoyi x displaystyle x nbsp mi vvodimo podvijnu zminnu nathnennu mnozhnikom Lagranzhal R m displaystyle displaystyle lambda in mathbb R m nbsp c i x l i m i 1 m 4 displaystyle displaystyle c i x lambda i mu forall i 1 ldots m quad 4 nbsp 4 inodi nazivayut umovoyu zburenoyi vzayemodopovnyuvanosti za yiyi shozhist z komplementarnoyu slabkistyu v umovah KKT Mi namagayemosya znajti ti x m l m displaystyle displaystyle x mu lambda mu nbsp dlya yakih gradiyent bar yernoyi funkciyi dorivnyuye nulyu Zastosovuyuchi 4 do 3 otrimuyemo rivnyannya dlya gradiyenta g A T l 0 5 displaystyle displaystyle g A T lambda 0 quad 5 nbsp de matricya A displaystyle A nbsp yakobian obmezhen c x displaystyle c x nbsp Intuyiciya pozadu 5 polyagaye v tomu sho gradiyent f x displaystyle f x nbsp povinen lezhati v pidprostori sho ohoplyuyetsya gradiyentami obmezhen Zburenu vzayemodopovnyuvanist z malim m displaystyle mu nbsp 4 mozhna rozumiti yak umovu sho rishennya povinno lezhati bilya mezhi c i x 0 displaystyle displaystyle c i x 0 nbsp abo sho proyekciya gradiyenta g displaystyle g nbsp na komponent obmezhennya c i x displaystyle displaystyle c i x nbsp normalno povinna buti majzhe nulovoyu Zastosovuyuchi metod Nyutona do 4 i 5 mi otrimuyemo rivnyannya x l displaystyle x lambda nbsp dlya onovlennya p x p l displaystyle displaystyle p x p lambda nbsp W A T L A C p x p l g A T l m 1 C l displaystyle displaystyle begin pmatrix W amp A T Lambda A amp C end pmatrix begin pmatrix p x p lambda end pmatrix begin pmatrix g A T lambda mu 1 C lambda end pmatrix nbsp De W displaystyle W nbsp matricya Gesseya B x m displaystyle displaystyle B x mu nbsp L displaystyle displaystyle Lambda nbsp ye diagonalnoyu matriceyu l displaystyle displaystyle lambda nbsp i C displaystyle C nbsp is a diagonal matrix with C i i c i x displaystyle displaystyle C ii c i x nbsp Cherez 1 4 umoval 0 displaystyle lambda geq 0 nbsp povinna zastosovuvatisya na kozhnomu kroci Ce mozhna zrobiti vibravshi vidpovidne a displaystyle alpha nbsp x l x a p x l a p l displaystyle displaystyle x lambda to x alpha p x lambda alpha p lambda nbsp Div takozh red Umovi Karusha Kuna TakeraPosilannya red Dantzig George 1963 Linear Programming and Extensions doi 10 7249 r366 Procitovano 24 grudnya 2019 Boyd Stephen Vandenberghe Lieven 8 bereznya 2004 Convex Optimization Cambridge University Press ISBN 978 0 521 83378 3 Wright Margaret H 21 veresnya 2004 The interior point revolution in optimization History recent developments and lasting consequences Bulletin of the American Mathematical Society 42 01 s 39 57 ISSN 0273 0979 doi 10 1090 s0273 0979 04 01040 7 Procitovano 24 grudnya 2019 Potra Florian A Wright Stephen J 2000 12 Interior point methods Journal of Computational and Applied Mathematics 124 1 2 s 281 302 ISSN 0377 0427 doi 10 1016 s0377 0427 00 00433 7 Procitovano 24 grudnya 2019 Otrimano z https uk wikipedia org w index php title Metod vnutrishnoyi tochki amp oldid 39595645