Metoda vnitřního bodu - Interior-point method

Metody vnitřních bodů (označovaný také jako bariérové metody nebo IPM) jsou určitou třídou algoritmy které řeší lineární a nelineární konvexní optimalizace problémy.

Příklad řešení

John von Neumann^[1] navrhl metodu lineárního programování ve vnitřním bodě, která v praxi nebyla ani metodou polynomiálního času, ani efektivní metodou. Ve skutečnosti se ukázalo, že je pomalejší než běžně používané simplexní metoda.

Metoda vnitřního bodu byla objevena sovětským matematikem I. I. Dikinem v roce 1967 a znovu objevena v USA v polovině 19. let. Narendra Karmarkar vyvinuli metodu pro lineární programování volala Karmarkarův algoritmus, který běží v prokazatelně polynomiálním čase a je také velmi efektivní v praxi. Umožnila řešení problémů lineárního programování, která byla nad možnosti simplexové metody. Na rozdíl od simplexní metody dosáhne nejlepšího řešení projetím vnitřku proveditelný region. Metodu lze zobecnit na konvexní programování na základě a souhlasný bariérová funkce slouží ke kódování souboru konvexní sada.

Jakýkoli konvexní problém s optimalizací lze transformovat na minimalizaci (nebo maximalizaci) a lineární funkce přes konvexní množinu převedením na epigraf formulář.^[2] Myšlenka kódování proveditelná sada použití bariéry a návrh bariérových metod studoval Anthony V. Yurii Nesterov a Arkadi Nemirovski přišel se speciální třídou takových bariér, které lze použít ke kódování jakékoli konvexní sady. Zaručují, že počet iterace algoritmu je omezen polynomem v dimenzi a přesnosti řešení.^[3]

Karmarkarův průlom oživil studium metod vnitřních bodů a problémů s bariérou a ukázal, že je možné vytvořit algoritmus pro lineární programování charakterizovaný polynomiální složitost a navíc to bylo konkurenceschopné s simplexní metodou. Již Khachiyan je elipsoidní metoda byl algoritmus polynomiálního času; bylo to však příliš pomalé na to, aby nás to zajímalo.

Za nejúspěšnější je považována třída metod prvotních duálních cest sledujících vnitřní bod.Mehrotrův algoritmus prediktor-korektor poskytuje základ pro většinu implementací této třídy metod.^[4]

Metoda Primal-dual inside-point pro nelineární optimalizaci

Myšlenka metody primal-dual se dá snadno demonstrovat nelineární optimalizace Pro jednoduchost zvažte variantu nelineární optimalizační úlohy s all-nerovností:

minimalizovat

{ displaystyle f (x)}

podléhá

{ displaystyle c_ {i} (x) geq 0 ~ { text {pro}} ~ i = 1, ldots, m, ~ x in mathbb {R} ^ {n},}

kde

{ displaystyle f: mathbb {R} ^ {n} to mathbb {R}, c_ {i}: mathbb {R} ^ {n} rightarrow mathbb {R} quad (1).}

Logaritmický bariérová funkce spojené s (1) je

{ Displaystyle B (x, mu) = f (x) - mu suma _ {i = 1} ^ {m} log (c_ {i} (x)). quad (2)}

Tady ${ displaystyle mu}$ je malý kladný skalár, někdy nazývaný „bariérový parametr“. Tak jako ${ displaystyle mu}$ konverguje k nule minimum ${ displaystyle B (x, mu)}$ by měl konvergovat k řešení (1).

Bariérová funkce spád je

{ displaystyle g_ {b} = g- mu sum _ {i = 1} ^ {m} { frac {1} {c_ {i} (x)}} nabla c_ {i} (x), quad (3)}

kde ${ displaystyle g}$ je přechod původní funkce ${ displaystyle f (x)}$ , a ${ displaystyle nabla c_ {i}}$ je gradient ${ displaystyle c_ {i}}$ .

Kromě původní („primární“) proměnné ${ displaystyle x}$ představujeme a Lagrangeův multiplikátor inspirovaný dvojí proměnná ${ displaystyle lambda in mathbb {R} ^ {m}}$

{ displaystyle c_ {i} (x) lambda _ {i} = mu, forall i = 1, ldots, m. quad (4)}

(4) se někdy nazývá „narušená komplementarita“, protože se podobá „doplňkové nečinnosti“ v Podmínky KKT.

Snažíme se je najít ${ displaystyle (x _ { mu}, lambda _ { mu})}$ pro které je gradient bariérové funkce nulový.

Použitím (4) až (3) získáme rovnici pro přechod:

{ displaystyle g-A ^ {T} lambda = 0, quad (5)}

kde matice ${ displaystyle A}$ je Jacobian omezení ${ displaystyle c (x)}$ .

Intuice za (5) spočívá v přechodu ${ displaystyle f (x)}$ by měla ležet v podprostoru překlenutém přechody omezení. „Narušená komplementarita“ s malou ${ displaystyle mu}$ (4) lze chápat jako podmínku, že řešení by mělo buď ležet blízko hranice ${ displaystyle c_ {i} (x) = 0}$ , nebo že projekce přechodu ${ displaystyle g}$ na komponentě omezení ${ displaystyle c_ {i} (x)}$ normální by měla být téměř nula.

