Disciplined Convex Programming and CVX

Stephen Boyd
Electrical Engineering Department
Stanford University

Convex Optimization, Boyd & Vandenberghe

 Outline

• cone program solvers

• modeling systems

• disciplined convex programming

• CVX (CVXPY, Convex.jl)

Convex Optimization, Boyd & Vandenberghe 1

 Cone program solvers

• LP solvers
– many, open source and commercial
• cone solvers
– each handles combinations of a subset of LP, SOCP, SDP, EXP cones
– open source: SDPT3, SeDuMi, CVXOPT, CSDP, ECOS, SCS, . . .
– commercial: Mosek, Gurobi, Cplex, . . .
• you’ll write a basic cone solver later in the course

Convex Optimization, Boyd & Vandenberghe 2

 Transforming problems to cone form

• lots of tricks for transforming a problem into an equivalent cone program

– introducing slack variables
– introducing new variables that upper bound expressions

• these tricks greatly extend the applicability of cone solvers

• writing code to carry out this transformation is painful

• modeling systems automate this step

Convex Optimization, Boyd & Vandenberghe 3

 Modeling systems
a typical modeling system
• automates transformation to cone form; supports
– declaring optimization variables
– describing the objective function
– describing the constraints
– choosing (and configuring) the solver

• when given a problem instance, calls the solver

• interprets and returns the solver’s status (optimal, infeasible, . . . )

• (when solved) transforms the solution back to original form

Convex Optimization, Boyd & Vandenberghe 4

 Some current modeling systems

• AMPL & GAMS (proprietary)

– developed in the 1980s, still widely used in traditional OR
– no support for convex optimization
• YALMIP (‘Yet Another LMI Parser’, matlab)
– first object-oriented convex optimization modeling system
• CVX (matlab)
• CVXPY (python, GPL)
• Convex.jl (Julia, GPL, merging into JUMP)
• CVX, CVXPY, and Convex.jl collectively referred to as CVX*

Convex Optimization, Boyd & Vandenberghe 5

 Disciplined convex programming
• describe objective and constraints using expressions formed from
– a set of basic atoms (affine, convex, concave functions)
– a restricted set of operations or rules (that preserve convexity)

• modeling system keeps track of affine, convex, concave expressions

• rules ensure that

– expressions recognized as convex are convex
– but, some convex expressions are not recognized as convex

• problems described using DCP are convex by construction

• all convex optimization modeling systems use DCP

Convex Optimization, Boyd & Vandenberghe 6

 CVX

• uses DCP

• runs in Matlab, between the cvx_begin and cvx_end commands

• relies on SDPT3 or SeDuMi (LP/SOCP/SDP) solvers

• refer to user guide, online help for more info

• the CVX example library has more than a hundred examples

Convex Optimization, Boyd & Vandenberghe 7

 Example: Constrained norm minimization
A = randn(5, 3);
b = randn(5, 1);
cvx_begin
variable x(3);
minimize(norm(A*x - b, 1))
subject to
-0.5 <= x;
x <= 0.3;
cvx_end
• between cvx_begin and cvx_end, x is a CVX variable
• statement subject to does nothing, but can be added for readability
• inequalities are intepreted elementwise

Convex Optimization, Boyd & Vandenberghe 8

 What CVX does
after cvx_end, CVX
• transforms problem into an LP
• calls solver SDPT3
• overwrites (object) x with (numeric) optimal value
• assigns problem optimal value to cvx_optval
• assigns problem status (which here is Solved) to cvx_status
(had problem been infeasible, cvx_status would be Infeasible and x
would be NaN)

Convex Optimization, Boyd & Vandenberghe 9

 Variables and affine expressions
• declare variables with variable name[(dims)] [attributes]
– variable x(3);
– variable C(4,3);
– variable S(3,3) symmetric;
– variable D(3,3) diagonal;
– variables y z;
• form affine expressions
– A = randn(4, 3);
– variables x(3) y(4);
– 3*x + 4
– A*x - y
– x(2:3)
– sum(x)

Convex Optimization, Boyd & Vandenberghe 10

 Some functions
