Konvex programmering

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 21 november 2021; kontroller kräver 2 redigeringar .

Konvex programmering är ett underområde av matematisk optimering som studerar problemet med att minimera konvexa funktioner på konvexa mängder . Medan många klasser av konvexa programmeringsproblem tillåter polynom-tidsalgoritmer [1] , är matematisk optimering i allmänhet NP-hård [2] [3] [4] .

Konvex programmering har applikationer inom en rad discipliner såsom automatiska styrsystem , signalutvärdering och bearbetning , kommunikation och nätverk, kretsar [5] , dataanalys och modellering, ekonomi , statistik ( optimal experimentdesign ) [6] och strukturell optimering [7] . Utvecklingen av datorteknik och optimeringsalgoritmer har gjort konvex programmering nästan lika enkel som linjär programmering [8] .

Definition

Ett konvext programmeringsproblem är ett optimeringsproblem där objektivfunktionen är en konvex funktion och domänen av möjliga lösningar är konvex . En funktion som mappar en delmängd till är konvex om domänen är konvex för både alla och alla i deras domän av . En mängd är konvex om för alla dess element och någon av dem också tillhör mängden. $f$ $\mathbb {R} ^{n}$ ${\displaystyle \mathbb {R} \cup \{\pm \infty \))$ $\theta \in [0,1]$ $x,y$ $f(\theta x+(1-\theta )y)\leqslant \theta f(x)+(1-\theta )f(y)$ $x,y$ $\theta \in [0,1]$ $\theta x+(1-\theta )y$

I synnerhet är problemet med konvex programmering problemet med att hitta några , på vilka $\mathbf {x^{\ast }} \in C$

{\displaystyle \inf\{f(\mathbf {x} ):\mathbf {x} \in C\))

där den objektiva funktionen är konvex, liksom uppsättningen av genomförbara lösningar [9] [10] . Om en sådan punkt finns kallas den för den optimala punkten . Mängden av alla optimala punkter kallas den optimala mängden . Om obegränsad av eller infimum inte uppnås, sägs optimeringen vara obegränsad . Om den är tom talar man om en oacceptabel uppgift [11] . $f$ $C$ $f$ $C$ $C$

Standardformulär

Ett konvext programmeringsproblem sägs vara i standardform om det skrivs som

Minimera

f(\mathbf {x} )

Under förhållanden

{\begin{aligned}&&g_{i}(\mathbf {x} )\leqslant 0,\quad i=1,\dots ,m\\&&h_{i}(\mathbf {x} )=0, \quad i=1,\dots ,p,\end{aligned}}

där är optimeringsvariabeln, funktionerna är konvexa och funktionerna är affina [11] . $x \in \mathbb{R}^n$ ${\displaystyle f,g_{1},\ldots ,g_{m))$ ${\displaystyle h_{1},\ldots ,h_{p))$

I dessa termer är funktionen den objektiva funktionen av problemet, och funktionerna och kallas begränsningsfunktioner. Den tillåtna uppsättningen av lösningar på optimeringsproblemet är den uppsättning som består av alla punkter som uppfyller villkoren och . Denna mängd är konvex eftersom subnivåmängder av en konvex funktion är konvexa, affina mängder är också konvexa och skärningspunkten mellan konvexa mängder är en konvex mängd [12] . $f$ $g_i$ $Hej}$ $x \in \mathbb{R}^n$ $g_{1}(x)\leqslant 0,\ldots ,g_{m}(x)\leqslant 0$ $h_{1}(x)=0,\ldots ,h_{p}(x)=0$

Många optimeringsproblem kan reduceras till denna standardform. Till exempel kan problemet med att maximera en konkav funktion omformuleras på samma sätt som problemet med att minimera en konvex funktion , så att problemet med att maximera en konkav funktion på en konvex uppsättning ofta hänvisas till som ett konvext programmeringsproblem $f$ $-f$

Egenskaper

Användbara egenskaper för konvexa programmeringsproblem [13] [11] :

varje lokalt minimum är ett globalt minimum ;
den optimala uppsättningen är konvex;
om den objektiva funktionen är starkt konvex har problemet högst en optimal punkt.

