Convex optimization, a subfield of mathematical optimization, studies the problem of minimizing convex functions over convex sets. Given a real vector space X together with a convex, real-valued function

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

for all .

The convexity of 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.

Convex optimization has applications beyond minimizing convex functions. Convex optimization is useful also for maximizing concave functions and for the theory of maximizing convex functions:

• The problem of maximizing a concave function can be re-formulated equivalently as a problem of minimizing a convex function.
• Consider the restriction of a convex function to a compact convex set: Then, on that set, the function attains its constrained maximum only on the boundary.^[1] Such results, called "maximum principles", are useful in the theory of harmonic functions, potential theory, and partial differential equations.

Contents 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 See also 8 References 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' 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 to be minimized over the variable x
• Inequality constraints of the form , 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 , where a_i and b_i are column-vectors..

A convex minimization problem is thus written as

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

Following from this fact, it is easy to understand why h_i(x) = 0 has to be affine as opposed to merely being convex. If h_i(x) is convex, is convex, but is concave. Therefore, the only way for h_i(x) = 0 to be convex is for h_i(x) to be affine.

Examples

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

• Least squares
• Linear programming
• Quadratic programming
• Conic optimization
• Geometric programming
• Second order cone programming
• Semidefinite programming
• Quadratically constrained quadratic programming
• Entropy maximization

Lagrange multipliers

Consider a convex minimization problem given in standard form by a cost function f(x) and inequality constraints , where . Then the domain is:

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:

1. x minimizes L(y, λ₀, λ₁, ..., λ_m) over all y in X,
2. λ₀ ≥ 0, λ₁ ≥ 0, ..., λ_m ≥ 0, with at least one λ_k>0,
3. λ₁g₁(x) = 0, ... , λ_mg_m(x) = 0 (complementary slackness).

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:^[2]

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

Other methods of interest:

• Cutting-plane methods
• Ellipsoid method
• Subgradient method

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

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

• YALMIP
• CVX
• CVXOPT
• CVXMOD

Convex minimization solvers

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

See also

• Convex analysis
• Convex function
• Convex set
• Interior-point method
• Karush–Kuhn–Tucker conditions
• Lagrange multiplier
• Linear programming
• Optimization problem
• Optimization theory
• Pseudoconvex function
• Quadratic programming
• Quasiconvex function (with convex lower level sets)
• Semidefinite programming
• Subgradient method

References

1. ^ Theorem 32.1 in Rockafellar's Convex Analysis states this maximum principle for extended real-valued functions.
2. ^ 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).
3. ^ 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. 

• Ruszczyński, 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 minimization Written for engineers, this overview states (without proofs) many important results and has illustrations. It may merit consultation before turning to Boyd and Vandenberghe's detailed but accessible textbook.
• Haitham Hindi, A Tutorial on convex minimization II: Duality and interior-point methods
• Brian Borchers, An Overview Of Software For convex minimization

v · d · Optimization: Algorithms, methods, and heuristics  Unconstrained nonlinear: Methods calling ... ... functions Golden section search · Interpolation methods · Line search · Successive parabolic interpolation ... and gradients Convergence Trust region · Wolfe conditions Quasi–Newton BFGS  · DFP  · L-BFGS  · Symmetric rank-one (SR1) Other methods Gauss–Newton · Gradient · Levenberg–Marquardt · Conjugate gradient ... and Hessians Newton's method  Constrained nonlinear General Barrier methods · Penalty methods Differentiable Augmented Lagrangian methods · Sequential quadratic programming · Successive linear programming  Convex minimization General Interior point method · Reduced gradient (Frank–Wolfe) · Subgradient method  · Cutting-plane method Linear and quadratic Interior point Ellipsoid method of Khachiyan  · Projective algorithm of Karmarkar  · Semidefinite programming Basis-exchange Simplex algorithm of Dantzig · Criss-cross algorithm · Principal pivoting algorithm of Lemke  Combinatorial Paradigms Approximation algorithm · Dynamic programming · Greedy algorithm · Integer programming (Branch & bound or cut) Graph algorithms Minimum spanning tree Bellman–Ford algorithm  · Borůvka · Dijkstra · Floyd–Warshall  · Johnson · Kruskal Network flows Dinic  · Edmonds–Karp  · Ford–Fulkerson  · Push-relabel maximum flow  Metaheuristics Evolutionary algorithm · Hill climbing · Local search · Simulated annealing · Tabu search Categories (Algorithms · Methods · Heuristics) · Software