function meaning attributes
norm(x, p) kxkp cvx
square(x) x2 cvx
square_pos(x) (x+)2 cvx, nondecr
pos(x) x+ cvx, nondecr
sum_largest(x,k) x[1] + · · · + x[k] cvx, nondecr
√
sqrt(x) x (x ≥ 0) ccv, nondecr
inv_pos(x) 1/x (x > 0) cvx, nonincr
max(x) max{x1, . . . , xn} cvx, nondecr
quad_over_lin(x,y) x2/y (y > 0) cvx, nonincr in y
lambda_max(X) λmax(X) (X = X T ) cvx
 2
x , |x| ≤ 1
huber(x) cvx
2|x| − 1, |x| > 1

Convex Optimization, Boyd & Vandenberghe 11

 Composition rules

• can combine atoms using valid composition rules, e.g.:

– a convex function of an affine function is convex
– the negative of a convex function is concave
– a convex, nondecreasing function of a convex function is convex
– a concave, nondecreasing function of a concave function is concave

Convex Optimization, Boyd & Vandenberghe 12

 Composition rules — multiple arguments

• for convex h, h(g1, . . . , gk ) is recognized as convex if, for each i,

– gi is affine, or
– gi is convex and h is nondecreasing in its ith arg, or
– gi is concave and h is nonincreasing in its ith arg

• for concave h, h(g1, . . . , gk ) is recognized as concave if, for each i,

– gi is affine, or
– gi is convex and h is nonincreasing in ith arg, or
– gi is concave and h is nondecreasing in ith arg

Convex Optimization, Boyd & Vandenberghe 13

 Valid (recognized) examples
u, v, x, y are scalar variables; X is a symmetric 3 × 3 variable
• convex:
– norm(A*x - y) + 0.1*norm(x, 1)
– quad_over_lin(u - v, 1 - square(v))
– lambda_max(2*X - 4*eye(3))
– norm(2*X - 3, ’fro’)

• concave:
– min(1 + 2*u, 1 - max(2, v))
– sqrt(v) - 4.55*inv_pos(u - v)

Convex Optimization, Boyd & Vandenberghe 14

 Rejected examples
u, v, x, y are scalar variables
• neither convex nor concave:
– square(x) - square(y)
– norm(A*x - y) - 0.1*norm(x, 1)

• rejected due to limited DCP ruleset:

– sqrt(sum(square(x))) (is convex; could use norm(x))
– square(1 + x^2) (is convex; could use square_pos(1 + x^2), or
1 + 2*pow_pos(x, 2) + pow_pos(x, 4))

Convex Optimization, Boyd & Vandenberghe 15

 Sets

• some constraints are more naturally expressed with convex sets

• sets in CVX work by creating unnamed variables constrained to the set

• examples:
– semidefinite(n)
– nonnegative(n)
– simplex(n)
– lorentz(n)

• semidefinite(n), say, returns an unnamed (symmetric matrix)

variable that is constrained to be positive semidefinite

Convex Optimization, Boyd & Vandenberghe 16

 Using the semidefinite cone
variables: X (symmetric matrix), z (vector), t (scalar)
constants: A and B (matrices)
• X == semidefinite(n)
– means X ∈ Sn+ (or X  0)

• A*X*A’ - X == B*semidefinite(n)*B’
– means ∃ Z  0 so that AXAT − X = BZB T

• [X z; z’ t] == semidefinite(n+1)
 
X z
– means 0
zT t

Convex Optimization, Boyd & Vandenberghe 17

 Objectives and constraints

• objective can be
– minimize(convex expression)
– maximize(concave expression)
– omitted (feasibility problem)

• constraints can be
– convex expression <= concave expression
– concave expression >= convex expression
– affine expression == affine expression
– omitted (unconstrained problem)

Convex Optimization, Boyd & Vandenberghe 18

 More involved example
A = randn(5);
A = A’*A;
cvx_begin
variable X(5, 5) symmetric;
variable y;
minimize(norm(X) - 10*sqrt(y))
subject to
X - A == semidefinite(5);
X(2,5) == 2*y;
X(3,1) >= 0.8;
y <= 4;
cvx_end

