Konveks programmering

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 21. november 2021; checks kræver 2 redigeringer .

Konveks programmering er et underområde af matematisk optimering , der studerer problemet med at minimere konvekse funktioner på konvekse sæt . Mens mange klasser af konvekse programmeringsproblemer tillader polynomiske tidsalgoritmer [1] , er matematisk optimering generelt NP-hård [2] [3] [4] .

Konveks programmering har applikationer inden for en række discipliner såsom automatiske kontrolsystemer , signalevaluering og -behandling , kommunikation og netværk, kredsløb [5] , dataanalyse og modellering, finans , statistik ( optimalt eksperimentdesign ) [6] og strukturel optimering [7] . Udviklingen af computerteknologi og optimeringsalgoritmer har gjort konveks programmering næsten lige så enkel som lineær programmering [8] .

Definition

Et konveks programmeringsproblem er et optimeringsproblem , hvor objektivfunktionen er en konveks funktion, og domænet af mulige løsninger er konveks . En funktion , der knytter en delmængde til , er konveks, hvis domænet er konveks for både alle og alle i deres domæne af . Et sæt er konveks, hvis for alle dets elementer, og ethvert af dem også hører til sættet. $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$

Især problemet med konveks programmering er problemet med at finde nogle , hvorpå $\mathbf {x^{\ast }} \in C$

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

hvor den objektive funktion er konveks, ligesom sættet af mulige løsninger er [9] [10] . Hvis et sådant punkt eksisterer, kaldes det det optimale punkt . Sættet af alle optimale punkter kaldes det optimale sæt . Hvis unbounded af eller infimum ikke nås, siges optimeringen at være unbounded . Hvis den er tom, taler man om en uacceptabel opgave [11] . $f$ $C$ $f$ $C$ $C$

Standardformular

Et konveks programmeringsproblem siges at være i standardform, hvis det skrives som

Minimer

f(\mathbf {x} )

Under forhold

{\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}}

hvor er optimeringsvariablen, funktionerne er konvekse, og funktionerne er affine [11] . $x \in \mathbb{R}^n$ ${\displaystyle f,g_{1},\ldots ,g_{m))$ ${\displaystyle h_{1},\ldots ,h_{p))$

I disse termer er funktionen den objektive funktion af problemet, og funktionerne og kaldes begrænsningsfunktioner. Det tilladte sæt af løsninger på optimeringsproblemet er det sæt, der består af alle punkter, der opfylder betingelserne og . Dette sæt er konveks, fordi subniveausæt af en konveks funktion er konvekse, affine mængder er også konvekse, og skæringspunktet mellem konvekse mængder er et konveks sæt [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$

Mange optimeringsproblemer kan reduceres til denne standardform. For eksempel kan problemet med at maksimere en konkav funktion omformuleres på samme måde som problemet med at minimere en konveks funktion , således at problemet med at maksimere en konkav funktion på et konveks sæt ofte omtales som et konveks programmeringsproblem $f$ $-f$

Egenskaber

Nyttige egenskaber ved konvekse programmeringsproblemer [13] [11] :

ethvert lokalt minimum er et globalt minimum ;
det optimale sæt er konveks;
hvis den objektive funktion er stærkt konveks, har problemet højst et optimalt punkt.

Disse resultater bruges i konveks minimeringsteori sammen med geometriske begreber fra funktionel analyse (på Hilbert-rum ), såsom Hilberts projektionssætning , støttehyperplansætningen og Farkas' lemma .

Eksempler

Følgende klasser af problemer er konvekse programmeringsproblemer eller kan reduceres til konvekse programmeringsproblemer ved simple transformationer [11] [14] :

Mindste kvadratisk metode
Lineær programmering
Konveks kvadratisk optimering med lineære begrænsninger
Kvadratisk programmering i kvadratiske begrænsninger
Konisk optimering
Geometrisk programmering
Konisk programmering på en andenordens kegle
Semi-Definite Programmering
Entropi maksimum princip med passende restriktioner

Metode til Lagrange-multiplikatorer

Overvej et konveks minimeringsproblem givet i standardform med en omkostningsfunktion og ulighedsbegrænsninger for . Så er definitionsdomænet : $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 til 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).

For ethvert punkt fra det minimerer til , er der reelle tal , kaldet Lagrange-multiplikatorer , for hvilke følgende betingelser er opfyldt samtidigt: $x$ $x$ $f$ $x$ $\lambda _{0},\lambda _{1},\ldots ,\lambda _{m},$

$x$ minimerer over alt $L(y,\lambda _{0},\lambda _{1},\ldots ,\lambda _{m})$ $y\in X,$
$\lambda _{0},\lambda _{1},\ldots ,\lambda _{m}\geqslant 0,$ med mindst én $\lambda _{k}>0,$
$\lambda _{1}g_{1}(x)=\cdots =\lambda _{m}g_{m}(x)=0$ (komplementær ikke-stivhed).

