Convex optimization: Difference between revisions

Revision as of 04:36, 25 November 2024

Revision as of 10:14, 3 December 2024

Line 1:

{{short description|Subfield of mathematical optimization}}

'''Convex optimization''' is a subfield of [[mathematical optimization]] that studies the problem of minimizing [[convex function]]s over [[convex set]]s<ref>{{Cite journal |last=Wang |first=Zhenbo |date=2024-01-01 |title=A survey on convex optimization for guidance and control of vehicular systems |url=https://www.sciencedirect.com/science/article/abs/pii/S1367578824000269 |journal=Annual Reviews in Control |volume=57 |pages=100957 |doi=10.1016/j.arcontrol.2024.100957 |issn=1367-5788|arxiv=2311.05115 }}</ref> (or, equivalently, maximizing [[concave functions]] over convex sets). Many classes of convex optimization problems admit polynomial-time algorithms,<ref name="Nesterov 1994">{{harvnb|Nesterov|Nemirovskii|1994}}</ref> whereas mathematical optimization is in general [[NP-hard]].<ref>

{{cite journal | last1 = Murty | first1 = Katta | last2 = Kabadi | first2 = Santosh | title = Some NP-complete problems in quadratic and nonlinear programming | journal = Mathematical Programming | volume = 39 | issue = 2 | pages = 117–129 | year = 1987 | doi = 10.1007/BF02592948| hdl = 2027.42/6740 | s2cid = 30500771 | hdl-access = free}}</ref><ref>Sahni, S. "Computationally related problems," in SIAM Journal on Computing, 3, 262--279, 1974.</ref><ref>{{cite journal | url=https://link.springer.com/article/10.1007/BF00120662 | doi=10.1007/BF00120662 | title=Quadratic programming with one negative eigenvalue is NP-hard | date=1991 | last1=Pardalos | first1=Panos M. | last2=Vavasis | first2=Stephen A. | journal=Journal of Global Optimization | volume=1 | pages=15–22 }}</ref>