cvx Users’ Guide
for cvx version 1.2 (build 711)
Michael Grant
mcgrant@stanford.edu
Stephen Boyd
boyd@stanford.edu
February 19, 200 9
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 Data types for variables . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.2 Objective functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.3 Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.4 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.5 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.6 Dual variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.7 Expression holders . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4 The DCP ruleset 25
4.1 A taxonomy of curva ture . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.2 To p-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 atom library 34
5.1 New functions via t he DCP ruleset . . . . . . . . . . . . . . . . . . . 34
5.2 New functions via pa rt ia lly specified problems . . . . . . . . . . . . . 35
6 Semidefinite programming using cvx 39
7 Geometric programming using cvx 41
7.1 To p-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 . . . . . . . . . . . . . . . . . 46
8.5 Indexed dual variables . . . . . . . . . . . . . . . . . . . . . . . . . . 48
A Installation and compatability 50
A.1 Basic instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 0
A.2 MEX file compilation . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
A.3 About SeDuMi and SD PT3 . . . . . . . . . . . . . . . . . . . . . . . 51
A.4 A Matlab 7.0 issue . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
B Operators, functions, and sets 53
B.1 Basic operators and linear functions . . . . . . . . . . . . . . . . . . . 53
B.2 Nonlinear functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
B.3 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
C cvx status messages 61
D Advanced solver t opics 63
D.1 The successive approximation method . . . . . . . . . . . . . . . . . . 63
D.2 Irrational powers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
D.3 Overdetermined problems . . . . . . . . . . . . . . . . . . . . . . . . 64
E Acknowledgements 65
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 progr ams
(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 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 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 compo nent of a larger system that uses convex opti-
mization, such as a branch and bound method, or a n 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 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 f uture.
4
1.2 What is disciplined convex programming?
Disciplined convex prog ramming 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 formulation 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 a uto matically 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 such 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
Suppor ted 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-po int 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 f orms. This includes a wide variety of functions, such as minimum and
maximum, absolute value, quadratic fo rms, 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 rat io nal. 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
suppo r t for a number of functions that cannot be exactly represented 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
- 1
- 2
- 3
- 4
- 5
前往页