第1页 / 共72页
第2页 / 共72页
第3页 / 共72页
第4页 / 共72页
第5页 / 共72页
第6页 / 共72页
第7页 / 共72页
第8页 / 共72页
凸优化CVX工具箱使用教程.pdf
cvx Users’ Guide
for cvx version 1.21 ∗
Michael Grant
Stephen Boyd
mcgrant@stanford.edu
boyd@stanford.edu
April, 2011
∗code commit 808, 2011-04-17 21:43:47; doc commit 806, 2011-02-25 11:00:44
1
Contents
1 Introduction
1.1 What is cvx? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 What is disciplined convex programming?
. . . . . . . . . . . . . . .
1.3 About this version . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4 Feedback . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5 What cvx is not . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2 A quick start
2.1 Least-squares
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Bound-constrained least-squares . . . . . . . . . . . . . . . . . . . . .
2.3 Other norms and functions . . . . . . . . . . . . . . . . . . . . . . . .
2.4 Other constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.5 An optimal trade-off curve . . . . . . . . . . . . . . . . . . . . . . . .
3 The basics
3.1 cvx begin and cvx end . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Data types for variables
. . . . . . . . . . . . . . . . . . . . . . . . .
3.3 Objective functions . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4 Constraints
3.5 Functions
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.6 Sets
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.7 Dual variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.8 Expression holders
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
4 The DCP ruleset
4.1 A taxonomy of curvature . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Top-level rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3 Constraints
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4 Expression rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.5 Functions
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.6 Compositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.7 Monotonicity in nonlinear compositions . . . . . . . . . . . . . . . . .
4.8 Scalar quadratic forms . . . . . . . . . . . . . . . . . . . . . . . . . .
5 Adding new functions to the cvx atom library
5.1 New functions via the DCP ruleset
. . . . . . . . . . . . . . . . . . .
5.2 New functions via partially specified problems . . . . . . . . . . . . .
6 Semidefinite programming using cvx
7 Geometric programming using cvx
7.1 Top-level rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.2 Constraints
7.3 Expressions
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
4
4
5
5
6
6
8
8
10
11
13
15
17
17
17
18
18
19
20
21
23
25
25
26
26
27
28
29
31
32
34
34
35
39
41
41
42
42
8 Advanced topics
8.1 Solver selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.2 Controlling solver precision . . . . . . . . . . . . . . . . . . . . . . . .
8.3 Miscellaneous cvx commands
. . . . . . . . . . . . . . . . . . . . . .
8.4 Assignments versus equality constraints . . . . . . . . . . . . . . . . .
8.5
. . . . . . . . . . . . . . . . . . . . . . . . . .
Indexed dual variables
A Installation and compatibility
A.1 Basic instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.2 About SeDuMi and SDPT3 . . . . . . . . . . . . . . . . . . . . . . .
A.3 A Matlab 7.0 issue . . . . . . . . . . . . . . . . . . . . . . . . . . . .
B Operators, functions, and sets
B.1 Basic operators and linear functions . . . . . . . . . . . . . . . . . . .
B.2 Nonlinear functions . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.3 Sets
C cvx status messages
D Advanced solver topics
D.1 The successive approximation method . . . . . . . . . . . . . . . . . .
D.2 Irrational powers
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
D.3 Overdetermined problems
E Acknowledgements
44
44
44
46
47
48
51
51
52
52
54
54
55
61
63
65
65
65
66
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 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.
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 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 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 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
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 xp, 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 represented via LP, SOCP, or
SDP, including log, exp, log-sum-exp log(exp x1+···+exp xn), entropy, and Kullback-
Leibler divergence. These problems are handled by solving a sequence (typically just
5
a handful) of SDPs, which yields the solution to the full accuracy of the core solver.
On the other hand, this technique can be substantially slower than if the core solver
directly handled such functions. The successive approximation method is briefly
described in Appendix D.1. Geometric problems are now solved in this manner as
well; in previous versions, an approximation was made.
Ultimately, we will interface cvx to a solver with native support for such functions,
which result in a large speedup in solving problems with these functions. Until then,
users should be aware that problems involving these functions can be slow to solve
using the current version of cvx. For this reason, when one of these functions is used,
the user will be warned that the successive approximate technique will be used.
We emphasize that most users do not need to know how cvx handles their problem;
what matters is what functions and operations can be handled. For a full list of
functions supported by cvx, see Appendix B, or use the online help function by
typing help cvx/builtins (for functions already in Matlab, such as sqrt or log) or
help cvx/functions (for functions not in Matlab, such as lambda_max).
1.4 Feedback
Please contact Michael Grant (mcgrant@stanford.edu) or Stephen Boyd (boyd@stanford.edu)
with your comments. If you discover what you think is a bug, please include the fol-
lowing in your communication, so we can reproduce and fix the problem:
• the cvx model and supporting data that caused the error
• a copy of any error messages that it produced
• the cvx version number and build number
• the version number of Matlab that you are running
• the name and version of the operating system you are using
The latter three items can all be discovered by typing
cvx_version
at the MATLAB command prompt; simply copy its output into your email message.
1.5 What cvx is not
cvx is not meant to be a tool for checking if your problem is convex. You need
to know a bit about convex optimization to effectively use cvx; otherwise you are
the proverbial monkey at the typewriter, hoping to (accidentally) type in a valid
disciplined convex program.
On the other hand, if cvx accepts your problem, you can be sure it is convex. In
conjunction with a course on (or self study of) convex optimization, cvx (especially,
its error messages) can be very helpful in learning some basic convex analysis. While
6
cvx will attempt to give helpful error messages when you violate the DCP ruleset, it
can sometimes give quite obscure error messages.
cvx is not meant for very large problems, so if your problem is very large (for
example, a large image processing problem), cvx is unlikely to work well (or at all).
For such problems you will likely need to directly call a solver, or to develop your
own methods, to get the efficiency you need.
For such problems cvx can play an important role, however. Before starting to
develop a specialized large-scale method, you can use cvx to solve scaled-down or
simplified versions of the problem, to rapidly experiment with exactly what problem
you want to solve. For image reconstruction, for example, you might use cvx to
experiment with different problem formulations on 50 × 50 pixel images.
cvx will solve many medium and large scale problems, provided they have ex-
ploitable structure (such as sparsity), and you avoid for loops, which can be slow in
Matlab, and functions like log and exp that require successive approximation. If you
encounter difficulties in solving large problem instances, please do contact us; we may
be able to suggest an equivalent formulation that cvx can process more efficiently.
7
2 A quick start
Once you have installed cvx (see §A), you can start using it by entering a cvx speci-
fication into a Matlab script or function, or directly from the command prompt. To
delineate cvx specifications from surrounding Matlab code, they are preceded with
the statement cvx_begin and followed with the statement cvx_end. A specification
can include any ordinary Matlab statements, as well as special cvx-specific commands
for declaring primal and dual optimization variables and specifying constraints and
objective functions.
Within a cvx specification, optimization variables have no numerical value; in-
stead, they are special Matlab objects. This enables Matlab to distinguish between
ordinary commands and cvx objective functions and constraints. As Matlab reads
a cvx specification, it builds an internal representation of the optimization problem.
If it encounters a violation of the rules of disciplined convex programming (such as
an invalid use of a composition rule or an invalid constraint), an error message is
generated. When Matlab reaches the cvx_end command, it completes the conversion
of the cvx specification to a canonical form, and calls the underlying core solver to
solve it.
If the optimization is successful, the optimization variables declared in the cvx
specification are converted from objects to ordinary Matlab numerical values that
can be used in any further Matlab calculations. In addition, cvx also assigns a few
other related Matlab variables. One, for example, gives the status of the problem
(i.e., whether an optimal solution was found, or the problem was determined to be
infeasible or unbounded). Another gives the optimal value of the problem. Dual
variables can also be assigned.
This processing flow will become more clear as we introduce a number of simple
examples. We invite the reader to actually follow along with these examples in Mat-
lab, by running the quickstart script found in the examples subdirectory of the cvx
distribution. For example, if you are on Windows, and you have installed the cvx
distribution in the directory D:\Matlab\cvx, then you would type
cd D:\Matlab\cvx\examples
quickstart
at the Matlab command prompt. The script will automatically print key excerpts of
its code, and pause periodically so you can examine its output. (Pressing “Enter” or
“Return” resumes progress.) The line numbers accompanying the code excerpts in
this document correspond to the line numbers in the file quickstart.m.
2.1 Least-squares
We first consider the most basic convex optimization problem, least-squares.
In a
least-squares problem, we seek x ∈ Rn that minimizes kAx − bk2, where A ∈ Rm×n
is skinny and full rank (i.e., m ≥ n and Rank(A) = n). Let us create some test
problem data for m, n, A, and b in Matlab:
8
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