Dessa resultat används i konvex minimeringsteori, tillsammans med geometriska begrepp från funktionsanalys (på Hilbert-utrymmen ), som Hilberts projektionssats , stödhyperplansatsen och Farkas lemma .

Exempel

Följande klasser av problem är konvexa programmeringsproblem eller kan reduceras till konvexa programmeringsproblem genom enkla transformationer [11] [14] :

Minsta kvadratiska metod
Linjär programmering
Konvex kvadratisk optimering med linjära begränsningar
Kvadratisk programmering i kvadratiska begränsningar
Konisk optimering
Geometrisk programmering
Konisk programmering på en andra ordningens kon
Semi-Definite Programmering
Entropimaximumprincip med lämpliga begränsningar

Metod för Lagrange-multiplikatorer

Betrakta ett konvext minimeringsproblem givet i standardform med en kostnadsfunktion och ojämlikhetsbegränsningar för . Då är definitionsdomänen : $f(x)$ $g_{i}(x)\leqslant 0$ $1\leqslant i\leqslant m$ ${\mathcal {X}}$

{\mathcal {X}}=\left\{x\in X\vert g_{1}(x),\ldots ,g_{m}(x)\leqslant 0\right\}.

Lagrange funktion för problemet

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

För vilken punkt som helst från den minimeras till , finns det reella tal , kallade Lagrange-multiplikatorer , för vilka följande villkor är uppfyllda samtidigt: $x$ $X$ $f$ $X$ $\lambda _{0},\lambda _{1},\ldots ,\lambda _{m},$

$x$ minimerar över allt $L(y,\lambda _{0},\lambda _{1},\ldots ,\lambda _{m})$ $y\in X,$
$\lambda _{0},\lambda _{1},\ldots ,\lambda _{m}\geqslant 0,$ med minst en $\lambda _{k}>0,$
$\lambda _{1}g_{1}(x)=\cdots =\lambda _{m}g_{m}(x)=0$ (kompletterande icke-stelhet).

Om det finns en "stark godtagbar punkt", det vill säga en tillfredsställande punkt $z$

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

då kan påståendet ovan förstärkas till att kräva . $\lambda _{0}=1$

Omvänt, om några av uppfyller villkoren (1)-(3) för skalärer med , så minimeras det definitivt på . $x$ $X$ ${\displaystyle \lambda _{0},\ldots ,\lambda _{m))$ $\lambda _{0}=1$ $x$ $f$ $X$

Algoritmer

Konvexa programmeringsproblem löses med följande moderna metoder: [15]

Subgradient beam methods } (Wolf, Lemerical, Kivel),
Subgradientprojektionsmetoder (Polyak),
Inre punktmetod [1] med självständiga barriärfunktioner [16] och självregelbundna barriärfunktioner [17] .
Skärplansmetod
Ellipsoid metod
Subgradientmetoder
Driftundergradienter och drift+straffmetoden

Sub-gradientmetoder kan implementeras helt enkelt för att de används i stor utsträckning [18] [19] . Dubbla subgradientmetoder är subgradientmetoder som tillämpas på ett dubbelt problem . Drift+penalty-metoden liknar den dubbla subgradientmetoden, men använder tidsgenomsnittet för huvudvariablerna.

Tillägg

Tillägg till konvex programmering inkluderar optimeringar för bikonvexa , pseudokonvexa och kvasikonvexa funktioner. Utvidgningar av teorin om konvex analys och iterativa metoder för den ungefärliga lösningen av icke-konvexa optimeringsproblem förekommer inom området för generaliserad konvexitet , känd som abstrakt konvex analys.

Se även

Anteckningar

