Introduction¶
What is CVX?¶
CVX is a modeling system for constructing and solving disciplined convex programs (DCPs). CVX supports a number of standard problem types, including linear and quadratic programs (LPs/QPs), second-order cone programs (SOCPs), and semidefinite programs (SDPs). CVX can also solve much more complex convex optimization problems, including many involving nondifferentiable functions, such as \(\ell_1\) norms. You can use CVX to conveniently formulate and solve constrained norm minimization, entropy maximization, determinant maximization, and many other convex programs. As of version 2.0, CVX also solves mixed integer disciplined convex programs (MIDCPs) as well, with an appropriate integer-capable solver.
To use CVX effectively, you need to know at least a bit about convex optimization. For background on convex optimization, see the book Convex Optimization [BV04] or the Stanford course EE364A.
CVX is implemented in Matlab, effectively turning Matlab into an optimization 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 optimization, such as a branch and bound method, or an engineering design framework.
CVX provides special modes to simplify the construction of problems from two specific problem classes. In semidefinite programming (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 geometric programming (GP) mode, CVX accepts all of the special functions and combination rules of geometric programming, including monomials, posynomials, and generalized posynomials, and transforms such problems into convex form so that they can be solved efficiently. For background on geometric programming, see this tutorial paper [BKVH05].
Previous versions of CVX supported two free SQLP solvers, SeDuMi [Stu99] and SDPT3 [TTT03]. These solvers are included with the CVX distribution. Starting with version 2.0, CVX supports two commercial solvers as well, Gurobi and MOSEK. For more information, see Solvers.
The ability to use CVX with commercial solvers is a capability that we have decided to include under a new CVX Professional license model. Academic users will be able to utilize these features at no charge, but commercial users will require a paid CVX Professional license. For more details, see Licensing.
What’s new?¶
Recent developments in solver technology are expanding CVX’s capability to solve problems. In particular, the commercial solver Mosek has added native support for the exponential cone; and this allows CVX to solve problems involving logarithms, exponentials, and entropy functions withouth reliance on its successive approximation heuristic.
What is disciplined convex programming?¶
Disciplined convex programming is a methodology for constructing convex optimization 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 The DCP ruleset. It is extremely 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 accepting the restrictions imposed by the ruleset, we obtain considerable benefits, such as automatic conversion of problems to solvable form, and full support for nondifferentiable functions. In practice, we have found that disciplined convex programs closely resemble their natural mathematical forms.
Mixed integer problems¶
With version 2.0, CVX now supports mixed integer disciplined convex programs (MIDCPs). A MIDCP is a model that obeys the same convexity rules as standard DCPs, except that one or more of its variables is constrained to take on integral values. In other words, if the integer constraints are removed, the result is a standard DCP.
Unlike a true DCP, a mixed integer problem is not convex. Finding the global optimum requires the combination of a traditional convex optimization algorithm with an exhaustive search such as a branch-and-bound algorithm. Some CVX solvers do not include this second piece and therefore do not support MIDCPs; see Solvers for more information. What is more, even the best solvers cannot guarantee that every moderately-sized MIDCP can be solved in a reasonable amount of time.
Mixed integer disciplined convex programming represents new territory for the CVX modeling framework—and for the supporting solvers as well. While solvers for mixed integer linear and quadratic programs (MILP/MIQP) are reasonably mature, support for more general convex nonlinearities is a relatively new development. We anticipate that MIDCP support will improve over time.
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. If you are not certain that your problem is convex before you enter it into CVX, you are using the tool improperly, and your efforts will likely fail.
CVX is not meant for very large problems, so if your problem is very large (for example, a large image processing or machine learning 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 \times 50\) pixel images.
CVX will solve many medium and large scale problems, provided they have exploitable structure (such as sparsity), and you avoid for loops, which can be slow in Matlab. If you encounter difficulties in solving large problem instances, consider posting your model to the CVX Forum; the CVX community may be able to suggest an equivalent formulation that CVX can process more efficiently.
Licensing¶
CVX is free for use in both academic and commercial settings when paired with a free solver—including the versions of SeDuMi and SDPT3 that are included with the package.
With version 2.0, we have added the ability to connect CVX to commercial solvers as well. This new functionality is released under a CVX Professional product tier which we intend to license to commercial users for a fee, and offer to academic users at no charge. The licensing structure is as follows:
- All users are free to use the standard features of CVX at no charge. This includes the ability to construct and solve any of the models supported by the free solvers SeDuMi and SDPT3.
- Commercial users who wish to solve CVX models using Gurobi or MOSEK will need to purchase a CVX Professional license. Please send an email to CVX Research for inquiries. for an availability schedule and pricing details.
- Academic users may utilize the CVX Professional capability at no charge. To do so, it is necessary to obtain licenses for Mosek and/or Gurobi directly from the vendors.
The bulk of CVX remains open source under a slightly modified version of the GPL Version 2 license. A small number of files that support the CVX Professional functionality remain closed source. If those files are removed, the modified package remains fully functional using the free solvers, SeDuMi and SDPT3. Users may freely modify, augment, and redistribute this free version of CVX, as long as all modifications are themselves released under the same license. This includes adding support for new solvers released under a free software license such as the GPL. For more details, please see the full Licensing section.
