Konvexní optimalizace - Convex optimization

Tento článek má několik problémů. Prosím pomozte vylepši to nebo diskutovat o těchto problémech na internetu diskusní stránka. (Zjistěte, jak a kdy tyto zprávy ze šablony odebrat) tento článek může být pro většinu čtenářů příliš technická na to, aby je pochopili. Prosím pomozte to vylepšit na aby to bylo srozumitelné pro neodborníky, aniž by byly odstraněny technické podrobnosti. (červen 2013) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) Tento článek obsahuje seznam obecných Reference, ale zůstává z velké části neověřený, protože postrádá dostatečné odpovídající vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Únor 2012) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Konvexní optimalizace je podpole z matematická optimalizace který studuje problém minimalizace konvexní funkce přes konvexní sady. Mnoho tříd konvexních optimalizačních problémů připouští algoritmy polynomiálního času,^[1] zatímco matematická optimalizace je obecně NP-tvrdé.^[2][3][4]

Konvexní optimalizace má aplikace v široké škále oborů, jako je automatika řídicí systémy, odhad a zpracování signálu, komunikace a sítě, elektronické návrh obvodu,^[5] analýza a modelování dat, finance, statistika (optimální experimentální design ),^[6] a strukturální optimalizace, kde se koncept aproximace osvědčil jako efektivní.^[7][8] S nedávným pokrokem v oblasti výpočetní techniky a optimalizační algoritmy, konvexní programování je téměř stejně jednoduché jako lineární programování.^[9]

Definice

Konvexní problém s optimalizací je optimalizační problém ve kterém je objektivní funkce a konvexní funkce a proveditelná sada je konvexní sada. Funkce ${ displaystyle f}$ mapování některé podmnožiny ${ displaystyle mathbb {R} ^ {n}}$do ${ displaystyle mathbb {R} pohár { pm infty }}$ je konvexní, pokud je jeho doména konvexní a pro všechny ${ displaystyle theta v [0,1]}$ a všechno ${ displaystyle x, y}$ ve své doméně platí následující podmínka: ${ Displaystyle f ( theta x + (1- theta) y) leq theta f (x) + (1- theta) f (y)}$. Sada S je konvexní, pokud je pro všechny členy ${ displaystyle x, y v S}$ a všechno ${ displaystyle theta v [0,1]}$, máme to ${ displaystyle theta x + (1- theta) y v S}$.

Konkrétně je problém s konvexní optimalizací problém s nalezením nějaké ${ displaystyle mathbf {x ^ { ast}} v C}$ dosažení

${ displaystyle inf {f ( mathbf {x}): mathbf {x} v C }}$,

kde objektivní funkce ${ displaystyle f: { mathcal {D}} subseteq mathbb {R} ^ {n} do mathbb {R}}$ je konvexní, stejně jako proveditelná množina ${ displaystyle C}$.^[10][11] Pokud takový bod existuje, označuje se jako optimální bod nebo řešení; množina všech optimálních bodů se nazývá optimální sada. Li ${ displaystyle f}$ je neomezeně dole nad ${ displaystyle C}$ nebo není dosaženo infimum, pak se říká, že je problém s optimalizací neomezený. Jinak, pokud ${ displaystyle C}$ je prázdná množina, pak se říká, že je problém nemožné.^[12]

Standardní forma

Konvexní problém s optimalizací je v standardní forma pokud je psáno jako

${ displaystyle { begin {aligned} & { underset { mathbf {x}} { operatorname {minimalizovat}}} && f ( mathbf {x}) & operatorname {subject to} && g_ {i} ( mathbf {x}) leq 0, quad i = 1, dots, m &&& h_ {i} ( mathbf {x}) = 0, quad i = 1, dots, p, end {zarovnaný}}}$

kde ${ displaystyle mathbf {x} in mathbb {R} ^ {n}}$ je optimalizační proměnná, funkce ${ displaystyle f: { mathcal {D}} subseteq mathbb {R} ^ {n} do mathbb {R}}$ je konvexní, ${ displaystyle g_ {i}: mathbb {R} ^ {n} to mathbb {R}}$, ${ displaystyle i = 1, ldots, m}$, jsou konvexní a ${ displaystyle h_ {i}: mathbb {R} ^ {n} to mathbb {R}}$, ${ displaystyle i = 1, ldots, p}$, jsou afinní.^[12] Tento zápis popisuje problém hledání ${ displaystyle mathbf {x} in mathbb {R} ^ {n}}$ který minimalizuje ${ displaystyle f ( mathbf {x})}$ mezi všemi ${ displaystyle mathbf {x}}$ uspokojující ${ displaystyle g_ {i} ( mathbf {x}) leq 0}$, ${ displaystyle i = 1, ldots, m}$ a ${ displaystyle h_ {i} ( mathbf {x}) = 0}$, ${ displaystyle i = 1, ldots, p}$. Funkce ${ displaystyle f}$ je objektivní funkce problému a funkce ${ displaystyle g_ {i}}$ a ${ displaystyle h_ {i}}$ jsou omezující funkce.