Přihlašování Newtonova metoda do (4) a (5), dostaneme rovnici pro ${ displaystyle (x, lambda)}$ Aktualizace ${ displaystyle (p_ {x}, p _ { lambda})}$ :

{ displaystyle { begin {pmatrix} W & -A ^ {T} Lambda A&C end {pmatrix}} { begin {pmatrix} p_ {x} p _ { lambda} end {pmatrix}} = { begin {pmatrix} -g + A ^ {T} lambda mu 1-C lambda end {pmatrix}},}

kde ${ displaystyle W}$ je Hesenská matice z ${ displaystyle B (x, mu)}$ , ${ displaystyle Lambda}$ je diagonální matice z ${ displaystyle lambda}$ , a ${ displaystyle C}$ je diagonální matice s ${ displaystyle C_ {ii} = c_ {i} (x)}$ .

Z důvodu (1), (4) podmínky

{ displaystyle lambda geq 0}

by mělo být prosazováno v každém kroku. Toho lze dosáhnout výběrem vhodného ${ displaystyle alpha}$ :

{ displaystyle (x, lambda) až (x + alpha p_ {x}, lambda + alpha p _ { lambda})}}

Přehrát média

Trajektorie iterací X pomocí metody vnitřního bodu.

Viz také

Reference

^ Dantzig, George B .; Thapa, Mukund N. (2003). Lineární programování 2: Teorie a rozšíření. Springer-Verlag.
^ Boyd, Stephen; Vandenberghe, Lieven (2004). Konvexní optimalizace. Cambridge: Cambridge University Press. str. 143. ISBN 978-0-521-83378-3. PAN 2061575.
^ Wright, Margaret H. (2004). „Revoluce vnitřních bodů v optimalizaci: historie, nedávný vývoj a trvalé důsledky“. Bulletin of the American Mathematical Society. 42: 39–57. doi:10.1090 / S0273-0979-04-01040-7. PAN 2115066.
^ Potra, Florian A .; Stephen J. Wright (2000). „Metody vnitřních bodů“. Journal of Computational and Applied Mathematics. 124 (1–2): 281–302. doi:10.1016 / S0377-0427 (00) 00433-7.

Bibliografie

Dikin, I.I. (1967). "Iterativní řešení problémů lineárního a kvadratického programování". Dokl. Akad. Nauk SSSR. 174 (1): 747–748.
Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude; Sagastizábal, Claudia A. (2006). Numerická optimalizace: Teoretické a praktické aspekty. Universitext (druhé přepracované vydání překladu z roku 1997, francouzské vydání). Berlín: Springer-Verlag. str. xiv + 490. doi:10.1007/978-3-540-35447-5. ISBN 978-3-540-35445-1. PAN 2265882.
Karmarkar, N. (1984). „Nový algoritmus polynomiálního času pro lineární programování“ (PDF). Sborník šestnáctého ročníku sympozia ACM o teorii práce s počítači - STOC '84. str. 302. doi:10.1145/800057.808695. ISBN 0-89791-133-4. Archivovány od originál (PDF) dne 28. prosince 2013.
Mehrotra, Sanjay (1992). „O implementaci metody Primal-Dual Interior Point“. SIAM Journal on Optimization. 2 (4): 575–601. doi:10.1137/0802028.
Nocedal, Jorge; Stephen Wright (1999). Numerická optimalizace. New York, NY: Springer. ISBN 978-0-387-98793-4.
Stiskněte, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). „Oddíl 10.11. Lineární programování: Metody vnitřních bodů“. Numerické recepty: Umění vědecké práce na počítači (3. vyd.). New York: Cambridge University Press. ISBN 978-0-521-88068-8.
Wright, Stephen (1997). Metody Primal-Dual Interior-Point. Philadelphia, PA: SIAM. ISBN 978-0-89871-382-4.
Boyd, Stephen; Vandenberghe, Lieven (2004). Konvexní optimalizace (PDF). Cambridge University Press.

[1] Dantzig, George B .; Thapa, Mukund N. (2003). Lineární programování 2: Teorie a rozšíření. Springer-Verlag.

[2] Boyd, Stephen; Vandenberghe, Lieven (2004). Konvexní optimalizace. Cambridge: Cambridge University Press. str. 143. ISBN 978-0-521-83378-3. PAN 2061575.

[3] Wright, Margaret H. (2004). „Revoluce vnitřních bodů v optimalizaci: historie, nedávný vývoj a trvalé důsledky“. Bulletin of the American Mathematical Society. 42: 39–57. doi:10.1090 / S0273-0979-04-01040-7. PAN 2115066.

[4] Potra, Florian A .; Stephen J. Wright (2000). „Metody vnitřních bodů“. Journal of Computational and Applied Mathematics. 124 (1–2): 281–302. doi:10.1016 / S0377-0427 (00) 00433-7.

[1]

[2]

[3]

[4]