Programare convexă

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 21 noiembrie 2021; verificările necesită 2 modificări .

Programarea convexă este un subdomeniu al optimizării matematice care studiază problema minimizării funcțiilor convexe pe mulțimi convexe . În timp ce multe clase de probleme de programare convexe admit algoritmi de timp polinomial [1] , optimizarea matematică este în general NP-hard [2] [3] [4] .

Programarea convexă are aplicații într-o gamă largă de discipline, cum ar fi sistemele de control automat , evaluarea și procesarea semnalului , comunicații și rețele, circuite [5] , analiza și modelarea datelor, finanțe , statistici ( proiectare optimă a experimentelor ) [6] și optimizare structurală [7] . Dezvoltarea tehnologiei informatice și a algoritmilor de optimizare a făcut programarea convexă aproape la fel de simplă ca programarea liniară [8] .

Definiție

O problemă de programare convexă este o problemă de optimizare în care funcția obiectiv este o funcție convexă și domeniul soluțiilor fezabile este convex . O funcție care mapează o anumită submulțime este convexă dacă domeniul este convex atât pentru toate cât și pentru toate în domeniul lor de . O mulțime este convexă dacă pentru toate elementele sale și oricare dintre ele aparține de asemenea mulțimii. $f$ $\mathbb {R} ^{n}$ $\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$

În special, problema programării convexe este problema găsirii unor , pe care $\mathbf {x^{\ast }} \in C$

\inf\{f(\mathbf {x}):\mathbf {x} \în C\)

unde funcția obiectiv este convexă, la fel ca și mulțimea soluțiilor fezabile [9] [10] . Dacă un astfel de punct există, se numește punct optim . Mulțimea tuturor punctelor optime se numește mulțime optimă . Dacă este nemărginită de sau infimumul nu este atins, se spune că optimizarea este nemărginită . Dacă este gol, se vorbește de o sarcină inacceptabilă [11] . $f$ $C$ $f$ $C$ $C$

Forma standard

Se spune că o problemă de programare convexă este în formă standard dacă este scrisă ca

Minimizați

f(\mathbf {x} )

În condiții

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

unde este variabila de optimizare, funcțiile sunt convexe, iar funcțiile sunt afine [11] . $x \in \mathbb{R}^n$ $f,g_{1},\ldots,g_{m)$ $h_{1},\ldots ,h_{p)$

În acești termeni, funcția este funcția obiectiv a problemei, iar funcțiile și sunt numite funcții de constrângere. Mulțimea admisibilă de soluții la problema de optimizare este mulțimea formată din toate punctele care îndeplinesc condițiile și . Această mulțime este convexă deoarece mulțimile de subnivel ale unei funcții convexe sunt convexe, mulțimile afine sunt de asemenea convexe, iar intersecția mulțimilor convexe este o mulțime convexă [12] . $f$ $g_i$ $Bună}$ $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$

Multe probleme de optimizare pot fi reduse la această formă standard. De exemplu, problema maximizării unei funcții concave poate fi reformulată în mod echivalent ca problema minimizării unei funcții convexe , astfel încât problema maximizării unei funcții concave pe o mulțime convexă este adesea denumită problemă de programare convexă. $f$ $-f$

Proprietăți

Proprietăți utile ale problemelor de programare convexă [13] [11] :

orice minim local este un minim global ;
setul optim este convex;
dacă funcția obiectiv este puternic convexă, problema are cel mult un punct optim.

Aceste rezultate sunt folosite în teoria minimizării convexe, împreună cu concepte geometrice din analiza funcțională (pe spații Hilbert ), cum ar fi teorema de proiecție a lui Hilbert , teorema hiperplanului suport și lema lui Farkas .

Exemple

Următoarele clase de probleme sunt probleme de programare convexe sau pot fi reduse la probleme de programare convexe prin transformări simple [11] [14] :

