cvx Users’ Guide
for cvx version 1.1 (build 594)
Michael Grant
mcgrant@stanford.edu
Stephen Boyd
boyd@stanford.edu
Yinyu Ye
yyye@stanford.edu
March 3, 2008
1
Contents
1 Introduction 4
1.1 What is cvx? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 What is disciplined convex programming? . . . . . . . . . . . . . . . 4
1.3 About this version . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Feedback . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.5 What cvx is not . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2 A quick start 6
2.1 Least-squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Bound-constrained least-squares . . . . . . . . . . . . . . . . . . . . . 9
2.3 Other norms and functions . . . . . . . . . . . . . . . . . . . . . . . . 10
2.4 Other constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.5 An optimal trade-off curve . . . . . . . . . . . . . . . . . . . . . . . . 13
3 The basics 14
3.1 Data types for variables . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.2 Objective functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.3 Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.4 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.5 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.6 Dual variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4 The DCP ruleset 21
4.1 A taxonomy of curvature . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.2 Top-level rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.3 Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.4 Expression rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.5 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.6 Compositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.7 Monotonicity in nonlinear compositions . . . . . . . . . . . . . . . . . 27
4.8 Scalar quadratic forms . . . . . . . . . . . . . . . . . . . . . . . . . . 28
5 Semidefinite programming using cvx 29
6 Geometric programming using cvx 31
6.1 Top-level rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
6.2 Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
6.3 Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
7 Advanced topics 34
7.1 Adding new functions to the cvx atom library . . . . . . . . . . . . . 34
7.2 Solver selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
7.3 Controlling solver precision . . . . . . . . . . . . . . . . . . . . . . . . 38
7.4 Miscellaneous cvx commands . . . . . . . . . . . . . . . . . . . . . . 40
2
7.5 Assignments versus equality constraints . . . . . . . . . . . . . . . . . 40
7.6 Indexed dual variables . . . . . . . . . . . . . . . . . . . . . . . . . . 42
A Installation and compatability 44
A.1 Basic instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
A.2 MEX file compilaton . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
A.3 About SeDuMi and SD PT3 . . . . . . . . . . . . . . . . . . . . . . . 45
A.4 A Matlab 7.0 issue . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
B Operators, functions, and sets 46
B.1 Basic operators and linear functions . . . . . . . . . . . . . . . . . . . 46
B.2 Standard Matlab nonlinear functions . . . . . . . . . . . . . . . . . . 47
B.3 New nonlinear functions . . . . . . . . . . . . . . . . . . . . . . . . . 48
B.4 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
C cvx status messages 52
D The GP/SDP approximation 53
E The irrational power limitation 55
F Overdeter mined problems 56
G Acknowledgements 57
3
1 Introd uction
1.1 What is cvx?
cvx is a modeling system for discipli ned co nvex progra mming. Disciplined convex
programs, or DCPs, are convex optimization problems that adhere to a limited set
of construction rules, which enables them to be analyzed a nd solved efficiently. The
set of DCPs includes most well-known classes of convex programs, including linear
programs (LPs), quadratic programs (QPs), second-order cone programs (SOCPs),
and semidefinite programs (SDPs). cvx can solve problems from all of these problem
classes, and many others as well. For background on convex optimization, see the
book Convex Optimization [BV04].
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
expressed in a more natural form. In GP mode, cvx accepts all of the special functions
and combination rules of geometric programming, including monomials, posynomials,
and g eneralized posynomials [BKVH05], and transforms such problems into convex
form so that they can be solved efficiently.
cvx is implemented in Matlab [Mat04], effectively turning Matlab into an op-
timization modeling la ngua ge. 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 o ptimal trade-off curve by forming
and solving a family o f optimization problems by varying the constraints. As ano ther
example, cvx can be used as a compo nent of a larger system that uses convex opti-
mization, such as a branch and bound method, or an engineering design framework.
cvx was designed and implemented by Michael Grant, with input from Stephen
Boyd and Yinyu Ye [GBY06]. It incorpora t es ideas from earlier work by L¨ofberg
[L¨of05], Dahl and Vandenberghe [DV05], Crusius [Cru02], Wu and Boyd [WB00], and
many others. The modeling la nguage follows the spirit of AMPL [FGK99] or GAMS
[BKMR98]; unlike these 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.
1.2 What is disciplined convex programming?
The term disciplined conve x programming refers to a methodology for constructing
convex optimization pro blems proposed by Michael Grant, Stephen Boyd, and Yinyu
Ye [GBY06, Gra04]. The name was chosen to communicate the treatment of convex
programming as a distinct discipline, one in which convexity is an advance require-
ment. In other words, it is designed to support the formulation and construction of
optimization problems that the user intends from the outset to be convex.
4
Disciplined convex programming impo ses a limited set of conventions o r rules,
which we call the DCP ruleset. Problems which adhere to the ruleset can b e ra pidly
and automatically verified as convex and converted to solva ble form. Problems that
violate the ruleset are rejected, even when the problem is convex. That is not to say
that such problems cannot be solved; 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 a nalysis. 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 suppor t for nondifferen-
tiable functions. In practice, we have found that disciplined convex programs closely
resemble their natural mathematical f orms.
1.3 About this version
This version of cvx supports two core solvers, SeDuMi [Stu99] and SDPT3 [TTT06],
with the latter being the default. Both are open-source interior-point solvers written
in Matlab for LPs, SOCPs, SDPs, and combinations thereof. Future versions of cvx
will support other solvers, such as MOSEK [MOS05], CVXOPT [DV05], and a general
purpose solver we are developing.
Because SeDuMi and SDPT3 support only LPs, SOCPs, and SDPs, this version of
cvx can only handle functions and sets that can be represented using these problem
types. Despite this limitation, the current version of cvx includes a wide variety of
functions, such as minimums and maximums, absolute values and ℓ
p
norms, quadratic
forms and square roots, some fo rms of the power function x
p
, and the minimum and
maximum eigenvalues of a symmetric matrix. A few obscure functions have also been
included, such as the sum of the k lar gest entries of a vector, and the convex envelopes
of nonconvex polynomials. For a full list of functions supported by cvx, see Appendix
B. Geometric programs and the related log-sum-exp function are handled through a
novel approximation method that is described briefly in Appendix D.
Some useful functions that are not supp orted in the current version include ex-
ponential, log, and entropy. Support for such functions will likely require the use of
one of the new solvers mentio ned above, but we are also investigating approximation
methods similar to that developed for geometric programs.
1.4 Feedback
Any feedback and criticism you might have about this software would be greatly ap-
boyd@stanford.edu) with your comments. If you discover a bug, please include the
following in your communication:
• the cvx model and supporting data that caused the error;
• a copy of any error messages that it produced;
5
