Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) No edit summary |
||
Line 58:
[[File:Hierarchy compact convex.png|thumb|A hierarchy of convex optimization problems. (LP: linear program, QP: quadratic program, SOCP second-order cone program, SDP: semidefinite program, CP: cone program.)]]
*[[Linear programming]] problems are
*
*[[Second order cone programming]] are more general.
*[[Semidefinite programming]] are more general.
Line 77:
These results are used by the theory of convex minimization along with geometric notions from [[functional analysis]] (in Hilbert spaces) such as the [[Hilbert projection theorem]], the [[separating hyperplane theorem]], and [[Farkas' lemma]].{{citation needed|date=July 2022}}
==Algorithms==
== Practical applications ==▼
Unconstrained convex optimization can be easily solved with [[gradient descent]] (a special case of [[Method of steepest descent|steepest descent]]) or [[Newton's method in optimization|Newton's method]], combined with [[line search]] for an appropriate step size; these can be mathematically proven to converge quickly, especially the latter method.<ref name=":2">{{Cite book|last1=Boyd|first1=Stephen|url=https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf|title=Convex Optimization|last2=Vandenberghe|first2=Lieven|publisher=[[Cambridge University Press]]|year=2004|isbn=978-0-521-83378-3|access-date=12 Apr 2021}}</ref> Convex optimization with linear equality constraints can also be solved using [[Karush–Kuhn–Tucker conditions|KKT matrix]] techniques if the objective function is a [[quadratic function]] (which generalizes to a variation of Newton's method, which works even if the point of initialization does not satisfy the constraints), but can also generally be solved by eliminating the equality constraints with [[linear algebra]] or solving the dual problem.<ref name=":2" /> Finally, convex optimization with both linear equality constraints and convex inequality constraints can be solved by applying an unconstrained convex optimization technique to the objective function plus [[Logarithmic barrier function|logarithmic barrier]] terms.<ref name=":2" /> (When the starting point is not feasible - that is, satisfying the constraints - this is preceded by so-called ''phase I'' methods, which either find a feasible point or show that none exist. Phase I methods generally consist of reducing the search in question to yet another convex optimization problem.<ref name=":2" />)▼
Convex optimization has applications in a wide range of disciplines, such as automatic [[control systems]], estimation and [[signal processing]], communications and networks, electronic [[circuit design]],<ref>{{harvnb|Boyd|Vandenberghe|2004|p=17}}</ref> data analysis and modeling, [[finance]], [[statistics]] ([[optimal design|optimal experimental design]]),<ref>Chritensen/Klarbring, chpt. 4.</ref> and [[structural optimization]], where the approximation concept has proven to be efficient.<ref>{{harvnb|Boyd|Vandenberghe|2004}}</ref><ref>Schmit, L.A.; Fleury, C. 1980: ''Structural synthesis by combining approximation concepts and dual methods''. J. Amer. Inst. Aeronaut. Astronaut 18, 1252-1260</ref> Convex optimization has practical applications for the following fields:▼
Convex optimization problems can also be solved by the following contemporary methods:<ref>For methods for convex minimization, see the volumes by Hiriart-Urruty and Lemaréchal (bundle) and the textbooks by [[Andrzej Piotr Ruszczyński|Ruszczyński]], [[Dimitri Bertsekas|Bertsekas]], and ▼
* [[Portfolio optimization]].<ref name=":0">{{Cite web|last1=Boyd|first1=Stephen|last2=Diamond|first2=Stephen|last3=Zhang|first3=Junzi|last4=Agrawal|first4=Akshay|title=Convex Optimization Applications|url=https://web.stanford.edu/~boyd/papers/pdf/cvx_applications.pdf|url-status=live|access-date=12 Apr 2021|archive-url=https://web.archive.org/web/20151001185038/http://web.stanford.edu/~boyd/papers/pdf/cvx_applications.pdf |archive-date=2015-10-01 }}</ref>▼
Boyd and Vandenberghe (interior point).▼
* Worst-case risk analysis.<ref name=":0" />▼
</ref>▼
* Optimal advertising.<ref name=":0" />▼
* [[Subgradient method#Subgradient-projection & bundle methods|Bundle methods]] (Wolfe, Lemaréchal, Kiwiel), and▼
* Variations of [[Regression analysis|statistical regression]] (including [[Regularization (mathematics)|regularization]] and [[quantile regression]]).<ref name=":0" />▼
* [[Subgradient method#Subgradient-projection & bundle methods|Subgradient projection]] methods (Polyak),▼
* Model fitting<ref name=":0" /> (particularly [[multiclass classification]]<ref name=":1">{{Cite web|last=Malick|first=Jérôme|date=2011-09-28|title=Convex optimization: applications, formulations, relaxations|url=https://www-ljk.imag.fr//membres/Jerome.Malick/Talks/11-INRIA.pdf|url-status=live|access-date=12 Apr 2021|archive-url=https://web.archive.org/web/20210412044738/https://www-ljk.imag.fr//membres/Jerome.Malick/Talks/11-INRIA.pdf |archive-date=2021-04-12 }}</ref>).▼
* [[Interior-point methods]],<ref name="Nesterov 1994" /> which make use of [[self-concordant function|self-concordant]] barrier functions <ref>{{cite book |title=Interior-Point Polynomial Algorithms in Convex Programming |last1= Nesterov |first1=Yurii |first2=Nemirovskii |last2=Arkadii |year=1995 |publisher=Society for Industrial and Applied Mathematics |isbn=978-0898715156 }}</ref> and self-regular barrier functions.<ref name="PengRoos2002">{{cite journal|last1=Peng|first1=Jiming|last2=Roos|first2=Cornelis|last3=Terlaky|first3=Tamás|title=Self-regular functions and new search directions for linear and semidefinite optimization|journal=Mathematical Programming|volume=93|issue=1|year=2002|pages=129–171|issn=0025-5610|doi=10.1007/s101070200296|s2cid=28882966}}</ref>▼
* [[Electricity generation]] optimization.<ref name=":1" />▼
*[[Cutting-plane methods]]▼
* [[Combinatorial optimization]].<ref name=":1" />▼
*[[Ellipsoid method]]▼
* Non-probabilistic modelling of [[uncertainty]].<ref>Ben Haim Y. and Elishakoff I., Convex Models of Uncertainty in Applied Mechanics, Elsevier Science Publishers, Amsterdam, 1990</ref>▼
*[[Subgradient method]]▼
* Localization using wireless signals <ref>[[Ahmad Bazzi]], Dirk TM Slock, and Lisa Meilhac. "Online angle of arrival estimation in the presence of mutual coupling." 2016 IEEE Statistical Signal Processing Workshop (SSP). IEEE, 2016.</ref>▼
*[[Drift plus penalty|Dual subgradients and the drift-plus-penalty method]]▼
Subgradient methods can be implemented simply and so are widely used.<ref>{{Cite journal |date=2006 |title=Numerical Optimization |url=https://link.springer.com/book/10.1007/978-0-387-40065-5 |journal=Springer Series in Operations Research and Financial Engineering |language=en |doi=10.1007/978-0-387-40065-5}}</ref> Dual subgradient methods are subgradient methods applied to a [[Duality (optimization)|dual problem]]. The [[Drift plus penalty|drift-plus-penalty]] method is similar to the dual subgradient method, but takes a time average of the primal variables.{{Citation needed|date=April 2021}}▼
== Lagrange multipliers ==
{{Unreferenced section|date=April 2021}}
Consider a convex minimization problem given in standard form by a cost function <math>f(x)</math> and inequality constraints <math>g_i(x)\leq 0</math> for <math> 1 \leq i \leq m</math>. Then the ___domain <math>\mathcal{X}</math> is:
Line 114 ⟶ 117:
Conversely, if some <math>x</math> in <math>X</math> satisfies (1)–(3) for [[scalar (mathematics)|scalar]]s <math>\lambda_{0},\ldots,\lambda_{m} </math> with <math>\lambda_{0}=1</math> then <math>x</math> is certain to minimize <math>f</math> over <math>X</math>.
==
▲Unconstrained convex optimization can be easily solved with [[gradient descent]] (a special case of [[Method of steepest descent|steepest descent]]) or [[Newton's method in optimization|Newton's method]], combined with [[line search]] for an appropriate step size; these can be mathematically proven to converge quickly, especially the latter method.<ref name=":2">{{Cite book|last1=Boyd|first1=Stephen|url=https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf|title=Convex Optimization|last2=Vandenberghe|first2=Lieven|publisher=[[Cambridge University Press]]|year=2004|isbn=978-0-521-83378-3|access-date=12 Apr 2021}}</ref> Convex optimization with linear equality constraints can also be solved using [[Karush–Kuhn–Tucker conditions|KKT matrix]] techniques if the objective function is a [[quadratic function]] (which generalizes to a variation of Newton's method, which works even if the point of initialization does not satisfy the constraints), but can also generally be solved by eliminating the equality constraints with [[linear algebra]] or solving the dual problem.<ref name=":2" /> Finally, convex optimization with both linear equality constraints and convex inequality constraints can be solved by applying an unconstrained convex optimization technique to the objective function plus [[Logarithmic barrier function|logarithmic barrier]] terms.<ref name=":2" /> (When the starting point is not feasible - that is, satisfying the constraints - this is preceded by so-called ''phase I'' methods, which either find a feasible point or show that none exist. Phase I methods generally consist of reducing the search in question to yet another convex optimization problem.<ref name=":2" />)
▲Convex optimization problems can also be solved by the following contemporary methods:<ref>For methods for convex minimization, see the volumes by Hiriart-Urruty and Lemaréchal (bundle) and the textbooks by [[Andrzej Piotr Ruszczyński|Ruszczyński]], [[Dimitri Bertsekas|Bertsekas]], and
▲Boyd and Vandenberghe (interior point).
▲</ref>
▲* [[Subgradient method#Subgradient-projection & bundle methods|Bundle methods]] (Wolfe, Lemaréchal, Kiwiel), and
▲* [[Subgradient method#Subgradient-projection & bundle methods|Subgradient projection]] methods (Polyak),
▲* [[Interior-point methods]],<ref name="Nesterov 1994"/> which make use of [[self-concordant function|self-concordant]] barrier functions <ref>{{cite book |title=Interior-Point Polynomial Algorithms in Convex Programming |last1= Nesterov |first1=Yurii |first2=Nemirovskii |last2=Arkadii |year=1995 |publisher=Society for Industrial and Applied Mathematics |isbn=978-0898715156 }}</ref> and self-regular barrier functions.<ref name="PengRoos2002">{{cite journal|last1=Peng|first1=Jiming|last2=Roos|first2=Cornelis|last3=Terlaky|first3=Tamás|title=Self-regular functions and new search directions for linear and semidefinite optimization|journal=Mathematical Programming|volume=93|issue=1|year=2002|pages=129–171|issn=0025-5610|doi=10.1007/s101070200296|s2cid=28882966}}</ref>
▲*[[Cutting-plane methods]]
▲*[[Ellipsoid method]]
▲*[[Subgradient method]]
▲*[[Drift plus penalty|Dual subgradients and the drift-plus-penalty method]]
▲Subgradient methods can be implemented simply and so are widely used.<ref>{{Cite journal |date=2006 |title=Numerical Optimization |url=https://link.springer.com/book/10.1007/978-0-387-40065-5 |journal=Springer Series in Operations Research and Financial Engineering |language=en |doi=10.1007/978-0-387-40065-5}}</ref> Dual subgradient methods are subgradient methods applied to a [[Duality (optimization)|dual problem]]. The [[Drift plus penalty|drift-plus-penalty]] method is similar to the dual subgradient method, but takes a time average of the primal variables.{{Citation needed|date=April 2021}}
There is a large software ecosystem for convex optimization. This ecosystem has two main categories: ''solvers'' on the one hand and ''modeling tools'' (or ''interfaces'') on the other hand.
Line 312 ⟶ 300:
|<ref name=":3" />
|}
▲== Practical applications ==
▲Convex optimization has applications in a wide range of disciplines, such as automatic [[control systems]], estimation and [[signal processing]], communications and networks, electronic [[circuit design]],<ref>{{harvnb|Boyd|Vandenberghe|2004|p=17}}</ref> data analysis and modeling, [[finance]], [[statistics]] ([[optimal design|optimal experimental design]]),<ref>Chritensen/Klarbring, chpt. 4.</ref> and [[structural optimization]], where the approximation concept has proven to be efficient.<ref>{{harvnb|Boyd|Vandenberghe|2004}}</ref><ref>Schmit, L.A.; Fleury, C. 1980: ''Structural synthesis by combining approximation concepts and dual methods''. J. Amer. Inst. Aeronaut. Astronaut 18, 1252-1260</ref> Convex optimization has practical applications for the following fields:
▲* [[Portfolio optimization]].<ref name=":0">{{Cite web |last1=Boyd |first1=Stephen |last2=Diamond |first2=Stephen |last3=Zhang |first3=Junzi |last4=Agrawal |first4=Akshay |title=Convex Optimization Applications |url=https://web.stanford.edu/~boyd/papers/pdf/cvx_applications.pdf |url-status=live
▲* Worst-case risk analysis.<ref name=":0" />
▲* Optimal advertising.<ref name=":0" />
▲* Variations of [[Regression analysis|statistical regression]] (including [[Regularization (mathematics)|regularization]] and [[quantile regression]]).<ref name=":0" />
▲* Model fitting<ref name=":0" /> (particularly [[multiclass classification]]<ref name=":1">{{Cite web |last=Malick |first=Jérôme |date=2011-09-28 |title=Convex optimization: applications, formulations, relaxations |url=https://www-ljk.imag.fr//membres/Jerome.Malick/Talks/11-INRIA.pdf |url-status=live
▲* [[Electricity generation]] optimization.<ref name=":1" />
▲* [[Combinatorial optimization]].<ref name=":1" />
▲* Non-probabilistic modelling of [[uncertainty]].<ref>Ben Haim Y. and Elishakoff I., Convex Models of Uncertainty in Applied Mechanics, Elsevier Science Publishers, Amsterdam, 1990</ref>
▲* Localization using wireless signals <ref>[[Ahmad Bazzi]], Dirk TM Slock, and Lisa Meilhac. "Online angle of arrival estimation in the presence of mutual coupling." 2016 IEEE Statistical Signal Processing Workshop (SSP). IEEE, 2016.</ref>
==Extensions==
| |||