↑ 1 2 Nesterov och Nemirovskii, 1994 .
↑ Murty och Kabadi 1987 , sid. 117–129.
↑ Sahni, 1974 , sid. 262-279.
↑ Pardalos och Vavasis, 1991 , sid. 15-22.
↑ Boyd och Vandenberghe 2004 , sid. 17.
↑ Christensen, Klarbring, 2008 , sid. kap. fyra.
↑ Boyd, Vandenberghe, 2004 .
↑ Boyd och Vandenberghe 2004 , sid. åtta.
↑ Hiriart-Urruty, Lemaréchal, 1996 , sid. 291.
↑ Ben-Tal, Nemirovskiĭ, 2001 , sid. 335–336.
↑ 1 2 3 4 Boyd, Vandenberghe, 2004 , sid. kap. fyra.
↑ Boyd och Vandenberghe 2004 , sid. kap. 2.
↑ Rockafellar, 1993 , sid. 183–238.
↑ Agrawal, Verschueren, Diamond, Boyd, 2018 , sid. 42–60.
↑ För metoder för konvex programmering, se böcker av Irriart-Urruti och Lemerical (flera böcker) och böcker av Rushczynski, Bercekas och Boyd och Vanderberge (inre punktmetoder).
↑ Nesterov, Nemirovskii, 1995 .
↑ Peng, Roos, Terlaky, 2002 , sid. 129–171.
↑ Bertsekas, 2009 .
↑ Bertsekas, 2015 .

Litteratur

Jean-Baptiste Hiriart-Urruty, Claude Lemarechal. Konvex analys och minimeringsalgoritmer: Grundläggande . - 1996. - ISBN 9783540568506 .
Aharon Ben-Tal, Arkadi Semenovich Nemirovskiĭ. Föreläsningar om modern konvex optimering: analys, algoritmer och tekniska tillämpningar . - 2001. - ISBN 9780898714913 .
Katta Murty, Santosh Kabadi. Några NP-kompletta problem i kvadratisk och olinjär programmering // Matematisk programmering. - 1987. - T. 39 , nr. 2 . — s. 117–129 . - doi : 10.1007/BF02592948 .
Sahni S. Beräkningsrelaterade problem // SIAM Journal on Computing. - 1974. - Utgåva. 3 .
Panos M. Pardalos, Stephen A. Vavasis. Kvadratisk programmering med ett negativt egenvärde är NP-hård // Journal of Global Optimization. - 1991. - T. 1 , nr 1 .
R. Tyrrell Rockafellar. Konvex analys . — Princeton: Princeton University Press, 1970.
R. Tyrrell Rockafellar. Lagrange multiplikatorer och optimalitet // SIAM Review. - 1993. - T. 35 , nr. 2 . - doi : 10.1137/1035044 .
Akshay Agrawal, Robin Verschueren, Steven Diamond, Stephen Boyd. Ett omskrivningssystem för konvexa optimeringsproblem // Kontroll och beslut. - 2018. - V. 5 , nr. 1 . - doi : 10.1080/23307706.2017.1397554 .
Yurii Nesterov, Arkadii Nemirovskii. Interiörpunktspolynomalgoritmer i konvex programmering. - Society for Industrial and Applied Mathematics, 1995. - ISBN 978-0898715156 .
Yurii Nesterov, Arkadii Nemirovskii. Inre punktpolynommetoder i konvex programmering. - SIAM, 1994. - V. 13. - (Studier i tillämpad och numerisk matematik). - ISBN 978-0-89871-319-0 .
Jurij Nesterov. Inledande föreläsningar om konvex optimering. - Boston, Dordrecht, London: Kluwer Academic Publishers, 2004. - T. 87. - (Applied Optimization). — ISBN 1-4020-7553-7 .
Jiming Peng, Cornelis Roos, Tamás Terlaky. Självreguljära funktioner och nya sökriktningar för linjär och semidefinitiv optimering // Matematisk programmering. - 2002. - T. 93 , nr. 1 . — ISSN 0025-5610 . - doi : 10.1007/s101070200296 .
Dimitri P. Bertsekas, Angelia Nedic, Asuman Ozdaglar. Konvex analys och optimering. - Athena Scientific, 2003. - ISBN 978-1-886529-45-8 .
Dimitri P. Bertsekas. Konvex optimeringsteori. - Belmont, MA.: Athena Scientific, 2009. - ISBN 978-1-886529-31-1 .
Dimitri P. Bertsekas. Konvexa optimeringsalgoritmer. - Belmont, MA.: Athena Scientific, 2015. - ISBN 978-1-886529-28-1 .
Stephen P. Boyd, Lieven Vandenberghe. Konvex optimering . - Cambridge University Press, 2004. - ISBN 978-0-521-83378-3 .
Jonathan M. Borwein, Adrian Lewis. Konvex analys och icke-linjär optimering. - Springer, 2000. - (CMS Books in Mathematics). — ISBN 0-387-29570-4 .
Peter W. Christensen, Anders Klarbring. En introduktion till strukturell optimering. - Springer Science & Business Media, 2008. - V. 153. - ISBN 9781402086663 .
Jean-Baptiste Hiriart-Urruty, Claude Lemarechal. Grunderna i konvex analys. - Berlin: Springer, 2004. - (Grundlehren textutgåvor). - ISBN 978-3-540-42205-1 .
Jean-Baptiste Hiriart-Urruty, Claude Lemarechal. Konvex analys och minimeringsalgoritmer, Volym I: Fundamentals. - Berlin: Springer-Verlag, 1993. - T. 305. - S. xviii + 417. - ISBN 978-3-540-56850-6 .
Jean-Baptiste Hiriart-Urruty, Claude Lemarechal. Konvex analys och minimeringsalgoritmer, Volym II: Avancerad teori och buntmetoder. - Berlin: Springer-Verlag, 1993. - T. 306. - S. xviii + 346. — ISBN 978-3-540-56852-0 .
Krzysztof C. Kiwiel. Nedstigningsmetoder för icke-differentierbar optimering. - New York: Springer-Verlag, 1985. - (Lecture Notes in Mathematics). — ISBN 978-3-540-15642-0 .
Claude Lemarechal. Lagrangian relaxation // Computational combinatorial optimization: Papers from the Spring School som hölls i Schloß Dagstuhl, 15–19 maj 2000. - Berlin: Springer-Verlag, 2001. - Vol. 2241. - S. 112-156. — ISBN 978-3-540-42877-0 . - doi : 10.1007/3-540-45586-8_4 .
Andrzej Ruszczyński. icke-linjär optimering. — Princeton University Press, 2006.
Eremin I. I. , Astafiev N. N. Introduktion till teorin om linjär och konvex programmering. - M. , Nauka , 1976. - 189 sid.
Kamenev GK Optimala adaptiva metoder för polyedrisk approximation av konvexa kroppar. M.: VTs RAN, 2007, 230 sid. ISBN 5-201-09876-2 .
Kamenev GK Numerisk studie av effektiviteten av metoder för polyedrisk approximation av konvexa kroppar. M: Ed. CC RAS, 2010, 118s. ISBN 978-5-91601-043-5 .