Hvis der findes et "stærkt acceptabelt punkt", det vil sige et punkt, der opfylder $z$

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

så kan ovenstående udsagn styrkes til at kræve . $\lambda _{0}=1$

Omvendt, hvis nogle af opfylder betingelserne (1)-(3) for skalarer med , så minimerer det bestemt på . $x$ $x$ ${\displaystyle \lambda _{0},\ldots ,\lambda _{m))$ $\lambda _{0}=1$ $x$ $f$ $x$

Algoritmer

Konvekse programmeringsproblemer løses ved følgende moderne metoder: [15]

Subgradientstrålemetoder } (Wolf, Lemerical, Kivel),
Subgradientprojektionsmetoder (Polyak),
Indvendig punktmetode [1] ved hjælp af selvkonsistente barrierefunktioner [16] og selvregulære barrierefunktioner [17] .
Skæreplan metode
Ellipsoid metode
Undergradientmetoder
Driftsundergradienter og drift+strafmetoden

Sub-gradient metoder kan implementeres simpelthen fordi de er meget udbredte [18] [19] . Dual subgradient metoder er subgradient metoder anvendt på et dobbelt problem . Drift+penalty-metoden ligner den dobbelte subgradient-metoden, men bruger tidsgennemsnittet af hovedvariablerne.

Udvidelser

Udvidelser til konveks programmering omfatter optimeringer for bikonvekse , pseudokonvekse og kvasikonvekse funktioner. Udvidelser til teorien om konveks analyse og iterative metoder til den omtrentlige løsning af ikke-konvekse optimeringsproblemer forekommer inden for området generaliseret konveksitet , kendt som abstrakt konveks analyse.

Se også

Noter

↑ 1 2 Nesterov og Nemirovskii, 1994 .
↑ Murty og Kabadi 1987 , s. 117-129.
↑ Sahni, 1974 , s. 262-279.
↑ Pardalos og Vavasis, 1991 , s. 15-22.
↑ Boyd og Vandenberghe 2004 , s. 17.
↑ Christensen, Klarbring, 2008 , s. chpt. fire.
↑ Boyd, Vandenberghe, 2004 .
↑ Boyd og Vandenberghe 2004 , s. otte.
↑ Hiriart-Urruty, Lemaréchal, 1996 , s. 291.
↑ Ben-Tal, Nemirovskiĭ, 2001 , s. 335-336.
↑ 1 2 3 4 Boyd, Vandenberghe, 2004 , s. chpt. fire.
↑ Boyd og Vandenberghe 2004 , s. chpt. 2.
↑ Rockafellar, 1993 , s. 183-238.
↑ Agrawal, Verschueren, Diamond, Boyd, 2018 , s. 42-60.
↑ For metoder til konveks programmering, se bøger af Irriart-Urruti og Lemerical (flere bøger) og bøger af Rushczynski, Bercekas og Boyd og Vanderberge (indre punktmetoder).
↑ Nesterov, Nemirovskii, 1995 .
↑ Peng, Roos, Terlaky, 2002 , s. 129-171.
↑ Bertsekas, 2009 .
↑ Bertsekas, 2015 .

Litteratur

