A new support option: the CVX Forum

CVX has reached a download pace of over 10,000 downloads per year! The acceptance of CVX in research settings has been amazing—and challenging. Supporting all of our users via email, as we have done for the last 6 years, is simply no longer feasible.

Of course, if you have found a bug in CVX, we want to hear about it; see our support page for information on submitting bug reports. CVX is on a rapid-release cycle, so a reported bug can be often fixed and made available to users in just a few short days.

But in fact, bug reports represent only a fraction of our total support effort. Most of our time is spent helping people to become effective users of CVX. Sometimes, this involves answering a usage question that is frequently asked, but not readily included in standard documentation. In other cases, it involves offering advice on how to implement a particular model found in a paper or application.

If only we were experts in the myriad applications in which that CVX has been applied. Alas, we are not; but our users are! It is clear to us that what is needed is an online knowledgebase and a community-driven Q&A forum—a place where the valuable experience of our large user community can be collected, organized, and shared.

That is the purpose of our new creation, the CVX Forum.

If you have visited sites such as Stack Overflow or OR Exchange, then the CVX Forum should look very familiar. Sites such as these have proven to be extremely successful at providing community-based support on a variety of topics. Through a novel voting system, the site self-organizes so that common questions and their most helpful answers are easy to find, creating a rich knowledgebase that no user manual can match. The CVX Forum will be a great place to discuss (and vote upon!) feature requests as well.

We encourage all CVX users to join us at the CVX Forum and join in a communal effort to improve the state of disciplined convex programming. Frankly, some of our users are better qualified to answer some of the questions we receive than we are! We hope you will prove us right.

Mixed-integer support in CVX 2.0

Gurobi and MOSEK, the first commercial solvers we have connected to CVX, support mixed-integer models: models with one or more variables constrained to assume integer or even binary (0/1) values. Such variables can be used not just in linear programs, but nonlinear convex programs as well.

We have decided to introduce the ability to specify integer and binary variables into CVX models as well. To use this feature, simply add the integer or binary keyword to the relevant variable declaration; for example:

variable x(10) integer;
variable y(3,3) binary;

Models with integer and binary variables must still obey all of the same disciplined convex programming rules that CVX enforces for continuous models. For this reason, we are calling these models mixed-integer disciplined convex programs, or MIDCPs.

Danger! Danger!

Mixed-integer DCPs are not convex.

As with mixed-integer linear and quadratic programs (MILPs/MIQPs), MIDCPs are theoretically intractable. In practice, your results will vary. Solving them requires the combination of a continuous optimization algorithm, such as an interior-point method, and an exhaustive search, such as a branch-and-bound. In some cases, your model will be solved globally after only a few branches. In other cases, the solver will fail to find a global solution in any reasonable amount of time.

Furthermore, solvers for MIDCPs are less mature than those devoted specifically to MILPs/MIQPs. Most of the developments that have improved the performance of MILP solvers map logically to MIDCPs, but MIDCPs present new challenges. We hypothesize that solver performance will be more sensitive to problem size with MIDCPs than with MILPs, and that the best results will come with models that make only sparing use of integer variables.

Non-convex constraints as MIDCP constraints

One of the more interesting consequences of MIDCP support is that, in limited cases, a nonconvex model can be transformed in to an MIDCP. For instance, suppose x is a vector variable, and l and u are constant vectors. If you were to specify the constraint

l <= abs(x) <= u;

in CVX, you would get the dreaded Disciplined convex programming error: message. But in fact, this constraint can be represented as an MIDCP by introducing a vector of binary variables:

varaible xb(size(x)) binary;
l - xb .* ( l + u ) <= x <= u - xb .* ( l + u );

For a nonlinear example, consider these constraints:

max(norm(x),norm(y)) <= 2;
min(norm(x),norm(y)) <= 1;

The first constraint is convex, the second is not. But together they can be specified in an MIDCP:

binary variable nb;
norm(x) <= 1 + nb;
norm(y) <= 2 - nb;

We emphasize that the ability to convert nonconvex constraints to MIDCP form is the exception rather than the rule. For instance, the constraint

1 <= norm(x) <= 2;

looks very similar to our first example, but it cannot be converted to an MIDCP. Furthermore, CVX will not perform these conversions for you; you will have to identify and perform them yourself. Do not ignore convexity during the modeling process, assuming that you will be able to convert your model to an MIDCP after the fact!

Solver support

