Convex optimization: Difference between revisions

Revision as of 20:17, 12 September 2023

Revision as of 09:03, 27 September 2023

Line 107:

==Algorithms==

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|url-status=live}}</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

Line 352:

| isbn = 978-1-886529-28-1

}}

*{{Cite book|last1=Borwein|first1=Jonathan|url=https://carma.newcastle.edu.au/resources/jon/Preprints/Books/CaNo2/cano2f.pdf|title=Convex Analysis and Nonlinear Optimization: Theory and Examples, Second Edition|last2=Lewis|first2=Adrian|publisher=Springer|year=2000|access-date=12 Apr 2021|url-status=live}}

* {{cite book

| author1 = Christensen, Peter W.