Proveditelná sada ${ displaystyle C}$ optimalizačního problému se skládá ze všech bodů ${ displaystyle mathbf {x} v { mathcal {D}}}$ uspokojení omezení. Tato sada je konvexní, protože ${ displaystyle { mathcal {D}}}$ je konvexní, podúrovňové sady konvexních funkcí jsou konvexní, afinní množiny jsou konvexní a průnik konvexních množin je konvexní.^[13]

Řešení problému s konvexní optimalizací je jakékoli místo ${ displaystyle mathbf {x} v C}$ dosažení ${ displaystyle inf {f ( mathbf {x}): mathbf {x} v C }}$. Obecně může mít problém s konvexní optimalizací nula, jedno nebo mnoho řešení.

V této standardní formě lze ekvivalentně formulovat mnoho optimalizačních problémů. Například problém maximalizace a konkávní funkce ${ displaystyle f}$ lze znovu formulovat ekvivalentně jako problém minimalizace konvexní funkce ${ displaystyle -f}$. Problém maximalizace konkávní funkce přes konvexní množinu se běžně nazývá konvexní optimalizační problém.

Vlastnosti

Níže jsou uvedeny užitečné vlastnosti konvexních optimalizačních problémů:^[14][12]

• každý místní minimum je globální minimum;
• optimální množina je konvexní;
• pokud je objektivní funkce přísně konvexní, pak má problém nanejvýš jeden optimální bod.

Tyto výsledky využívá teorie konvexní minimalizace spolu s geometrickými představami z funkční analýza (v Hilbertových prostorech), jako je Hilbertova věta o projekci, teorém o dělení hyperplánu, a Farkasovo lemma.

Analýza nejistoty

Ben-Hain a Elishakoff^[15] (1990), Elishakoff et al.^[16] (1994) aplikovali konvexní analýzu na nejistota modelu.

Příklady

Následující třídy problémů jsou všechny konvexní optimalizační problémy, nebo je lze pomocí jednoduchých transformací snížit na konvexní optimalizační problémy:^[12][17]

Hierarchie konvexních optimalizačních problémů. (LP: lineární program, QP: kvadratický program, kuželový program druhého řádu SOCP, SDP: semidefinitní program, CP: kuželový program.)

• Nejmenší čtverce
• Lineární programování
• Konvexní kvadratická minimalizace s lineárními omezeními
• Kvadratická minimalizace s konvexními kvadratickými omezeními
• Kónická optimalizace
• Geometrické programování
• Programování kuželů druhého řádu
• Semidefinitní programování
• Maximalizace entropie s příslušnými omezeními

Lagrangeovy multiplikátory

Zvažte konvexní problém minimalizace daný ve standardní formě nákladovou funkcí ${ displaystyle f (x)}$ a omezení nerovnosti ${ displaystyle g_ {i} (x) leq 0}$ pro ${ displaystyle 1 leq i leq m}$. Pak doména ${ displaystyle { mathcal {X}}}$ je:

${ displaystyle { mathcal {X}} = vlevo {x v X vert g_ {1} (x), ldots, g_ {m} (x) leq 0 vpravo }.}$

Lagrangeova funkce problému je

${ displaystyle L (x, lambda _ {0}, lambda _ {1}, ldots, lambda _ {m}) = lambda _ {0} f (x) + lambda _ {1} g_ {1} (x) + cdots + lambda _ {m} g_ {m} (x).}$

Za každý bod ${ displaystyle x}$ v ${ displaystyle X}$ který minimalizuje ${ displaystyle f}$ přes ${ displaystyle X}$, existují reálná čísla ${ displaystyle lambda _ {0}, lambda _ {1}, ldots, lambda _ {m},}$ volala Lagrangeovy multiplikátory, které současně splňují tyto podmínky:

1. ${ displaystyle x}$ minimalizuje ${ displaystyle L (y, lambda _ {0}, lambda _ {1}, ldots, lambda _ {m})}$ nade vše ${ displaystyle y v X,}$
2. ${ displaystyle lambda _ {0}, lambda _ {1}, ldots, lambda _ {m} geq 0,}$ s alespoň jedním ${ displaystyle lambda _ {k}> 0,}$
3. ${ displaystyle lambda _ {1} g_ {1} (x) = cdots = lambda _ {m} g_ {m} (x) = 0}$ (doplňková ochablost).

Pokud existuje „přísně proveditelný bod“, tj. Bod ${ displaystyle z}$ uspokojující

${ displaystyle g_ {1} (z), ldots, g_ {m} (z) <0,}$

pak lze výše uvedené tvrzení posílit tak, aby to vyžadovalo ${ displaystyle lambda _ {0} = 1}$.

Naopak, pokud nějaké ${ displaystyle x}$ v ${ displaystyle X}$ vyhovuje (1) - (3) pro skaláry ${ displaystyle lambda _ {0}, ldots, lambda _ {m}}$ s ${ displaystyle lambda _ {0} = 1}$ pak ${ displaystyle x}$ je určitě minimalizovat ${ displaystyle f}$ přes ${ displaystyle X}$.

