Convex optimization: Information from Answers.com

Convex optimization is a subfield of mathematical optimization, which is concerned with minimizing convex functions. Given a real vector space $X$ together with a convex, real-valued function

$f:\mathcal{X}\to \mathbb{R}$

defined on a convex subset $\mathcal{X}$ of $X$ , the problem is to find a point $x *$ in $\mathcal{X}$ for which the number $f (x)$ is smallest, i.e., a point $x *$ such that $f(x^*) \le f(x)$ for all $x \in \mathcal{X}$ .

The convexity of $\mathcal{X}$ and $f$ makes the powerful tools of convex analysis applicable: the Hahn–Banach theorem and the theory of subgradients lead to a particularly satisfying theory of necessary and sufficient conditions for optimality, a duality theory generalizing that for linear programming, and effective computational methods.

Convex minimization 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 (optimal design), and finance. With recent improvements in computing and in optimization theory, convex minimization is nearly as straightforward as linear programming.

1 Theory
2 Standard form
3 Examples
4 Lagrange multipliers
5 Methods
6 Software
- 6.1 Convex programming languages
- 6.2 Convex minimization solvers
7 References
8 See also
9 External links

Theory

The following statements are true about the convex minimization problem:

if a local minimum exists, then it is a global minimum.
the set of all (global) minima is convex.
for each strictly convex function, if the function has a minimum, then the minimum is unique.

These results are used by the theory of convex minimization along with geometric notions from functional 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 minimization problem. It consists of the following three parts:

A convex function $f(x): \mathbb{R}^n \to \mathbb{R}$ to be minimized over the variable $x$
Inequality constraints of the form $g_i(x) \leq 0$ , where the functions $g i$ are convex
Equality constraints of the form $h i (x) = 0$ , where the functions $h i$ are affine. In practice, the terms "linear" and "affine" are often used interchangeably. Such constraints can be expressed in the form $h i (x) = A x + b$ , where $A$ is a matrix and $b$ is a vector.

A convex minimization problem is thus written as

minimize $f (x)$ subject to

$g_i(x) \leq 0, \quad i = 1,\dots,m$

$h_i(x) = 0, \quad i = 1, \dots,p$

Note that every equality constraint $h (x) = 0$ can be equivalently replaced by a pair of inequality constraints $h(x)\leq 0$ and $-h(x)\leq 0$ . Therefore, for theoretical purposes, equality constraints are redundant; however, it can be beneficial to treat them specially in practice.

Examples

Hierarchical representation of common convex minimization problems

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

Lagrange multipliers

Consider a convex minimization problem given in standard form by a cost function $f (x)$ and inequality constraints $g_i(x)\leq 0$ , where $i=1\ldots m$ . Then the domain $\mathcal{X}$ is:

$\mathcal{X} = \left\lbrace{x\in X \vert g_1(x)\le0, \ldots, g_m(x)\le0}\right\rbrace.$

The Lagrangian function for the problem is

L(x,λ₀,...,λ_m) = λ₀f(x) + λ₁g₁(x) + ... + λ_mg_m(x).

For each point x in X that minimizes f over X, 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, ... , λ_mg_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 X satisfies 1-3 for scalars λ₀, ..., λ_m with λ₀ = 1, then x is certain to minimize f over X.

Methods

Convex minimization problems can be solved by the following contemporary methods^[1]:

"Bundle methods" (Wolfe, Lemaréchal), and
"Subgradient projection" methods (Polyak),
Interior-point methods (Nemirovskii and Nesterov).

Other methods of interest:

Subgradient methods can be implemented simply and so are widely used.^[2]

Software

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

Convex programming languages

Convex minimization solvers

MOSEK (commercial, stand-alone software and Matlab interface)
solver.com (commercial)
SeDuMi (GPLv2, Matlab package)
SDPT3 (GPLv2, Matlab package)
OBOE

References

^ For methods for convex minimization, see the volumes by Hiriart-Urruty and Lemaréchal (bundle) and the textbooks by Ruszczynski and Boyd and Vandenberghe (interior point).
^ Bertsekas

Bertsekas, Dimitri (2003). Convex Analysis and Optimization. Athena Scientific.

Boyd, Stephen and Vandenberghe, Lieven (2004). Convex Optimization. Cambridge University Press. http://www.stanford.edu/~boyd/cvxbook/. (book in pdf)

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

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

Luenberger, David (1984). Linear and Nonlinear Programming. Addison-Wesley.

Luenberger, David (1969). Optimization by Vector Space Methods. Wiley & Sons.

Rockafellar, R. T. (1970). Convex analysis. Princeton: Princeton University Press.

Ruszczynski, Andrzej (2006). Nonlinear Optimization. Princeton University Press.

External links

Stephen Boyd and Lieven Vandenberghe, Convex Optimization (book in pdf)
EE364a and EE364b, a Stanford course homepage
6.253, an MIT OCW course homepage
Haitham Hindi, A Tutorial on Convex Optimization This has an slight engineering focus but is written informally and at a very accessible level.
Haitham Hindi, A Tutorial on Convex Optimization II: Duality and Interior Point Methods This considers further issues for convex optimization

This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)

Donate to Wikimedia

	What is a convex octagon? Read answer...
	What is a convex figure? Read answer...
	What is the opposite of Convex? Read answer...

	Defferentiate a convex from a non-convex?
	Difference of non convex and convex?
	What is convex quadrilateral?

Convex optimization

Contents