CONVEX OPTIMIZATION

'Convex optimization' is a subfield of mathematical optimization. Given a real vector space $X$ together with a convex, real-valued function
:$f:mathcal\{X\}\; o\; mathbb\; R$
defined on a convex subset $mathcal\{X\}$ of $X$, the problem is to find the point $x^$
★ in $mathcal\{X\}$ for which the number $f(x)$ is smallest.
The convexity of $mathcal\{X\}$ and $f$ make the powerful tools of convex analysis applicable: the Hahn-Banach theorem and the theory of subgradients lead to a particularly satisfying and complete theory of necessary and sufficient conditions for optimality, a duality theory comparable in perfection to that for linear programming, and effective computational methods. 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, data analysis and modeling, statistics, and finance. Modern computing power has improved the tractability of convex optimization problems to a level roughly equal to that of linear programming.

Contents

Theory

Standard form

Examples

Methods

Software

Convex programming languages

Convex optimization solvers

References

External links

Theory

The following statements are true about the convex optimization problem:

★ if a local minimum exists, then it is a global minimum

★ the set of all (global) minima is convex

★ if the function is strictly convex, then there exists at most one minimum
The theoretical framework for convex optimization uses the facts above in conjunction with notions from convex analysis such as the Hilbert projection theorem, the separating hyperplane theorem, and Farkas's lemma.

Standard form

''Standard form'' is the usual and most intuitive form of describing a convex optimization problem. It consists of the following three parts:

★ A 'convex function' $f\_0(x):\; mathbb\{R\}^n\; o\; mathbb\{R\}$ to be minimized over the variable $x$

★ 'Inequality constraints' of the form $f\_i(x)\; leq\; 0$, where the functions $f\_i$ are convex

★ 'Equality constraints' of the form $h\_i(x)\; =\; 0$, where the functions $h\_i$ are affine. In practice, the terminology "linear" and "affine" are generally equivalent and most often expressed in the form $Ax\; =\; b$, where $A$ is a matrix and $b$ is a vector.
A convex optimization problem is thus written as
minimize $f\_0(x)$ subject to
: $f\_i(x)\; leq\; 0,\; quad\; i\; =\; 1,dots,m$
: $h\_i(x)\; =\; 0,\; quad\; i\; =\; 1,\; dots,p$

Examples

The following problems are all convex optimization problems, or can be transformed into convex optimization problems via a change of variables:

★ Least squares

★ Linear programming

★ Conic optimization

★ Geometric programming

★ Second order cone programming

★ Semidefinite programming

★ Quadratically constrained quadratic programming

★ Entropy maximization
In a significant example, the set $mathcal\{X\}$ is defined by a system of inequalities involving ''m'' convex functions ''g''₁,
''g''₂,
...,
''g''_''m'' defined on ''X'',
like this:
:
ight
brace.
The Lagrange function for the problem is
:''L''(''x'',''λ''₀,...,''λ''_''m'') = ''λ''₀''f''(''x'') + ''λ''₁''g''₁(''x'') + ... + ''λ''_''m''''g''_''m''(''x'').
For each point ''x'' in ''A'' that minimizes ''f'' over ''A'', there exist real numbers ''λ''₀, ..., ''λ''_m, called Lagrange multipliers,
that satisfy these conditions simultaneously:
# ''x'' minimizes ''L''(''y'', λ₀, λ₁, ..., λ_m) over all ''y'' in ''X'',
# λ₀ ≥ 0, λ₁ ≥ 0, ..., λ_''m'' ≥ 0, with at least one λ_''k''>0,
# ''λ''₁''g''₁(''x'') = 0, ... , ''λ''_''m''''g''_''m''(''x'') = 0
If there exists a "strictly feasible point", i.e., a point ''z'' satisfying
:''g''₁(''z'') < 0,...,''g''_''m''(''z'') < 0,
then the statement above can be upgraded to assert that λ₀=1.
Conversely, if some ''x'' in ''A'' satisfies 1)-3) for scalars λ₀, ..., λ_''m'' with λ₀ = 1, then ''x'' is certain to minimize ''f'' over ''A''.

Methods

The following methods are used in solving convex optimization problems:

★ Ellipsoid method

★ Subgradient method

★ Cutting-plane methods

★ Interior-point methods

Software

Although most general-purpose nonlinear equation solvers such as LSSOL, LOQO, MINOS, and Lancelot work well, many software packages dealing exclusively with convex optimization problems are also available:

Convex programming languages

★ YALMIP

★ CVX

★ CVXOPT

Convex optimization solvers

★ MOSEK

★ solver.com

★ SeDuMi

References

★ Convex analysis, , R. T., Rockafellar, Princeton University Press, ,

★ Linear and Nonlinear Programming, , David, Luenberger, Addison-Wesley, ,

★ Optimization by Vector Space Methods, , David, Luenberger, Wiley & Sons, ,

★ Convex Analysis and Optimization, , Dimitri, Bertsekas, Athena Scientific, ,

★ Hiriart-Urruty, Jean-Baptiste, and Lemaréchal, Claude. (2004). ''Fundamentals of Convex analysis''. Berlin: Springer.

★ Borwein, Jonathan, and Lewis, Adrian. (2000). ''Convex Analysis and Nonlinear Optimization''. Springer.

★ {{cite book
| last = Berkovitz
| first = Leonard
| title = Convexity and Optimization in $mathbb\{R\}^n$
| publisher = John Wiley & Sons
| date = 2001
}}

★ Nonlinear Optimization, , Andrzej, Ruszczynski, Princeton University Press, ,

External links

★ Stephen Boyd and Lieven Vandenberghe, Convex Optimization (book in pdf)

★ EE364 and EE364b, a Stanford course homepage

★ 6.253, an MIT OCW course homepage

★ Jon Dattorro, Convex Optimization & Euclidean Distance Geometry