cvx Users’ Guide
for cvx version 1.22
∗
Michael Grant
mcg@cvxr.com
Stephen Boyd
boyd@stanford.edu
February, 2012
∗
code commit 829, 2012-02-01 10:10:26; doc comm it 827, 2012-02-01 09:48:08
1
Contents
1 Introduction 4
1.1 What is cvx? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 What is disciplined convex programming? . . . . . . . . . . . . . . . 5
1.3 About this version . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Feedback . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.5 What cvx is not . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2 A quick start 8
2.1 Least-squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Bound-constrained least-squares . . . . . . . . . . . . . . . . . . . . . 10
2.3 Other norms and functions . . . . . . . . . . . . . . . . . . . . . . . . 11
2.4 Other constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.5 An optimal trade-off curve . . . . . . . . . . . . . . . . . . . . . . . . 15
3 The basics 17
3.1 cvx
begin and cvx end . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.2 Data types for variables . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.3 Objective functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.4 Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.5 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.6 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.7 Dual variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.8 Expression holders . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4 The DCP ruleset 25
4.1 A taxonomy of curvature . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.2 Top-level rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.3 Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.4 Expression rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.5 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.6 Compositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.7 Monotonicity in nonlinear compositions . . . . . . . . . . . . . . . . . 31
4.8 Scalar quadratic forms . . . . . . . . . . . . . . . . . . . . . . . . . . 32
5 Adding new functions to the cvx ato m library 34
5.1 New functions via the DCP ruleset . . . . . . . . . . . . . . . . . . . 34
5.2 New functions via partially specified problems . . . . . . . . . . . . . 35
6 Semidefinite programmi ng using cvx 39
7 Geometric programm ing using cvx 41
7.1 Top-level rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
7.2 Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
7.3 Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2
8 Advanced topics 44
8.1 Solver selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
8.2 Controlling solver precision . . . . . . . . . . . . . . . . . . . . . . . . 44
8.3 Miscellaneous cvx commands . . . . . . . . . . . . . . . . . . . . . . 46
8.4 Assignments versus equality constraints . . . . . . . . . . . . . . . . . 47
8.5 Indexed dual variables . . . . . . . . . . . . . . . . . . . . . . . . . . 48
A Installation and compatibility 51
A.1 Basic instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
A.2 About SeDuMi and SDPT3 . . . . . . . . . . . . . . . . . . . . . . . 52
A.3 A Matlab 7.0 issue . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
B Operators, functions, and sets 54
B.1 Basic operators and linear functions . . . . . . . . . . . . . . . . . . . 54
B.2 Nonlinear functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
B.3 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
C cvx status messages 63
D Advanced solver topics 65
D.1 The successive approximation method . . . . . . . . . . . . . . . . . . 65
D.2 Irrational powers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
D.3 Overdetermined problems . . . . . . . . . . . . . . . . . . . . . . . . 66
E Acknowledgements 67
3
1 Introduction
1.1 What is cvx?
cvx is a modeling system for disciplined convex programming. Disciplined convex pro-
grams, or DCPs, are convex optimization problems that are described using a limited
set of construction rules, which enables them to be analyzed and solved efficiently.
cvx can solve standard problems such as linear programs (LPs), quadratic programs
(QPs), second-order cone programs (SOCPs), and semidefinite programs (SDPs);
but compared to directly using a solver for one or these types of problems, cvx can
greatly simplify the task of specifying the problem. cvx can also solve much more
complex convex optimization problems, including many involving nondifferentiable
functions, such as `
1
norms. You can use cvx to conveniently formulate and solve
constrained norm minimization, entropy maximization, determinant maximization,
and many other problems.
To use cvx effectively, you need to know at least a bit about convex optimiza-
tion. For background on convex optimization, see the book Convex Optimization
[BV04], available on-line at www.stanford.edu/
∼
boyd/cvxbook/, or the Stanford
course EE364A, available at www.stanford.edu/class/ee364a/.
cvx is implemented in Matlab [Mat04], effectively turning Matlab into an op-
timization modeling language. Model specifications are constructed using common
Matlab operations and functions, and standard Matlab code can be freely mixed with
these specifications. This combination makes it simple to perform the calculations
needed to form optimization problems, or to process the results obtained from their
solution. For example, it is easy to compute an optimal trade-off curve by forming
and solving a family of optimization problems by varying the constraints. As another
example, cvx can be used as a component of a larger system that uses convex opti-
mization, such as a branch and bound method, or an engineering design framework.
cvx also provides special modes to simplify the construction of problems from two
specific problem classes. In SDP mode, cvx applies a matrix interpretation to the
inequality operator, so that linear matrix inequalities (LMIs) and SDPs may be ex-
pressed in a more natural form. In GP mode, cvx accepts all of the special functions
and combination rules of geometric programming, including monomials, posynomi-
als, and generalized posynomials, and transforms such problems into convex form
so that they can be solved efficiently. For background on geometric programming,
see the tutorial paper [BKVH05], available at www.stanford.edu/
∼
boyd/papers/
gp
tutorial.html.
cvx was designed by Michael Grant and Stephen Boyd, with input from Yinyu Ye;
and was implemented by Michael Grant [GBY06]. It incorporates ideas from earlier
work by L¨ofberg [L¨of05], Dahl and Vandenberghe [DV05], Crusius [Cru02], Wu and
Boyd [WB00], and many others. The modeling language follows the spirit of AMPL
[FGK99] or GAMS [BKMR98]; unlike thes e packages, however, cvx was designed
from the beginning to fully exploit convexity. The specific method for implementing
cvx in Matlab draws heavily from YALMIP [L¨of05]. We also hope to develop versions
of cvx for other platforms in the future.
4
1.2 What is disciplined convex programming?
Disciplined convex programming is a methodology for constructing convex optimiza-
tion problems proposed by Michael Grant, Stephen Boyd, and Yinyu Ye [GBY06,
Gra04]. It is meant to support the f ormulation and construction of optimization
problems that the user intends from the outset to be convex. Disciplined convex
programming imposes a set of conventions or rules, which we call the DCP ruleset.
Problems which adhere to the ruleset can be rapidly and automatically verified as
convex and converted to solvable form. Problems that violate the ruleset are rejected,
even when the problem is convex. That is not to say that s uch problems cannot be
solved using DCP; they just need to be rewritten in a way that conforms to the DCP
ruleset.
A detailed description of the DCP ruleset is given in §4, and it is important for
anyone who intends to actively use cvx to understand it. The ruleset is simple to
learn, and is drawn from basic principles of convex analysis. In return for accept-
ing the restrictions imposed by the ruleset, we obtain considerable benefits, such as
automatic conversion of problems to solvable form, and full support for nondifferen-
tiable functions. In practice, we have found that disciplined convex programs closely
resemble their natural mathematical forms.
1.3 About this version
Supported solvers. This version of cvx supports two core solvers, SeDuMi [Stu99]
and SDPT3 [TTT06], which is the default. Future versions of cvx may support other
solvers, such as MOSEK [MOS05] or CVXOPT [DV05]. SeDuMi and SDPT3 are
open-source interior-point solvers written in Matlab for LPs, SOCPs, SDPs, and
combinations thereof.
Problems handled exactly. cvx will convert the specified problem to an LP,
SOCP, or SDP, when all the functions in the problem specification can be represented
in these forms. This includes a wide variety of functions, such as minimum and
maximum, absolute value, quadratic forms, the minimum and maximum eigenvalues
of a symmetric matrix, power functions x
p
, and `
p
norms (both for p rational).
Problems handled with (good) approximations. For a few functions, cvx will
make a (good) approximation to transform the specified problem to one that can
be handled by a combined LP, SOCP, and SDP solver. For example, when a power
function or `
p
-norm is used, with non-rational exponent p, cvx replaces p with a
nearby rational. The log of the normal cumulative distribution log Φ(x) is replaced
with an SDP-compatible approximation.
Problems handled with successive approximation. This version of cvx adds
support for a number of functions that cannot be exactly repres ented via LP, SOCP, or
SDP, including log, exp, log-sum-exp log(exp x
1
+···+exp x
n
), entropy, and Kullback-
Leibler divergence. These problems are handled by solving a sequence (typically just
5