Algoritmy

Problémy s konvexní optimalizací lze vyřešit následujícími současnými metodami:^[18]

• Metody svazků (Wolfe, Lemaréchal, Kiwiel) a
• Subgradientní projekce metody (Polyak),
• Metody vnitřních bodů,^[1] které využívají souhlasný bariérové ​​funkce ^[19] a samoregulační bariérové ​​funkce.^[20]
• Metody roviny řezu
• Elipsoidní metoda
• Subgradientní metoda
• Duální podskupiny a metoda drift-plus-penalty

Subgradientní metody lze implementovat jednoduše, a proto jsou široce používány.^[21] Duální metody subgradientu jsou metody subgradientu aplikované na a dvojí problém. The drift-plus-trest metoda je podobná metodě duálního subgradientu, ale vyžaduje časový průměr primárních proměnných.

Rozšíření

Rozšíření konvexní optimalizace zahrnují optimalizaci bikonvexní, pseudo-konvexní, a kvazikonvexní funkce. Rozšíření teorie konvexní analýza a iterační metody pro přibližně řešení nekonvexních minimalizačních problémů se vyskytují v oblasti zobecněná konvexita, známá také jako abstraktní konvexní analýza.

Viz také

• Dualita
• Karush – Kuhn – Tuckerovy podmínky
• Problém s optimalizací
• Metoda proximálního gradientu

Poznámky

Reference

• Bertsekas, Dimitri P .; Nedic, Angelia; Ozdaglar, Asuman (2003). Konvexní analýza a optimalizace. Belmont, MA .: Athena Scientific. ISBN  978-1-886529-45-8.
• Bertsekas, Dimitri P. (2009). Konvexní teorie optimalizace. Belmont, MA .: Athena Scientific. ISBN  978-1-886529-31-1.
• Bertsekas, Dimitri P. (2015). Konvexní optimalizační algoritmy. Belmont, MA .: Athena Scientific. ISBN  978-1-886529-28-1.

• Boyd, Stephen P .; Vandenberghe, Lieven (2004). Konvexní optimalizace (PDF). Cambridge University Press. ISBN  978-0-521-83378-3. Citováno 15. října 2011.

• Borwein, Jonathane a Lewis, Adrian. (2000). Konvexní analýza a nelineární optimalizace. Springer.
• Christensen, Peter W .; Anders Klarbring (2008). Úvod do strukturální optimalizace. 153. Springer Science & Business Media. ISBN  9781402086663.

• Hiriart-Urruty, Jean-Baptiste a Lemaréchal, Claude. (2004). Základy konvexní analýzy. Berlín: Springer.
• Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). Konvexní algoritmy analýzy a minimalizace, svazek I: Základy. Grundlehren der Mathematischen Wissenschaften [Základní principy matematických věd]. 305. Berlín: Springer-Verlag. str. xviii + 417. ISBN  978-3-540-56850-6. PAN  1261420.
• Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). Konvexní algoritmy analýzy a minimalizace, svazek II: Pokročilá teorie a svazkové metody. Grundlehren der Mathematischen Wissenschaften [Základní principy matematických věd]. 306. Berlín: Springer-Verlag. str. xviii + 346. ISBN  978-3-540-56852-0. PAN  1295240.
• Kiwiel, Krzysztof C. (1985). Metody sestupu pro nediferencovatelnou optimalizaci. Přednášky z matematiky. New York: Springer-Verlag. ISBN  978-3-540-15642-0.
• Lemaréchal, Claude (2001). "Lagrangeova relaxace". V Michael Jünger a Denis Naddef (ed.). Výpočetní kombinatorická optimalizace: Příspěvky z jarní školy konané ve Schloß Dagstuhl, 15. – 19. Května 2000. Přednášky z informatiky. 2241. Berlín: Springer-Verlag. str. 112–156. doi:10.1007/3-540-45586-8_4. ISBN  978-3-540-42877-0. PAN  1900016. S2CID  9048698.
• Nesterov, Yurii; Nemirovskii, Arkadii (1994). Polynomické metody vnitřních bodů v konvexním programování. SIAM.
• Nesterov, Yurii. (2004). Úvodní přednášky o konvexní optimalizaci, Kluwer Academic Publishers
• Rockafellar, R. T. (1970). Konvexní analýza. Princeton: Princeton University Press.

• Ruszczyński, Andrzej (2006). Nelineární optimalizace. Princeton University Press.
• Schmit, L.A .; Fleury, C. 1980: Strukturální syntéza kombinací aproximačních konceptů a duálních metod. J. Amer. Inst. Vzduchoplavec. Astronaut 18, 1252-1260

externí odkazy

• EE364a: Konvexní optimalizace I a EE364b: Konvexní optimalizace II, Domovské stránky kurzu ve Stanfordu
• 6.253: Konvexní analýza a optimalizace, domovská stránka kurzu MIT OCW
• Brian Borchers, Přehled softwaru pro konvexní optimalizaci