Jean-Baptiste Hiriart-Urruty, Claude Lemarechal. Konvekse analyse- og minimeringsalgoritmer: Grundlæggende . - 1996. - ISBN 9783540568506 .
Aharon Ben-Tal, Arkadi Semenovich Nemirovskiĭ. Foredrag om moderne konveks optimering: analyse, algoritmer og tekniske applikationer . - 2001. - ISBN 9780898714913 .
Katta Murty, Santosh Kabadi. Nogle NP-komplette problemer i kvadratisk og ikke-lineær programmering // Matematisk programmering. - 1987. - T. 39 , no. 2 . — s. 117–129 . - doi : 10.1007/BF02592948 .
Sahni S. Beregningsrelaterede problemer // SIAM Journal on Computing. - 1974. - Udgave. 3 .
Panos M. Pardalos, Stephen A. Vavasis. Kvadratisk programmering med én negativ egenværdi er NP-hård // Journal of Global Optimization. - 1991. - T. 1 , nr. 1 .
R. Tyrrell Rockafellar. Konveks analyse . — Princeton: Princeton University Press, 1970.
R. Tyrrell Rockafellar. Lagrange multiplikatorer og optimalitet // SIAM Review. - 1993. - T. 35 , no. 2 . - doi : 10.1137/1035044 .
Akshay Agrawal, Robin Verschueren, Steven Diamond, Stephen Boyd. Et omskrivningssystem til konvekse optimeringsproblemer // Kontrol og beslutning. - 2018. - V. 5 , no. 1 . - doi : 10.1080/23307706.2017.1397554 .
Yurii Nesterov, Arkadii Nemirovskii. Interior-Point Polynomial Algoritmer i konveks programmering. - Selskab for industriel og anvendt matematik, 1995. - ISBN 978-0898715156 .
Yurii Nesterov, Arkadii Nemirovskii. Indvendige punktpolynomiske metoder i konveks programmering. - SIAM, 1994. - V. 13. - (Studier i anvendt og numerisk matematik). - ISBN 978-0-89871-319-0 .
Yurii Nesterov. Indledende forelæsninger om konveks optimering. - Boston, Dordrecht, London: Kluwer Academic Publishers, 2004. - T. 87. - (Applied Optimization). — ISBN 1-4020-7553-7 .
Jiming Peng, Cornelis Roos, Tamás Terlaky. Selvregulære funktioner og nye søgeretninger for lineær og semidefinite optimering // Matematisk programmering. - 2002. - T. 93 , no. 1 . — ISSN 0025-5610 . - doi : 10.1007/s101070200296 .
Dimitri P. Bertsekas, Angelia Nedic, Asuman Ozdaglar. Konveks analyse og optimering. - Athena Scientific, 2003. - ISBN 978-1-886529-45-8 .
Dimitri P. Bertsekas. Konveks optimeringsteori. - Belmont, MA.: Athena Scientific, 2009. - ISBN 978-1-886529-31-1 .
Dimitri P. Bertsekas. Konvekse optimeringsalgoritmer. - Belmont, MA.: Athena Scientific, 2015. - ISBN 978-1-886529-28-1 .
Stephen P. Boyd, Lieven Vandenberghe. Konveks optimering . - Cambridge University Press, 2004. - ISBN 978-0-521-83378-3 .
Jonathan M. Borwein, Adrian Lewis. Konveks analyse og ikke-lineær optimering. - Springer, 2000. - (CMS-bøger i matematik). — ISBN 0-387-29570-4 .
Peter W. Christensen, Anders Klarbring. En introduktion til strukturel optimering. - Springer Science & Business Media, 2008. - V. 153. - ISBN 9781402086663 .
Jean-Baptiste Hiriart-Urruty, Claude Lemarechal. Grundlæggende om konveks analyse. - Berlin: Springer, 2004. - (Grundlehren tekstudgaver). - ISBN 978-3-540-42205-1 .
Jean-Baptiste Hiriart-Urruty, Claude Lemarechal. Konvekse analyse- og minimeringsalgoritmer, bind I: Fundamentals. - Berlin: Springer-Verlag, 1993. - T. 305. - S. xviii + 417. - ISBN 978-3-540-56850-6 .
Jean-Baptiste Hiriart-Urruty, Claude Lemarechal. Konvekse analyse- og minimeringsalgoritmer, bind II: Avanceret teori og bundlemetoder. - Berlin: Springer-Verlag, 1993. - T. 306. - S. xviii + 346. — ISBN 978-3-540-56852-0 .
Krzysztof C. Kiwiel. Metoder til nedstigning til ikke-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 afholdt 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. ikke-lineær optimering. — Princeton University Press, 2006.
Eremin I. I. , Astafiev N. N. Introduktion til teorien om lineær og konveks programmering. - M. , Nauka , 1976. - 189 s.
Kamenev GK Optimale adaptive metoder til polyhedral tilnærmelse af konvekse kroppe. M.: VTs RAN, 2007, 230 s. ISBN 5-201-09876-2 .
Kamenev GK Numerisk undersøgelse af effektiviteten af metoder til polyhedral tilnærmelse af konvekse kroppe. M: Ed. CC RAS, 2010, 118s. ISBN 978-5-91601-043-5 .

Links

Stephen Boyd, Lieven Vandenberghe, Konveks optimering (pdf)
EE364a: Convex Optimization I , EE364b: Convex Optimization II , Oxford University kursusside
6.253: Konveks analyse og optimering , MIT OCW kursusside
Brian Borchers, En oversigt over software til konveks optimering

Optimeringsmetoder _
Endimensionel	gyldne snit metode Modsætning Parabel metode Netsøgning Ensartet bloksøgningsmetode Fibonacci metode Ternær søgning Piyavsky metode Strongin metode
Nul orden	Gauss metode Nelder-Mead metode Hook-Jeeves metode Rosenbrock metode Powell metode
Første ordre	gradient nedstigning Zeutendijk metode Koordinat nedstigning Konjugeret gradientmetode Kvasi-newtonske metoder Levenberg-Marquardt algoritme
anden orden	Newtons metode Newton-Raphson metode Broyden-Fletcher-Goldfarb-Shanno-algoritme (BFGS)
Stokastisk	Monte Carlo metode Simuleret udglødning Evolutionære algoritmer differentiel evolution Myre-algoritme Partikelsværmmetode Algoritme for bikoloni Tilfældig gå-metode
Lineære programmeringsmetoder _	Enkel metode Gomoris algoritme Ellipsoid metode Potentiel metode
Ikke-lineære programmeringsmetoder	Sekventiel kvadratisk programmering