Content deleted Content added
Erel Segal (talk | contribs) No edit summary |
Erel Segal (talk | contribs) Unify some references |
||
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 (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>[https://link.springer.com/article/10.1007/BF00120662 Quadratic programming with one negative eigenvalue is NP-hard], Panos M. Pardalos and Stephen A. Vavasis in ''Journal of Global Optimization'', Volume 1, Number 1, 1991, pg.15-22.</ref> With recent advancements in computing and [[Mathematical optimization#Computational optimization techniques|optimization algorithms]], convex programming is nearly as straightforward as [[linear programming]].<ref name=":2" />{{
==Definition==
Line 13:
The goal of the problem is to find some <math>\mathbf{x^\ast} \in C</math> attaining
:<math>\inf \{ f(\mathbf{x}) : \mathbf{x} \in C \}</math>.
In general, there are three options regarding the existence of a solution:<ref name="
* If such a point ''x''* exists, it is referred to as an ''optimal point'' or ''solution''; the set of all optimal points is called the ''optimal set''; and the problem is called ''solvable''.
Line 29:
\end{align}</math>
where:<ref name="
* <math>\mathbf{x} \in \mathbb{R}^n</math> is the vector of optimization variables;
Line 36:
* The equality constraint functions <math>h_i : \mathbb{R}^n \to \mathbb{R}</math>, <math>i=1, \ldots, p</math>, are [[affine transformation]]s, that is, of the form: <math>h_i(\mathbf{x}) = \mathbf{a_i}\cdot \mathbf{x} - b_i</math>, where <math>\mathbf{a_i}</math> is a vector and <math>b_i</math> is a scalar.
The feasible set <math>C</math> of the optimization problem consists of all points <math>\mathbf{x} \in \mathcal{D}</math> satisfying the inequality and the equality constraints. This set is convex because <math>\mathcal{D}</math> is convex, the [[sublevel set]]s of convex functions are convex, affine sets are convex, and the intersection of convex sets is convex.<ref name=":2" />{{
Many optimization problems can be equivalently formulated in this standard form. For example, the problem of maximizing a [[concave function]] <math>f</math> can be re-formulated equivalently as the problem of minimizing the convex function <math>-f</math>. The problem of maximizing a concave function over a convex set is commonly called a convex optimization problem.<ref>{{cite web | url=https://www.solver.com/convex-optimization | title=Optimization Problem Types - Convex Optimization | date=9 January 2011 }}</ref>
===Standard form with linear objective{{Anchor|linear}}===
In the standard form it is possible to assume, without loss of generality, that the objective function ''f'' is a [[linear function]]. This is because any program with a general objective can be transformed into a program with a linear objective by adding a single variable t and a single constraint, as follows
:<math>\begin{align}
Line 53:
==Special cases==
The following problem classes are all convex optimization problems, or can be reduced to convex optimization problems via simple transformations:<ref name="
{{cite journal |last1=Agrawal |first1=Akshay |last2=Verschueren |first2=Robin |last3=Diamond |first3=Steven |last4=Boyd |first4=Stephen |year=2018 |title=A rewriting system for convex optimization problems |url=https://web.stanford.edu/~boyd/papers/pdf/cvxpy_rewriting.pdf |journal=Control and Decision |volume=5 |issue=1 |pages=42–60 |arxiv=1709.04494 |doi=10.1080/23307706.2017.1397554 |s2cid=67856259}}</ref>
Line 69:
*[[Entropy maximization]] with appropriate constraints.
==Properties==
The following are useful properties of convex optimization problems:<ref name="rockafellar93">{{cite journal | author = Rockafellar, R. Tyrrell | title = Lagrange multipliers and optimality | journal = SIAM Review | volume = 35 | issue = 2 | year = 1993 | pages = 183–238 |url = http://web.williams.edu/Mathematics/sjmiller/public_html/105Sp10/handouts/Rockafellar_LagrangeMultAndOptimality.pdf | doi=10.1137/1035044| citeseerx = 10.1.1.161.7209}}</ref><ref name="
* every [[local minimum]] is a [[global minimum]];
Line 302:
== 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 name=":2" />{{
* [[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 |archive-url=https://web.archive.org/web/20151001185038/http://web.stanford.edu/~boyd/papers/pdf/cvx_applications.pdf |archive-date=2015-10-01 |access-date=12 Apr 2021}}</ref>
| |||