Länkar

Stephen Boyd, Lieven Vandenberghe, Konvex optimering (pdf)
EE364a: Convex Optimization I , EE364b: Convex Optimization II , Oxford University kurssida
6.253: Konvex analys och optimering , MIT OCW kurssida
Brian Borchers, En översikt över programvara för konvex optimering

Optimeringsmetoder _
En-dimensionell	gyllene snittmetoden Dikotomi Parabolmetoden Rutnätssökning Enhetlig blocksökningsmetod Fibonacci-metoden Ternär sökning Piyavsky-metoden Strongin metod
Noll ordning	Gauss metod Nelder-Mead metod Hook-Jeeves metod Rosenbrock-metoden Powells metod
Första beställning	lutning nedstigning Zeutendijk-metoden Koordinera nedstigning Konjugerad gradientmetod Kvasi-newtonska metoder Levenberg-Marquardts algoritm
andra beställning	Newtons metod Newton-Raphson-metoden Broyden-Fletcher-Goldfarb-Shanno-algoritm (BFGS)
Stokastisk	Monte Carlo metoden Simulerad glödgning Evolutionära algoritmer differentiell evolution Myralgoritm Partikelsvärmmetod Algoritm för bikoloni Random walk-metod
Linjära programmeringsmetoder _	Enkel metod Gomoris algoritm Ellipsoid metod Potentiell metod
Icke -linjära programmeringsmetoder	Sekventiell kvadratisk programmering