Neither of CVX’s free solvers supports MIDCPs. Gurobi and MOSEK are currently the only choices for these problem types. Academic users will be able to use either solver (or both!) at no charge. Commercial users can use them by purchasing a CVX Professional License.

We hope to add support for a free mixed-integer solver in a future version of CVX. We are currently studying the use of GLPK, the GNU Linear Programming Kit. Of course, as the name implies, GLPK will only support models that can be converted to LPs or MILPs. If a reliable, free solver that supports both integer variables and conic constraints becomes available, we will certainly consider it; please contact us!

Can a mixed-integer problem truly be disciplined?

Among those of you who know us well, there might be some surprise at our decision to include mixed-integer support. After all, we have been, and remain, very strong advocates for a deliberate approach to convex programming. Indeed, we coined the term disciplined convex programming to describe our philosophy: that the best way to exploit convexity is not to search for it after the model is constructed, but rather to make convexity an explicit goal of the modeling process itself.

We hold that a proper use of MIDCPs still requires a disciplined approach to model building. As we said above, non-convex models representable as MIDCPs will be the exception, not the rule; it is still necessary to build models with convexity as a goal, not an artifact. The performance limits of MIDCP solvers will tend to limit the use of integer and binary variables in CVX models.

There is no doubt that the addition of MIDCPs to CVX is an experiment for us. It will also be an experiment for our users and our solver partners as well. We look forward to seeing the new applications that arise when modelers can add modest numbers of integer constraints to their models. And we look forward to seeing the algorithms for mixed-integer convex programming improve as a suite of “difficult” test problems accumulates.

Announcing CVX 2.0 beta

We are proud to announce the release of CVX 2.0. We have added some interesting new features, big and small, and are looking forward to seeing our users exploit them!

Some of the highlights include:

Using Gurobi and MOSEK

MOSEK ApS and Gurobi Optimization are two great companies that provide high-performance, well-supported solvers for convex programming. Both companies have been fantastic about supporting our efforts to connect CVX to their solvers; you’ll hear more our about our work together in the coming weeks. We believe that they will make great choices for use with the models our users wish to solve.

The addition of support for commercial solvers is part of our commercialization strategy for CVX Research. CVX will remain free of charge for all users when paired with the free solvers SDPT3 and SeDuMi; and commercial solver support will be free for all academic users as well. But starting with the final version of CVX 2.0, commercial customers will need to purchase a CVX Professional License to use CVX with Gurobi or MOSEK.

We will share more about product and pricing details over the course of this beta period. But for now, version 2.0 beta includes a built-in, time-limited CVX Professional License. Thus all users, both academic and commercial, are free to use CVX with Gurobi and MOSEK for the duration of the beta period. Simply make sure that Matlab sees mosekopt and/or gurobi in its path before you run cvx_setup.

Mixed integer support

It is now possible to specify that one or more of your variables must assume integer or binary (0/1) values. We call such models mixed integer disciplined convex programs, or MIDCPs. We’ve created an separate post devoted to some of the very real caveats and cautions that come with adding integer support; click here to see it.

A new support infrastructure

CVX has reached a download pace of over 10,000 downloads per year? The acceptance of our software into the research community has truly been amazing—and challenging. Supporting all of our users via email, as we have done for the last 6 years, entirely at our expense, is simply no longer tenable. So we’re creating a new support infrastructure so that we believe will truly help the CVX user community. Please see here for more details.

Support for (very) old versions of Matlab dropped

Version 1.22 of CVX required Matlab version 6.5 or later. Starting with 2.0, we have dropped support for versions 7.4 and older, and now support Matlab only on versions 7.5 or later. We did this to help streamline our development process and to enable us to take advantage of some of the more modern features of the MATLAB language.

Of course, Matlab 7.5 is over five years old now, and we are certain that nearly all of our users are using even newer versions. Nevertheless, if for some reason you absolutely must run CVX on Matlab 7.4 or earlier, you can still download CVX 1.22 from our web site.

CVX wins the Beale Orchard-Hayes prize!

Michael Grant & Stephen Boyd were selected to win the 2012 Beale Orchard-Hays Prize for Excellence in Computational Mathematical Programming. This award is presented once every three years by the Mathematical Optimization Society, and is given in memory of Martin Beale and William Orchard-Hayes, two pioneers in computational mathematical optimization. The prize was awarded specifically for CVX, and cites both the software itself and a paper that describes some of the key technology.