Metoda celor mai mici pătrate
Programare liniară
Optimizare cuadratică convexă cu constrângeri liniare
Programare pătratică în constrângeri pătratice
Optimizare conică
Programare geometrică
Programare conică pe un con de ordinul doi
Programare semidefinită
Principiul maxim al entropiei cu restricții corespunzătoare

Metoda multiplicatorilor Lagrange

Luați în considerare o problemă de minimizare convexă dată în formă standard cu o funcție de cost și constrângeri de inegalitate pentru . Atunci domeniul de definiție este: $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\}.

Funcția Lagrange pentru problemă

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

Pentru orice punct de la care se minimizează la , există numere reale , numite multiplicatori Lagrange , pentru care următoarele condiții sunt îndeplinite simultan: $X$ $X$ $f$ $X$ $\lambda _{0},\lambda _{1},\ldots,\lambda _{m},$

$X$ minimizează peste toate $L(y,\lambda _{0},\lambda _{1},\ldots,\lambda _{m})$ $y\în X,$
$\lambda _{0},\lambda _{1},\ldots,\lambda _{m}\geqslant 0,$ cu cel putin unul $\lambda _{k}>0,$
$\lambda _{1}g_{1}(x)=\cdots =\lambda _{m}g_{m}(x)=0$ (non-rigiditate complementară).

Dacă există un „punct puternic admisibil”, adică un punct satisfăcător $z$

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

atunci afirmația de mai sus poate fi întărită pentru a solicita . $\lambda _{0}=1$

În schimb, dacă unele dintre ele îndeplinesc condițiile (1)-(3) pentru scalarii cu , atunci cu siguranță se minimizează pe . $X$ $X$ $\lambda _{0},\ldots,\lambda _{m)$ $\lambda _{0}=1$ $X$ $f$ $X$

Algoritmi

Problemele de programare convexă sunt rezolvate prin următoarele metode moderne: [15]

Metode ale fasciculului subgradient } (Wolf, Lemerical, Kivel),
Metode de proiecție subgradient (Polyak),
Metoda punctului interior [1] folosind funcții de barieră auto-consistente [16] și funcții de barieră auto-regulate [17] .
Metoda planului de tăiere
Metoda elipsoidă
Metode de subgradient
Subgradienți de deriva și metoda derivei+penalizării

Metodele sub-gradient pot fi implementate pur și simplu pentru că sunt utilizate pe scară largă [18] [19] . Metodele cu subgradient dublu sunt metode subgradiente aplicate unei probleme duale . Metoda drift+penalty este similară cu metoda dual subgradient, dar folosește media de timp a principalelor variabile.

Extensii

Extensiile pentru programarea convexă includ optimizări pentru funcții biconvexe , pseudoconvexe și cvasiconvexe . Extensii ale teoriei analizei convexe și metodelor iterative pentru rezolvarea aproximativă a problemelor de optimizare neconvexe apar în domeniul convexității generalizate , cunoscut sub numele de analiză abstractă convexă.

Vezi și

Note

↑ 1 2 Nesterov și Nemirovskii, 1994 .
↑ Murty și Kabadi 1987 , p. 117–129.
↑ Sahni, 1974 , p. 262-279.
↑ Pardalos și Vavasis, 1991 , p. 15-22.
↑ Boyd și Vandenberghe 2004 , p. 17.
↑ Christensen, Klarbring, 2008 , p. cap. patru.
↑ Boyd, Vandenberghe, 2004 .
↑ Boyd și Vandenberghe 2004 , p. opt.
↑ Hiriart-Urruty, Lemaréchal, 1996 , p. 291.
↑ Ben-Tal, Nemirovskiĭ, 2001 , p. 335–336.
↑ 1 2 3 4 Boyd, Vandenberghe, 2004 , p. cap. patru.
↑ Boyd și Vandenberghe 2004 , p. cap. 2.
↑ Rockafellar, 1993 , p. 183–238.
↑ Agrawal, Verschueren, Diamond, Boyd, 2018 , p. 42–60.
↑ Pentru metode de programare convexă, vezi cărțile lui Irriart-Urruti și Lemerical (mai multe cărți) și cărțile lui Rushczynski, Bercekas și Boyd și Vanderberge (metodele punctului interior).
↑ Nesterov, Nemirovskii, 1995 .
↑ Peng, Roos, Terlaky, 2002 , p. 129–171.
↑ Bertsekas, 2009 .
↑ Bertsekas, 2015 .

