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 DCP-based 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 constant expression is
Any sum of constants and parameters.
A nonnegative expression is
Any nonnegative number.
Any parameter or variable marked as nonnegative.
Any sum of nonnegative expressions.
Any difference of a nonnegative and nonpositive expression.
The negation of a nonpositive expression.
(Similarly for nonpositive expressions.)
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.