As of February 20, over 10000 students are enrolled in CVX101, Stanford University’s online course in convex optimization offered by Professor Stephen Boyd and colleagues. This course has been taught using Stanford’s internal video distance learning platform for years, so it is well suited for the OpenEdX MOOC platform.
Our Matlab package CVX is being used throughout the course. The Mathworks is providing time-limited Matlab licenses to all enrollees for the duration of the course.
To provide enrollees with a gentle introduction to CVX, Prof. Boyd recorded the following video. If you’re not yet a CVX user yourself, you might find it useful as well!
We are pleased to announce that the authors of TFOCS, in conjunction with copyright holders CVX Research and the California Institute of Technology, have agreed to release TFOCS under a permissive 3-Clause BSD license. It is our sincere hope that moving to a permissive open source license will encourage wider use and community-driven improvements.
As part of our shift to this new license, we have moved the source repository for TFOCS to GitHub. From this site, users can download a versioned release, clone the repository for more frequent updates, or create their own fork for customization.
Community support for TFOCS is available on CVX Forum, a question and answer site modeled after the popular StackExchange family of sites. The forum serves users of both TFOCS and the namesake package CVX. For more dedicated assistance, paid support contracts are available from the packages’ authors.
For more details, please visit the TFOCS home page. The full text of the license is available on the download page as well as in the file LICENSE in the package itself.
One of the key features added to CVX 2.0 is the ability to connect to the commercial solvers Gurobi and MOSEK. Both solvers are highly respected in the optimization community, and we have found that they work very well with CVX. These solvers have also enabled us to support mixed-integer modeling.
This week we have taken a step to further simplify the process of using CVX with these solvers by bundling them with CVX itself. Of course, if you already use CVX with these solvers, nothing has changed—you can continue to connect CVX to your existing Gurobi and MOSEK installations. But now it is even easier for new users of CVX to use our modeling framework with these excellent solvers.
Some technical details:
We have improved our installation instructions to cover the details of installing a CVX Professional License, and have created separate sections describing how to install and use Gurobi and/or MOSEK with CVX.
Because these bundles are a new offering for us, we have decided to keep the “beta” version designation for just a bit longer, in case this wider release reveals some installation issues. But we have many users happily using Gurobi and MOSEK with CVX already, so we encourage you download CVX 2.0 now.
We are grateful to both Gurobi Optimizaton and MOSEK ApS for working closely with us to ensure that the use of their solvers with CVX is as seamless and straightforward as possible.
We have been hard at work to exit the beta period for CVX 2.0. We’re almost there! However, due to some recent developments in the solver arena, we have decided to release a new build of CVX 2.0 beta today. We invite you to download a copy. Feel free to install this beta on top of your current version of CVX 2.0, but do re-run cvx_setup once you have done so.
Ordinarily, an update to a solver Gurobi or MOSEK would not require a new release of CVX. Gurobi 5.1 was released on January 8th, and the previous version of CVX 2.0 beta worked perfectly with that new release. If you’re content with your current version of CVX, there is no need to download the new build.
Mosek 7 adds support for semidefinite programs (SDPs), however, and this required some code changes to the Mosek solver shim. Previously, users who required an SDP-capable solver had to rely on the SDPT3 and SeDuMi solvers bundled with CVX. We are very pleased that now our users will have another new, commercially supported option for such problems now.
If you want to try the beta version of Mosek 7 now, head over to the beta section of their web site. There you can download a copy of MOSEK for your preferred platform, as well as a trial license that expires on March 1, 2013. Once you’ve installed MOSEK 7.0, add its Matlab MEX directory to your MATLAB path, and re-run cvx_setup.
Both Gurobi and MOSEK are excellent solvers, and the companies behind them have been wonderful to work with. It is a privilege for us to be able to support their use with CVX. In fact, we have some exciting new developments brewing on that front that we hope to share very soon. Stay tuned…
A new version of CVX 2.0 beta has been posted to the web site. Please go get it. We’ve fixed a handful of bugs, but most importantly, we’ve completed the licensing engine. As with the previous beta, this version comes with a license for CVX Professional that expires on November 30, 2012—a little over three weeks away. After that date, you’ll need a license to use the CVX Professional features.
If you are an academic user, you can obtain a license key at no charge. Just visit our Academic license request page and fill out the online form. An active university email address is required, as well as the username and host ID of the computer you are using. If everything checks out, you should receive your license key within minutes. Please note that these license keys require this latest beta release to operate (build 883 or later).
Commercial users will need to purchase a CVX Professional license from us to continue using Gurobi and MOSEK with CVX after the conclusion of the beta period. Feel free to send us an email at email@example.com for a quote.
Lastly, let us take this opportunity to promote the CVX Forum! This is a community-driven Q&A site where you can find answers to a variety of common usage questions posed by users of CVX. If you have a question that hasn’t yet been asked, of course, you can ask it. And if you have an answer that others may find useful, you can provide it, too. We truly hope that over time the CVX Forum will become a rich database of expertise in disciplined convex programming, CVX, and TFOCS.
We’re hard at work getting ready for the full release of CVX 2.0. We have incorporated some great feedback from our users already, including bug fixes submitted to our help desk and issues raised on our Q&A site.
We are committed to offering academic licenses at no charge—and with as little inconvenience as possible. I have been hard at work building the infrastructure to support that. But it looks like that work will not be finished by the time the beta period ends in two weeks—on October 31, 2012. For that reason, I have created a new beta license key that extends the beta period another month—to November 30, 2012.
To grab the new license key, click on this link to be taken to our help desk site. There you will find a link to download the new license key, as well as instructions for installing it.
Remember, a license key is required only if you need to use CVX with commercial solvers. If you are content with SDPT3 or SeDuMi, a license is unnecessary.
EDIT: We’ve posted a new version of CVX 2.0 beta on the download page that includes the license key, as well as a couple of minor fixes.
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.
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
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.
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
u are constant vectors. If you were to specify the constraint
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 )
For a nonlinear example, consider these constraints:
The first constraint is convex, the second is not. But together they can be specified in an MIDCP:
binary variable nb;
We emphasize that the ability to convert nonconvex constraints to MIDCP form is the exception rather than the rule. For instance, the constraint
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!
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.
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:
- Solve problems using commercial solvers Gurobi and MOSEK
- Support for binary and integer variables
- A new support infrastructure
- The ability to save preferences, like your preferred solver, precision settings, and so forth, between MATLAB sessions, using the
- A revamped
cvx_setup installation script
- Support dropped for Matlab 7.4 and earlier
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
gurobi in its path before you run
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.
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.