Literatură

Jean-Baptiste Hiriart-Urruty, Claude Lemarechal. Analiză convexă și algoritmi de minimizare: Fundamente . - 1996. - ISBN 9783540568506 .
Aharon Ben-Tal, Arkadi Semenovich Nemirovskiĭ. Prelegeri despre optimizarea convexă modernă: analiză, algoritmi și aplicații de inginerie . - 2001. - ISBN 9780898714913 .
Katta Murty, Santosh Kabadi. Câteva probleme NP-complete în programarea pătratică și neliniară // Programare matematică. - 1987. - T. 39 , nr. 2 . — p. 117–129 . - doi : 10.1007/BF02592948 .
Sahni S. Probleme legate de calcul // SIAM Journal on Computing. - 1974. - Emisiune. 3 .
Panos M. Pardalos, Stephen A. Vavasis. Programarea pătratică cu o singură valoare negativă este NP-hard // Journal of Global Optimization. - 1991. - T. 1 , Nr. 1 .
R. Tyrrell Rockafellar. Analiza convexă . — Princeton: Princeton University Press, 1970.
R. Tyrrell Rockafellar. Multiplicatori Lagrange și optimitate // Revizuirea SIAM. - 1993. - T. 35 , nr. 2 . - doi : 10.1137/1035044 .
Akshay Agrawal, Robin Verschueren, Steven Diamond, Stephen Boyd. Un sistem de rescriere pentru probleme de optimizare convexe // Control și decizie. - 2018. - V. 5 , nr. 1 . - doi : 10.1080/23307706.2017.1397554 .
Yurii Nesterov, Arkadii Nemirovskii. Algoritmi polinomii de punct interior în programarea convexă. - Societatea de Matematică Industrială și Aplicată, 1995. - ISBN 978-0898715156 .
Yurii Nesterov, Arkadii Nemirovskii. Metode polinomiale punctului interior în programarea convexă. - SIAM, 1994. - V. 13. - (Studii de matematică aplicată şi numerică). - ISBN 978-0-89871-319-0 .
Yurii Nesterov. Prelegeri introductive despre optimizarea convexă. - Boston, Dordrecht, Londra: Kluwer Academic Publishers, 2004. - T. 87. - (Optimizare aplicată). — ISBN 1-4020-7553-7 .
Jiming Peng, Cornelis Roos, Tamás Terlaky. Funcții autonome și noi direcții de căutare pentru optimizare liniară și semidefinită // Programare matematică. - 2002. - T. 93 , nr. 1 . — ISSN 0025-5610 . - doi : 10.1007/s101070200296 .
Dimitri P. Bertsekas, Angelia Nedic, Asuman Ozdaglar. Analiză și optimizare convexă. - Athena Scientific, 2003. - ISBN 978-1-886529-45-8 .
Dimitri P. Bertsekas. Teoria optimizării convexe. - Belmont, MA.: Athena Scientific, 2009. - ISBN 978-1-886529-31-1 .
Dimitri P. Bertsekas. Algoritmi de optimizare convexă. - Belmont, MA.: Athena Scientific, 2015. - ISBN 978-1-886529-28-1 .
Stephen P. Boyd, Lieven Vandenberghe. Optimizare convexă . - Cambridge University Press, 2004. - ISBN 978-0-521-83378-3 .
Jonathan M. Borwein, Adrian Lewis. Analiză convexă și optimizare neliniară. - Springer, 2000. - (CMS Books in Mathematics). — ISBN 0-387-29570-4 .
Peter W. Christensen, Anders Klarbring. O introducere în optimizarea structurală. - Springer Science & Businees Media, 2008. - V. 153. - ISBN 9781402086663 .
Jean-Baptiste Hiriart-Urruty, Claude Lemarechal. Fundamentele analizei convexe. - Berlin: Springer, 2004. - (Ediții de text Grundlehren). - ISBN 978-3-540-42205-1 .
Jean-Baptiste Hiriart-Urruty, Claude Lemarechal. Algoritmi de analiză convexă și minimizare, Volumul I: Fundamente. - Berlin: Springer-Verlag, 1993. - T. 305. - S. xviii + 417. - ISBN 978-3-540-56850-6 .
Jean-Baptiste Hiriart-Urruty, Claude Lemarechal. Algoritmi de analiză convexă și minimizare, Volumul II: Teorie avansată și metode de pachet. - Berlin: Springer-Verlag, 1993. - T. 306. - S. xviii + 346. — ISBN 978-3-540-56852-0 .
Krzysztof C. Kiwiel. Metode de coborâre pentru optimizarea nediferențiată. - New York: Springer-Verlag, 1985. - (Lecture Notes in Mathematics). — ISBN 978-3-540-15642-0 .
Claude Lemarechal. Relaxare lagrangiană // Optimizare combinatorie computațională: Lucrări de la școala de primăvară ținută în Schloß Dagstuhl, 15–19 mai 2000. - Berlin: Springer-Verlag, 2001. - Vol. 2241. - P. 112-156. — ISBN 978-3-540-42877-0 . - doi : 10.1007/3-540-45586-8_4 .
Andrzej Ruszczyński. optimizare neliniară. — Princeton University Press, 2006.
Eremin I. I. , Astafiev N. N. Introducere în teoria programării liniare și convexe. - M. , Nauka , 1976. - 189 p.
Kamenev GK Metode adaptative optime pentru aproximarea poliedrică a corpurilor convexe. M.: VTs RAN, 2007, 230 p. ISBN 5-201-09876-2 .
Kamenev GK Studiu numeric al eficienței metodelor de aproximare poliedrică a corpurilor convexe. M: Ed. CC RAS, 2010, 118s. ISBN 978-5-91601-043-5 .

