凸优化CVX工具箱使用教程

【实例简介】
CVX matlab工具箱配套教程，供大家学习使用。
8 Advanced topics 44 8.1 Solver selection 8.2 Controlling solver precision 8.3 Miscellaneous cvx commands 6 8.4 Assignments versus equality constraints 8.5 Indexed dual variables a Installation and compatibility 51 A 1 Basic instructions A2 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 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 E Acknowledgements 67 1 Introduction 1 What is cvx? cvX is a, modeling system for di sciplined 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 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 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 Convea Optimization Bv04,availableon-lineatwww.stanford.edu/boyd/cvxbook/,ortheStanford courseee364a.availableatwww.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 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,availableatwww.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 Lofberg Lof05, Dahl and Vandenberghe [DvO5J, CrusiusCru02), Wu and Boyd wB00J, 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 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 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 beset 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 TTTo6J, which is the default. Future versions of cvx may support other solvers, such as MOSEK [MOS05 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 maximum, absolute value, quadratic forms the minimum and maximum eigenvalue of a symmetric matrix, power functions 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 mn),entropy, and Kullback- Leibler divergence. These problems are handled by solving a sequence(ty pically 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 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 ther 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) 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 o the cyx model and supporting data, that, caused the error a copy of any error messages that it produced e the cvx version number and build number o the version number of Matlab that you are running e 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 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) ty ype 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 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 his processing flow will become more clear as we introduce a number of simpl examples. We invite the reader to actually follow along with these examples in Mat ab, 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 east- squares problem, we seek x∈ Rn that minimizes‖Ar-be, where A∈Rxn 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 15m=16;n=8; 16 A=randn(m,n) 17 b= randn(m, 1 (We chose small values of m and n to keep the output readable. )Then the least- squares solution =(AA)A b is easily computed using the backslash operator 20X1s=A\b; Using cvx, the same problem can be solved as follows 23 cvx_begin variable x(n) minimize( norm(A*x-b)) 26CVⅹend (The indentation is used for purely stylistic reasons and is optional. Let us 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 e 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 clidean or l2-norm of Ax-b 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 simple 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, the 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, ic,(4A)Ab. 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.,A.C-bl2 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 e cvx slvitr: the number of iterations taken by the solver All of these quantities, x, cvx_optval, and cvx_status, elc. 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 norn 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 Iminiinize‖Ax-b|2 subject to I〈x where l and u are given data, vectors with the same dimension as the variable The vector inequality u< v means componentwise, i.e ui< vi for all i. We can no longer use the simple backslash notation to solve this probleIn, 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 47 bnds randn(n, 2) 1=min( bnds, [ 2) 49 u =max( bnds, [] 2 Then if you have the Matlab Optimization Toolbox [Mato5, you can use the quadprog function to solve the problem as follows 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 【实例截图】
【核心代码】