Convex optimization

From Wikipedia, the free encyclopedia

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

$f:A\to \mathbb R$

defined on a convex subset A of X, the problem is to find the point x in A for which the number f(x) is smallest.

The convexity of A and f makes 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.

1 Properties
2 Example
3 External links
4 References

[edit] Properties

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

[edit] Example

In a significant example, the set A is defined by a system of inequalities involving m convex functions g₁, g₂, ..., g_m defined on X, like this:

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

The Lagrange function for the problem is

L(x,λ₀,...,λ_m) = λ₀f(x) + λ₁g₁(x) + ... + λ_mg_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: