If an optimization problem turns out to be convex, special-purpose algorithms can be used to solve it efficiently. The difficulty for the modeler is that proving convexity of a problem is a very hard task in general. There is no magic tool that allows a user to plug in any optimization problem and hope that the tool recognizes convexity and exploits it in the solution method.
In disciplined convex programming, the set of problems that are allowed is restricted: problems are constructed as convex from the outset. Hence, convexity verification is automatic. In the software package CVX, the objective and constraint functions that are allowed are built from a library of basic examples of convex functions. Calculus rules or transformations then allow to handle functions beyond the ones in the library.
The ruleset corresponds to the operations that preserve convexity, and includes the following.
Sum: if and are convex, so is .
Affine composition: if is convex, and is a matrix and a vector of compatible size, so is .
Pointwise maximum: if are convex, so is .
Partial minimization: if is convex, and is convex, then the function with values
is convex. (See for example the case when is quadratic and convex.)
Composition: if h is convex and increasing, and f is convex, then is convex (there are several similar composition rules).
For example, if CVX encounters a constraint of the form
with convex functions in the library, then it adds two new convex constraints
and replaces the original constraint with . This way, only ‘‘basic’’ constraints are to be handled when solving the problem.
Consider the problem of sparse linear least-squares:
where , are given. A CVX code for solving this is almost a verbatim version of the above:CVX syntax
% input: mxn data matrix A, m-vector y % output: optimal solution x in Rn cvx_begin variable x(n,1) minimize( (A*x-y)'*(A*x-y) + norm(x,1) ) cvx_end
CVX recognizes the first term as an affine composition involving the squared function , which is part of the library. The second term is an -norm, and is also part of the library. CVX knows how to handle this norm, by introducing a new variable , replacing the norm by , and adding the constraints , . The problem is replaced with the equivalent form
Using an interior-point method amounts to handle the inequality constraints via a ‘‘barrier’’ term in the objective. The problem is further replaced with
where is a small parameter. A final step is to add extra variables to as to make sure the objective only contains basic functions:
The problem above has linear equality constraints only. It involves an objective function given as a sum of functions that are in the library only. Hence, its gradient and hessian (the objects needed to implement an interior-point method) can be easily derived from those of functions in the library.
Consider the following variation on the problem above:
where the -norm is squared.
We can be tempted to write the above problem in CVX as follows.A wrong CVX implementation
cvx_begin variable x(n,1) minimize( (A*x-y)'*(A*x-y) + norm(x,1)^2 ) cvx_end
However, CVX will fail with this expression of the problem, as it cannot recognize the convexity of the squared -norm function as written. The reason is that the square of a convex function is only convex if that function is non-negative. To square a convex function that is non-negative, we use the square_pos function.CVX implementation
cvx_begin variable x(n,1) minimize( (A*x-y)'*(A*x-y) + square_pos(norm(x,1)) ) end cvx_end
This approach does restrict the available models:
We can't just call a convex optimization solver, hoping for the best; convex optimization is not a ‘‘plug & play’’ or ‘‘try my code’’ method;
we can't just type in a problem description, hoping it's convex, and that a sophisticated analysis tool will recognize it.
The good news are:
by learning and following a modest set of atoms and rules, we can specify a problem in a form very close to its natural mathematical form.
We can simultaneously verify convexity of problem, automatically generate an equivalent problem that is compatible with an interior-point method solver.