|
|
|
|
Convex optimization
|
| |
|
| |
Convex optimization is a subfield of mathematical optimization. Given a real vector space together with a convex, real-valued function
defined on a convex subset of , the problem is to find the point in for which the number is smallest, i.e., the point such that for all .
The convexity of and 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.
Discussion
Ask a question about 'Convex optimization' Start a new discussion about 'Convex optimization' Answer questions from other users |
Encyclopedia
Convex optimization is a subfield of mathematical optimization. Given a real vector space together with a convex, real-valued function
defined on a convex subset of , the problem is to find the point in for which the number is smallest, i.e., the point such that for all .
The convexity of and 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.
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 to be minimized over the variable
- Inequality constraints of the form , where the functions are convex
- Equality constraints of the form , where the functions are affine. In practice, the terminology "linear" and "affine" are generally equivalent and most often expressed in the form , where is a matrix and is a vector.
A convex optimization problem is thus written as
minimize subject to
-
-
Examples
The following problems are all convex optimization problems, or can be transformed into convex optimization problems via a change of variables:
In a significant example, the set is defined by a system of inequalities involving m convex functions g1,
g2,
...,
gm defined on X,
like this:
The Lagrange function for the problem is
- L(x,λ0,...,λm) = λ0f(x) + λ1g1(x) + ... + λmgm(x).
For each point x in X that minimizes f over X, there exist real numbers λ0, ..., λm, called Lagrange multipliers,
that satisfy these conditions simultaneously:
- x minimizes L(y, λ0, λ1, ..., λm) over all y in X,
- λ0 ≥ 0, λ1 ≥ 0, ..., λm ≥ 0, with at least one λk>0,
- λ1g1(x) = 0, ... , λmgm(x) = 0
If there exists a "strictly feasible point", i.e., a point z satisfying
- g1(z) < 0,...,gm(z) < 0,
then the statement above can be upgraded to assert that λ0=1.
Conversely, if some x in X satisfies 1)-3) for scalars λ0, ..., λm with λ0 = 1, then x is certain to minimize f over X.
Methods
The following methods are used in solving convex optimization problems:
Software
Although most general-purpose nonlinear equation solvers such as , , , and work well, many software packages dealing exclusively with convex optimization problems are also available:
Convex programming languages
Convex optimization solvers
- (commercial, stand-alone software and Matlab interface)
- (commercial)
- (GPLv2, Matlab package)
- (GPLv2, Matlab package)
- [https://projects.coin-or.org/OBOE OBOE]
External links
- Stephen Boyd and Lieven Vandenberghe, (book in pdf)
- and , a Stanford course homepage
- , an MIT OCW course homepage
- Jon Dattorro, (book pdf)
- Haitham Hindi, This has an slight engineering focus but is written informally and at a very accessible level.
|
| |
|
|