The presentation took place on August 19, 2012 at the opening ceremony of the International Symposium for Mathematical Programming in Berlin, Germany. The Berlin ISMP organizing committee delivered a fantastic show. The ceremony was held in the historic Konzerthaus Berlin, and featured performances by the Berlin Sibelius Orchestra. University of Wisconsin Professor Michael Ferris, a member of the award committee, delivered a flattering introduction.

We want thank our nominator, the award committee, and the Mathematical Optimization Society for a wonderful honor. It is truly a privilege to be counted among the winners of the Beale-Orchard-Hays prize; some great names are included among them. In fact, Professor Ferris won the prize himself in 1997; and the inaugural awardee was Professor Michael Saunders, a fellow Stanford affiliate and one of Michael Grant’s dissertation readers. (It would seem that Michael is a good first name to have in this field.)

Most importantly, however, we would like to thank all of our users. You have given us wonderful encouragement over the years—whether directly through an email of thanks, or indirectly by citing our work in your publications, or even just by contributing to our download count! Knowing that our work has proven useful to you has driven us to persist in development and support.

We have a strong future planned for CVX, and for new software on other mathematical platforms. CVX 2.0 beta has just been released—our first step towards a sustainable business built on convex optimization. (Everyone who likes CVX except that they have to run Matlab to use it—I hope you’ll stay tuned as well.)

The text of the award citation is below:

2012 Beale-Orchard-Hays Prize Citation

Michael Grant and Stephen Boyd, “CVX: Matlab software for disciplined convex programming, version 1.21”, http://cvxr.com/cvx, April 2011

Michael Grant and Stephen Boyd, “Graph Implementations for Nonsmooth Convex Programs” in Recent Advances in Learning and Control, V. Blondel, S. Boyd and H. Kimura (eds), pp. 95-110, Lecture Notes in Control and Informational Sciences, Springer, 2008.

In a unanimous decision, the selection committee (Michael Ferris (Chair), Philip Gill, Tim Kelley, Jon Lee) for the Beale Orchard Hays Prize for 2012 decided that the award be given to Michael Grant and Stephen Boyd for the software CVX as described in the above papers.

The nomination states that “CVX is a modeling language for convex programming that has been implemented in Matlab. It also automatically links to semidefinite solvers … CVX makes convex programming as easy as Matlab makes matrix computation.” The committee feels that this work is very well respected within our community and is used extensively for both research and teaching at a number of high-profile institutions. In particular, it provides a unique, well-documented tool for prototyping and exploring existing and emerging applications of convex optimization.

This Prize is sponsored by the Society in memory of Martin Beale and William Orchard-Hays, pioneers in computational mathematical programming. The Prize is given for excellence in any aspect of computational mathematical programming. “Computational mathematical programming” includes the development of high-quality mathematical programming algorithms and software, the experimental evaluation of mathematical programming algorithms, and the development of new methods for the empirical testing of mathematical programming techniques.

In the photo, from left to right: Michael Ferris, award committee chair; Nicolas Zimmer, Berlin government representative; Professor Stephen Boyd; Philippe Toint, MOS chair; Michael Grant.

CVX Research, Inc. is here.

A few years ago, I was able to secure the four-letter domain “cvxr.com”. I’d have loved to secure “cvx.com”, but unfortunately the Connecticut Valley Electric Exchange got there first. (And they call themselves CONVEX no less. The nerve…) Still, a four letter domain name is a fun thing to have… especially if the “R” means something.

After a little thought, CVX Research seemed like a very reasonable name, given the various projects on my plate. I registered that name as a d/b/a for my consulting practice, and CVX Research was born.

If you’ve been to the web site lately, however, you’ll notice that now it says “CVX Research, Inc.” You might have also seen our new logo, pictured above.

Over a year ago, Stephen Boyd and I concluded that a market existed for a commercially supported version of CVX, and that we could tap that market without compromising our commitment to the academic community. In July, we created this corporation to help achieve this goal. Incorporating enables us to construct commercial license agreements and enter into agreements with other software vendors as well.

To start, we intend to fund our operations by connecting CVX to well-respected commercial solvers, and licensing this new capability to commercial customers for a fee. Academic users will receive full access to the commercial features at no charge; and the standard version of CVX will remain free to all customers.

We feel truly honored by the success of CVX, excited to see it used in so many different fields, and encouraged by the thanks we have received from so many of our users. Thank you very much for your support, and stay tuned.

Regards,
Michael C. Grant, Ph.D.
Co-founder
CVX Research, Inc.