Convex Optimization, Boyd & Vandenberghe 19

 Defining new functions
• can make a new function using existing atoms

• example: the convex deadzone function


 0,
 |x| ≤ 1
f (x) = max{|x| − 1, 0} = x − 1, x > 1
 1 − x, x < −1


• create a file deadzone.m with the code

function y = deadzone(x)
y = max(abs(x) - 1, 0)

• deadzone makes sense both within and outside of CVX

Convex Optimization, Boyd & Vandenberghe 20

 Defining functions via incompletely specified problems
• suppose f0, . . . , fm are convex in (x, z)
• let φ(x) be optimal value of convex problem, with variable z and
parameter x

minimize f0(x, z)
subject to fi(x, z) ≤ 0, i = 1, . . . , m
A 1 x + A2 z = b

• φ is a convex function
• problem above sometimes called incompletely specified since x isn’t
(yet) given
• an incompletely specified concave maximization problem defines a
concave function

Convex Optimization, Boyd & Vandenberghe 21

 CVX functions via incompletely specified problems
implement in cvx with
function cvx_optval = phi(x)
cvx_begin
variable z;
minimize(f0(x, z))
subject to
f1(x, z) <= 0; ...
A1*x + A2*z == b;
cvx_end
• function phi will work for numeric x (by solving the problem)

• function phi can also be used inside a CVX specification, wherever a

convex function can be used

Convex Optimization, Boyd & Vandenberghe 22

 Simple example: Two element max
• create file max2.m containing

function cvx_optval = max2(x, y)

cvx_begin
variable t;
minimize(t)
subject to
x <= t;
y <= t;
cvx_end

• the constraints define the epigraph of the max function

• could add logic to return max(x,y) when x, y are numeric
(otherwise, an LP is solved to evaluate the max of two numbers!)

Convex Optimization, Boyd & Vandenberghe 23

 A more complex example

• f (x) = x + x1.5 + x2.5, with dom f = R+, is a convex, monotone

increasing function

• its inverse g = f −1 is concave, monotone increasing, with dom g = R+

• there is no closed form expression for g

• g(y) is optimal value of problem

maximize t
subject to t+ + t1.5 2.5
+ + t+ ≤ y

(for y < 0, this problem is infeasible, so optimal value is −∞)

Convex Optimization, Boyd & Vandenberghe 24

• implement as
function cvx_optval = g(y)
cvx_begin
variable t;
maximize(t)
subject to
pos(t) + pow_pos(t, 1.5) + pow_pos(t, 2.5) <= y;
cvx_end

• use it as an ordinary function, as in g(14.3), or within CVX as a

concave function:
cvx_begin
variables x y;
minimize(quad_over_lin(x, y) + 4*x + 5*y)
subject to
g(x) + 2*g(y) >= 2;
cvx_end

Convex Optimization, Boyd & Vandenberghe 25

 Example

• optimal value of LP

f (c) = inf{cT x | Ax  b}

is concave function of c

• by duality (assuming feasibility of Ax  b) we have

f (c) = sup{−λT b | AT λ + c = 0, λ  0}

Convex Optimization, Boyd & Vandenberghe 26

• define f in CVX as

function cvx_optval = lp_opt_val(A,b,c)

cvx_begin
variable lambda(length(b));
maximize(-lambda’*b);
subject to
A’*lambda + c == 0; lambda >= 0;
cvx_end

• in lp opt val(A,b,c) A, b must be constant; c can be affine

Convex Optimization, Boyd & Vandenberghe 27

 CVX hints/warnings

• watch out for = (assignment) versus == (equality constraint)

• X >= 0, with matrix X, is an elementwise inequality
• X >= semidefinite(n) means: X is elementwise larger than some
positive semidefinite matrix (which is likely not what you want)
• writing subject to is unnecessary (but can look nicer)
• many problems traditionally stated using convex quadratic forms can
posed as norm problems (which can have better numerical properties):
x’*P*x <= 1 can be replaced with norm(chol(P)*x) <= 1

Convex Optimization, Boyd & Vandenberghe 28