What is disciplined convex programming?

Convex programming unifies and generalizes least squares (LS), linear programming (LP), and quadratic programming (QP). It has received considerable attention recently for a number of reasons: its attractive theoretical properties; the development of efficient, reliable numerical algorithms; and the discovery of a wide variety of applications in both scientific and non-scientific fields. Courses devoted entirely to convex programming are available at Stanford and elsewhere.

For these reasons, convex programming has the potential to become a ubiquitous numerical technology alongside LS, LP, and QP. Nevertheless, there remains a significant impediment to its more widespread adoption: the high level of expertise in both convex analysis and numerical algorithms required to use it. For potential users whose focus is the application, this prerequisite poses a formidable barrier, especially if it is not yet certain that the outcome will be better than with other methods. We have developed a modeling methodology called disciplined convex programming with the goal of lowering this barrier.

As its name suggests, disciplined convex programming imposes a set of conventions to follow when constructing problems. Compliant problems are called, appropriately, disciplined convex programs, or DCPs. The conventions are simple and teachable, taken from basic principles of convex analysis, and inspired by the practices of experts who regularly study and apply convex optimization today. The conventions do not limit generality; but they do allow the steps required to solve DCPs to be automated and enhanced. For instance, determining if an arbitrary mathematical program is convex is an intractable task, but determining if that same problem is a DCP is straightforward. A number of common numerical methods for optimization can be adapted to solve DCPs. The conversion of DCPs to solvable form can be fully automated, and the natural problem structure in DCPs can be exploited to improve performance.

Disciplined convex programming also provides a framework for collaboration between users with different levels of expertise. In short, disciplined convex programming allows applications-oriented users to focus on modeling, and — as they would with LS, LP, and QP — to leave the underlying mathematical details to experts.

Papers

Clicking on a title leads to a separate page with an abstract and a downloadable PDF.

Graph Implementations for Nonsmooth Convex Programs by M. Grant and S. Boyd. Recent Advances in Learning and Control (tribute to M. Vidyasagar), V. Blondel, S. Boyd, and H. Kimura, editors, Springer, 2008, pp. 95-110.

This paper is to be preferred over the next two for two reasons: one, it is considerably shorter; and two, it makes use of the current, public version of CVX as opposed to an earlier prototype.

Disciplined Convex Programming by M. Grant, S. Boyd, and Y. Ye. Chapter in Global Optimization: From Theory to Implementation, L. Liberti and N. Maculan, eds., in the book series Nonconvex Optimization and Applications, Springer, 2006, pp. 155-210.

This paper is the first public presentation of disciplined convex programming and how it can be supported in modeling software. The discussion refers heavily to a never-released prototype of CVX, our modeling software. The current version is considerably different than this prototype.

Disciplined Convex Programming by M. Grant. Ph.D. dissertation, Stanford University, 2005.

My dissertation covers the same material presented in the above paper, but expands the introduction and covers a number of more tedious but important details such as the conversion to solvable form and the recovery of equivalent dual information. Like the paper, it refers to a never-released prototype of CVX. A full reading is recommended only as a cure for insomnia; but the introduction provides a good overview of convex optimization, the practical challenges to solving convex problems, and our proposed solution.