所需积分/C币:9 2014-04-26 16:26:22 340KB PDF
收藏 收藏

cvx is a modeling system for disciplined convex programming. Disciplined convex programs, 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.
8 Advanced topics 44 8.1 Solver selection 8.2 Controlling solver precision 8.3 Miscellaneous cvx commands 46 8.4 Assignments versus equality constraints 8.5 Indexed dual variables a Installation and compatibility 51 A 1 Basic instructions 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 B2 Nonlinear functions B 3 Sets 61 cvx status messages 63 D Advanced solver topics 65 D.1 The successive approximation method 65 D2 Irrational powers 65 D 3 Overdetermined proble 66 E Acknowledgements 67 1 Introduction 1.1 What is cvx? cvX is a modeling system for disci lined conver 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 eatly simplify the task of specifying the problem. cvx can also solve much more complex convex optimization problems, including many involving nondifferentiable unctions, such as e1 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,,ortheStanford courseee364a.availableatwww.stanfordedu/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 matric 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 seethetutorialpaperBkvhO5, 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 Lofberg [Lofo5, Dahl and Vandenberghe Dvo5, CrusiusCru02, Wu and Boyd wB00], and many others. The modeling language follows the spirit of AMPL FGK99 or GAMS BKMR9S; 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 [Lof05. We also hope to develop versions of cvx for other platforms in the future 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 gBYo6 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 TTTo6, which is the default. Future versions of cvx may support other solvers, such as MOSEK [MOSO5 or CVXOPT [DVO5]. 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 naximum, absolute value, quadratic forms the minimun and maximun eigenvalues of a symmetric matrix, power functions cp, and lp 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 lp-norm is used, with non-rational exponent p, cvx replaces p with a nearby rational. The log of the normal cumulative distribution log (a) 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 c1+..+exp rn), entropy, and Kullback- Leibler divergence. These problems are handled by solving a sequence(typically just 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.I. 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 unctions 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(boydostanford 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 o the cvx nodel and supporting data. that caused the error a copy of any error messages that it produced the cvx version number and build number o the version number of matlab that you are running o the name and version of the operating system you are using The latter three items can all be discovered by typing CVⅩVers1on at the matlab command prompt; simply copy its output into your email message 1. 5 What cyx 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 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 x 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 2 A quick start Once you have installed cvx(see SA), 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 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 (ic,, 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 ty 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 E Rn that minimizesAC-bl2, where A E Rm is skinny and full rank(i.e, m 2 n and Rank(A)=n). Let us create some test problem data for m, n, A, and b in Matlab 17m=16 8; 18 A= randn(m,n) 19 b= randn(m, 1) (We chose small values of n and n to keep the output readable. Then the least- squares solution =(AAA 6 is easily computed using the backslash operator 1s=A、b Using cvx, the same problem can be solved as follows 3 cvx_begin variable x(n) minimize( norm (A*x-b)) 26 CVx end (The indentation is used for purely stylistic reasons and is optional. Let s examine this specification line by line Line 23 creates a placeholder for the new cvx specification, and prepares Matlab to accept variable declarations, constraints, an objective function, and so forth Line 24 declares x to be an optimization variable of dimension n. cvx requires that all problem variables be declared before they are used in an objective function or constraints Line 25 specifies an objective function to be minimized; in this case, the Eu- A clidean or c2-norm of Ac Line 26 signals the end of the cvx specification, and causes the problem to be solved The backslash form is clearly simpler there is no reason to use cvx to solve a simp least-squares problem. But this example serves as sort of a"Hello world! program in cvx; i.e., the simplest code segment that actually does something useful If you were to type x at the Matlab prompt after line 24 but before the cvx_end command, you would see something like this cvx affine expression (8x1 vector That is because within a specification, variables have no numeric value; rather, they are Matlab objects designed to represent problem variables and expressions involving them. Similarly, because the objective function norm(A*x-b) involves a cvx variable it does not have a numeric value either; it is also represented by a Matlab object When Matlab reaches the cvx_end command, the least-squares problem is solved and the Matlab variable x is overwritten with the solution of the least-squares prob lem, i.c.,(44)-46. Now x is an ordinary length-n numerical vector, identical to what would be obtained in the traditional approach, at least to within the accuracy of the solver. In addition two additional matlab variables are created cvx_optval, which contains the value of the objective function; i. e,Ac-bll2 cvx_status, which contains a string describing the status of the calculation. In this case, cvx_status would contain the string Solved. See Appendix c for a list of the possible values of cvx_status and their meaning cvx_slvtol: the tolerance level achieved by the solver cvx_slvitr: the number of iterations taken by the solver All of these quantities, x, cvx_optval, and cvx_status, Etc. may now be freely used in other Matlab statements, just like any other numeric or string values. There is not much room for error in specifying a simple least-squares problem but if you make one, you will get an error or warning message. For example, if you replace line 25 with maximize( norm(A*x-b)) which asks for the norin to be maximized, you will get an error message stating that a convex function cannot be maximized (at least in disciplined convex programming ?? Error using == maximize Disciplined convex programming error: Objective function in a maximization must be concave 2.2 Bound-constrained least-squares Suppose we wish to add some simple upper and lower bounds to the least-squares problem above: i.e., we wish to solve Immunize‖Ax=bl subject to l< where l and u are given data, vectors with the same dimension as the variable The vector inequality u v means componentwise, i.e,, i vi for all i. We can no longer use the simple backslash notation to solve this problen. but it can be transformed into a quadratic program(QP), which can be solved without difficulty if you have some form of QP software available Let us provide some numeric values for l and u 49 bnds =randn(n, 2) 501=min(bnds,[],2); 61 u= max( bnds, [,2 Then if you have the Matlab Optimization Toolbox [Mato5, you can use the quadprog function to solve the problem as follow IIf you type who or whos at the command prompt, you may see other, unfamiliar variables as well. Any variable that begins with the prefix cvx_ is reserved for internal use by cvx itself, and should not be changed 10

试读 72P cvx_usrguide
限时抽奖 低至0.43元/次
身份认证后 购VIP低至7折
  • 签到新秀

关注 私信
cvx_usrguide 9积分/C币 立即下载

试读结束, 可继续读5页

9积分/C币 立即下载