Link -uri

Stephen Boyd, Lieven Vandenberghe, Optimizare convexă (pdf)
EE364a: Optimizare convexă I , EE364b: Optimizare convexă II , pagina de curs de la Universitatea Oxford
6.253: Convex Analysis and Optimization , pagina de curs MIT OCW
Brian Borchers, O prezentare generală a software-ului pentru optimizarea convexă

Metode de optimizare
Unidimensional	metoda secțiunii de aur Dihotomie Metoda parabolelor Căutare în grilă Metoda de căutare uniformă a blocurilor Metoda Fibonacci Căutare ternară metoda Piyavsky Metoda Strongin
Comanda zero	metoda Gauss Metoda Nelder-Mead Metoda Hook-Jeeves metoda Rosenbrock Metoda Powell
Prima comanda	coborâre în gradient Metoda Zeutendijk Coordonarea coborârii Metoda gradientului conjugat Metode cvasi-newtoniene Algoritmul Levenberg-Marquardt
a doua comanda	metoda lui Newton Metoda Newton-Raphson Algoritmul Broyden-Fletcher-Goldfarb-Shanno (BFGS)
Stochastic	Metoda Monte Carlo Recoacere simulată Algoritmi evolutivi evolutie diferentiala Algoritmul furnicilor Metoda roiului de particule Algoritmul coloniilor de albine Metoda de mers aleatoriu
Metode de programare liniară	Metoda simplex algoritmul lui Gomori Metoda elipsoidă Metoda potențială
Metode de programare neliniară	Programare secvenţială pătratică