Disciplined Convex Programming and CVX

Convex Optimization > Convex sets | Convex functions | Convex optimization problems | Algorithms | DCP

For more details on disciplined convex programming, see here.

Basic idea
The ruleset
Example
Some do's and don'ts of CVX
Pros and cons of CVX

Basic idea

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

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

$g(x) = inf_{y in C} : f(x, y)$

is 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 f(x) := max( f_1(x),f_2(x)) le 1 , with f_1,f_2 convex functions in the library, then it adds two new convex constraints f_i(x) le t , i=1,2 , and replace the original constraint with t le 1 . This way, only ‘‘basic’’ constraints are to be handled when solving the problem.

Example

Consider the problem of sparse linear least-squares:

where $A in mathbf{R}^{m times n}$ , $b in mathbf{R}^m$ 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 z rightarrow z^Tz , which is part of the library. The second term is an l_1 -norm, and is also part of the library. CVX knows how to handle this norm, by introducing a new variable $t in mathbf{R}^n$ , replacing the norm by t_1+ldots+t_n , and adding the constraints -t_i le x_i le t_i , i=1,ldots,n . The problem is replaced with the equivalent form

$min_{x,z,t} : z^Tz + sum_{i=1}^n t_i ~:~ z = Ax-y, ;; -t_i le x_i le t_i, ;; i=1,ldots,n.$

Using an interior-point method amounts to handle the inequality constraints via a ‘‘barrier’’ term in the objective. The problem is further replaced with

$min_{x,z,t} : z^Tz +sum_{i=1}^n t_i - mu sum_{i=1}^n left( log(t_i-x_i) + log(t_i+x_i) right) ~:~ z = Ax-y,$

where mu>0 is a small parameter. A final step is to add extra variables to as to make sure the objective only contains basic functions:

$min_{x,z,t,u,v} : z^Tz +sum_{i=1}^n t_i - mu sum_{i=1}^n left( log(u_i) + log(v_i) right) ~:~ z = Ax-y, ;; u = t-x, ;; v = t+x.$

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.

Some do's and don'ts of CVX

Consider the following variation on the problem above:

where the l_1 -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 l_1 -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

Pros and cons of CVX

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.