Convexity
CVXGEN works for problems that it can transform to quadratic programs. It uses
the disciplined convex
programming (DCP) approach to guarantee the accuracy and validity of its
automatic transformations. Expressions are checked to see whether they are
affine, convex, concave or unknown, and positive, negative or unknown.
Compositions are only allowed when CVXGEN can guarantee convexity.
Some examples
In each example below, x and y are optimization variables.
 2*x
Affine in x.
 abs(2*x)
Convex in x.
Convex function of affine function.
 sum(square(x))
Convex in x.
Increasing convex (in fact, increasing affine) function of convex function.
 abs(2*x) + sum(square(x))
Convex in x.
Sum of two convex functions.
 max(abs(x) + pos(x))
Convex in x.
Convex, nondecreasing function of convex functions.
 square(pos(x))
Convex in x. The
square function is convex and increasing when its argument is positive. The
pos function is convex.
 a*quad(2*x + 3, Q)
Convex in x, if
a is marked nonnegative and Q is marked psd.
 quad(abs(x) + 1, Q)
Convex in x,
if Q is marked psd and positive. This is
because quad is convex if Q is psd, and nondecreasing if both arguments
are positive, and abs(x)  1 is convex.
 square(2  pos(x))
Not convex in x.
Invalid composition.
 abs(x + pos(x))
Not known convex in x.
This function is convex, but CVXGEN cannot recognize it as such via DCP. This
is because abs is only nondecreasing when its domain is positive. In this
case, x + pos(x) is not positive, so the composition rules do not hold.
For more examples, see the CVX user
guide, 4. (CVX is DCPbased convex optimization
modeling software for Matlab.)
Convex calculus
CVXGEN keeps track of the curvature, monotonicity and sign of expressions, where
possible. Following the CVX user guide,
which has similar rules, we have the following classifications. For
completeness, here is a list of the rules CVXGEN applies. When we use terms like
‘affine’, ‘convex’, ‘nonnegative’ etc, we mean ‘verified by CVXGEN to be
affine’. For example, square(x + 1)  square(x) is affine, but is not
recognised as affine by CVXGEN.
A affine expression is
A constant expression.
An optimization variable.
The product of any constant expression and a affine expression.
Any affine function of a affine expression.
A convex expression is
Any affine expression.
A convex function of an affine expression. Example: abs(x).
The sum of multiple convex expressions.
The product of a nonnegative affine expression and a convex expression.
The product of a nonpositive affine expression and a concave expression.
The composition of a convex, nondecreasing function and a convex expression.
(This includes sign information; for example square is known nondecreasing
on its positive domain.)
The composition of a convex, nonincreasing function and a concave expression.
A concave expression is
Any affine expression.
A concave function of an affine expression. Example: min(x).
The sum of multiple concave expressions.
The product of a nonnegative affine expression and a concave expression.
The product of a nonpositive affine expression and a convex expression.
The composition of a concave, nondecreasing function and a concave
expression.
The composition of a concave, nonincreasing function and a convex expression.
