Metode de subgradient

Metodele subgradient sunt metode iterative pentru rezolvarea problemelor de minimizare convexe . Metodele subgradient dezvoltate de Naum Zuselevich Shor converg chiar și atunci când sunt aplicate la funcții obiectiv nediferențiabile . Când funcția este diferențiabilă, metodele subgradient pentru probleme neconstrânse utilizează aceeași direcție de căutare ca metoda de coborâre cu cea mai abruptă .

Metodele subgradient sunt mai lente decât metodele lui Newton , în care funcțiile convexe dublu diferențiabile continuu sunt utilizate pentru minimizare. Cu toate acestea, metodele lui Newton încetează să convergă asupra problemelor care au îndoieli nediferențiabile.

În ultimii ani, unele metode de punct interior au fost propuse pentru probleme de minimizare convexă, dar atât metodele de proiecție subgradient, cât și metodele de coborâre a fasciculului aferente rămân competitive. Pentru problemele de minimizare convexe cu un număr mare de dimensiuni, metodele de proiecție subgradient sunt acceptabile deoarece necesită o cantitate mică de memorie.

Metodele de proiecție subgradient sunt adesea aplicate problemelor de dimensiuni mari folosind tehnici de descompunere. Astfel de metode de descompunere permit adesea o metodă simplă de sarcini distribuite.

Reguli pentru subgradientul clasic

Fie o funcție convexă cu domeniu . Metoda clasică subgradient iterează $f:\mathbb {R} ^{n}\la \mathbb {R}$ $\mathbb {R} ^{n}$

x^{(k+1)}=x^{(k)}-\alpha _{k}g^{(k))

unde este orice subdiferențială a funcției în punctul , și este a k - a iterație a variabilei . Dacă este diferențiabilă, atunci singurul său subgradient este gradientul lui . Se poate întâmpla ca în acel punct să nu fie o direcție descrescătoare . Prin urmare, conținem o listă , care stochează cele mai mici valori găsite ale funcției obiectiv, adică $g^{(k))$ $f$ $x^{{(k)}}$ $x^{{(k)}}$ $X$ $f\$ $\nabla f$ $-g^{(k))$ $f$ $x^{{(k)}}$ $f_{\rm {cel mai bun)}$

f_{\rm {cel mai bun}}^{(k)}=\min\{f_{\rm {cel mai bun}}^{(k-1)},f(x^{(k)})\ }.

Reguli pentru dimensiunea pasului

Metodele subgradient utilizează un număr mare de reguli diferite de selecție a mărimii pasului. Aici notăm cinci reguli clasice pentru care sunt cunoscute dovezile de convergență :

Dimensiunea pasului constant, . $\alpha _{k}=\alpha$
Lungimea pasului constant , care dă . $\alpha _{k}=\gamma /\lVert g^{(k)}\rVert _{2)$ $\lVert x^{(k+1)}-x^{(k)}\rVert _{2}=\gamma$
Dimensiunea pasului pătrat însumabil, dar nesumabil, adică orice dimensiune a pasului pentru care

\alpha _{k}\geqslant 0,\qquad \sum _{k=1}^{\infty }\alpha _{k}^{2}<\infty,\qquad \sum _{k= 1}^{\infty }\alpha _{k}=\infty .

O dimensiune descrescătoare a pasului, care nu se însumează, adică orice pas care satisface

\alpha _{k}\geqslant 0,\qquad \lim _{k\to \infty }\alpha _{k}=0,\qquad \sum _{k=1}^{\infty }\ alfa _{k}=\infty .

Lungimea pasului descrescătoare nesumabilă, adică unde $\alpha _{k}=\gamma _{k}/\lVert g^{(k)}\rVert _{2)$

\gamma _{k}\geqslant 0,\qquad \lim _{k\to \infty }\gamma _{k}=0,\qquad \sum _{k=1}^{\infty }\ gamma _{k}=\infty .

Pentru toate cele cinci reguli, dimensiunea pasului este determinată „în avans”, înainte de începerea metodei. Dimensiunea pasului este independentă de iterațiile anterioare. Proprietatea de selecție a pașilor „în avans” pentru metodele subgradient diferă de regulile de selecție a pașilor „în desfășurare” utilizate în metodele pentru funcții diferențiabile - multe metode de minimizare a funcțiilor diferențiabile satisfac condițiile Wolf pentru convergență, unde dimensiunile pasului depind de curentul poziţia punctului şi direcţia curentă de căutare. O discuție extinsă despre regulile de selecție a pașilor pentru metodele subgradient, inclusiv versiunile incrementale, este dată în cartea lui Bertsekas [1] și, de asemenea, în cartea lui Bertsekas, Nedić și Ozdağlar [2] .

Convergență

Pentru o lungime constantă a pasului și subgradienți scalabili având o normă euclidiană egală cu unu, metoda subgradientului se apropie în mod arbitrar de valoarea minimă, i.e.

\lim _{k\to \infty }f_{\rm {cel mai bun}}^{(k)} -f^{*}<\epsilon

conform Shore [3] .

Metodele clasice subgradient au o convergență slabă și nu mai sunt recomandate pentru utilizare [4] [5] . Cu toate acestea, ele sunt încă folosite în aplicații specializate deoarece sunt simple și ușor de adaptat la structuri speciale pentru a profita de caracteristicile acestora.

