Convex optimization

Convex optimization problem

The general form of an optimization problem (also referred to as a mathematical programming problem or minimization problem) is to find some x ∗ ∈ X such that

for some feasible set X ⊂ R n and objective function f ( x ) : R n → R . The optimization problem is called a convex optimization problem if X is a convex set and f ( x ) is a convex function defined on R n .

Alternatively, an optimization problem of the form

is called convex if the functions f , g 1 … g m : R n → R are all convex functions.

Theory

The following statements are true about the convex minimization problem:

These results are used by the theory of convex minimization along with geometric notions from functional analysis (in Hilbert spaces) 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 minimization problem is thus written as

Note that every equality constraint h ( x ) = 0 can be equivalently replaced by a pair of inequality constraints h ( x ) ≤ 0 and − h ( x ) ≤ 0 . 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, h i ( x ) ≤ 0 is convex, but − h i ( x ) ≤ 0 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:

Lagrange multipliers

Consider a convex minimization problem given in standard form by a cost function f ( x ) and inequality constraints g i ( x ) ≤ 0 for 1 ≤ i ≤ m . Then the domain X is:

The Lagrangian function for the problem is

For each point x in X that minimizes f over X , there exist real numbers λ 0 , λ 1 , … , λ m , called Lagrange multipliers, that satisfy these conditions simultaneously:

1. x minimizes L ( y , λ 0 , λ 1 , … , λ m ) over all y ∈ X ,
2. λ 0 , λ 1 , … , λ m ≥ 0 , with at least one λ k > 0 ,
3. λ 1 g 1 ( x ) = ⋯ = λ m g m ( x ) = 0 (complementary slackness).

If there exists a "strictly feasible point", that is, a point z satisfying

then the statement above can be strengthened to require 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

Convex minimization problems can be solved by the following contemporary methods:

Other methods of interest:

Subgradient methods can be implemented simply and so are widely used. Dual subgradient methods are subgradient methods applied to a dual problem. The drift-plus-penalty method is similar to the dual subgradient method, but takes a time average of the primal variables.

Convex minimization with good complexity: Self-concordant barriers

The efficiency of iterative methods is poor for the class of convex problems, because this class includes "bad guys" whose minimum cannot be approximated without a large number of function and subgradient evaluations; thus, to have practically appealing efficiency results, it is necessary to make additional restrictions on the class of problems. Two such classes are problems special barrier functions, first self-concordant barrier functions, according to the theory of Nesterov and Nemirovskii, and second self-regular barrier functions according to the theory of Terlaky and coauthors.

Quasiconvex minimization

Problems with convex level sets can be efficiently minimized, in theory. Yurii Nesterov proved that quasi-convex minimization problems could be solved efficiently, and his results were extended by Kiwiel. However, such theoretically "efficient" methods use "divergent-series" stepsize rules, which were first developed for classical subgradient methods. Classical subgradient methods using divergent-series rules are much slower than modern methods of convex minimization, such as subgradient projection methods, bundle methods of descent, and nonsmooth filter methods.

Solving even close-to-convex but non-convex problems can be computationally intractable. Minimizing a unimodal function is intractable, regardless of the smoothness of the function, according to results of Ivanov.

Convex maximization

Conventionally, the definition of the convex optimization problem (we recall) requires that the objective function f to be minimized and the feasible set be convex. In the special case of linear programming (LP), the objective function is both concave and convex, and so LP can also consider the problem of maximizing an objective function without confusion. However, for most convex minimization problems, the objective function is not concave, and therefore a problem and then such problems are formulated in the standard form of convex optimization problems, that is, minimizing the convex objective function.

For nonlinear convex minimization, the associated maximization problem obtained by substituting the supremum operator for the infimum operator is not a problem of convex optimization, as conventionally defined. However, it is studied in the larger field of convex optimization as a problem of convex maximization.

The convex maximization problem is especially important for studying the existence of maxima. 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. Such results, called "maximum principles", are useful in the theory of harmonic functions, potential theory, and partial differential equations.

The problem of minimizing a quadratic multivariate polynomial on a cube is NP-hard. In fact, in the quadratic minimization problem, if the matrix has only one negative eigenvalue, is NP-hard.

Extensions

Advanced treatments consider convex functions that can attain positive infinity, also; the indicator function of convex analysis is zero for every x ∈ X and positive infinity otherwise.

Extensions of convex functions include biconvex, pseudo-convex, and quasi-convex functions. Partial extensions of the theory of convex analysis and iterative methods for approximately solving non-convex minimization problems occur in the field of generalized convexity ("abstract convex analysis").