Proiecții subgradient și metode ale fasciculului

În anii 1970, Claude Lemérachel și Phil Wolf au propus „metode snopi” pentru coborâre pentru probleme de minimizare convexă [6] . Sensul termenului „metode fascicul” s-a schimbat mult de atunci. Versiuni moderne și o analiză completă de convergență au fost date de Kiel [7] . Metodele moderne ale fasciculului folosesc adesea reguli de „ control al nivelului ” pentru selectarea dimensiunii pasului, care dezvoltă tehnici din metoda „proiecției subgradient” a lui Boris T. Polyak (1969). Cu toate acestea, există probleme din cauza cărora metodele fasciculului oferă adesea puțin avantaj față de metodele de proiecție subgradient [4] [5] .

Optimizare constrânsă

Metoda de proiecție subgradient

O extensie a metodelor subgradient este metoda proiecției subgradient , care rezolvă problema de optimizare constrânsă.

minimizați în condiții

f(x)

x\in {\mathcal {C)}

unde este o mulțime convexă . Metoda de proiecție subgradient folosește iterații ${\mathcal {C}}$

x^{(k+1)}=P\left(x^{(k)}-\alpha _{k}g^{(k)}\right)

unde este proiecția pe , și este orice subgradient la . $P$ ${\mathcal {C}}$ $g^{(k))$ $f$ $x^{{(k)}}$

Restricții generale

Metoda subgradientului poate fi extinsă pentru a rezolva problema cu constrângeri sub formă de inegalități

minimizați în condiții

f_{0}(x)

f_{i}(x)\leqslant 0,\quad i=1,\dots,m

unde funcțiile sunt convexe. Algoritmul ia aceeași formă a cazului fără restricții $f_{i}$

x^{(k+1)}=x^{(k)}-\alpha _{k}g^{(k))

unde este dimensiunea pasului și este subgradientul funcției obiectiv sau una dintre funcțiile de constrângere în punctul . Aici $\alpha _{k}>0$ $g^{(k))$ $X$

g^{(k)}={\begin{cases}\partial f_{0}(x)&f_{i}(x)\leqslant 0\;\forall i=1\dots m\\\partial f_{j}(x)&\există j:f_{j}(x)>0\end{cases}}

unde înseamnă subdiferenţialul funcţiei . Dacă punctul curent este valid, algoritmul folosește subgradientul funcției obiectiv. Dacă punctul este invalid, algoritmul selectează un subgradient al oricărei constrângeri care este încălcată. $\partial f$ $f$

Note

↑ Bertsekas, 2015 .
↑ Bertsekas, Nedic, Ozdaglar, 2003 .
↑ Convergența metodelor subgradient cu pas constant (scalat) este menționată în exercițiul 6.3.14(a) din cartea lui Bertsekas (pagina 636) ( Bertsekas 1999 ) și el atribuie acest rezultat lui Shor ( Shor 1985 )
↑ 1 2 Lemarechal, 2001 , p. 112–156.
↑ 1 2 Kiwiel, Larsson, Lindberg, 2007 , p. 669–686.
↑ Bertsekas, 1999 .
↑ Kiwiel, 1985 , p. 362.

Literatură

Dimitri P. Bertsekas . Algoritmi de optimizare convexă. - Al doilea. - Belmont, MA.: Athena Scientific, 2015. - ISBN 978-1-886529-28-1 .
Dimitri P. Bertsekas, Angelia Nedic, Asuman Ozdaglar. Analiză și optimizare convexă. - Al doilea. - Belmont, MA.: Athena Scientific, 2003. - ISBN 1-886529-45-0 .
Naum Z. Shor . Metode de minimizare pentru funcții nediferențiabile. - Springer-Verlag , 1985. - ISBN 0-387-12763-1 .
Dimitri P. Bertsekas . programare neliniară. - Al doilea. - Cambridge, MA.: Athena Scientific, 1999. - ISBN 1-886529-00-0 .
Krzysztof Kiwiel. Metode de coborâre pentru optimizarea nediferențiată. - Berlin: Springer Verlag , 1985. - ISBN 978-3540156420 .
Claude Lemarechal. Relaxare lagrangiană // Optimizare combinatorie computațională: lucrări de la școala de primăvară ținută în Schloß Dagstuhl, 15–19 mai 2000 / Michael Jünger, Denis Naddef. - Berlin: Springer-Verlag, 2001. - T. 2241. - (Lecture Notes in Computer Science). — ISBN 3-540-42877-1 . - doi : 10.1007/3-540-45586-8_4 .
Krzysztof C. Kiwiel, Torbjörn Larsson, Lindberg PO Relaxarea lagrangiană prin metode de subgradient cu pas de bile // Matematica cercetării operaționale. - 2007. - august ( vol. 32 , nr. 3 ). — S. 669–686 . - doi : 10.1287/moor.1070.0261 .

Lectură suplimentară

Andrzej Piotr Ruszczyński. optimizare neliniară. — Princeton, NJ: Princeton University Press , 2006. — p. xii+454. - ISBN 978-0691119151 .

Link -uri

EE364A și EE364B , secvența de curs de optimizare convexă a lui Stanford.

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ă