Kochenderfer & Wheeler, Chapter 14

Disciplined Convex Programming

A grammar for convexity. Write your problem using approved atoms and composition rules, and a solver can automatically verify and solve it.

Prerequisites: Chapter 10 (Constraints), Chapter 12–13 (LP/QP).

Chapters

Simulations

Quizzes

Chapter 0: Why DCP?

Determining whether a problem is convex can be difficult. Even if it is convex, converting it to a form that a solver accepts (like an LP or QP) requires expertise. Disciplined Convex Programming (DCP) automates both steps.

The core idea: DCP defines a grammar for constructing convex programs. If your problem can be expressed using the grammar's rules, it is guaranteed to be convex, and the system can automatically transform it into a form solvable by standard algorithms. You write the problem naturally; the system handles the rest.

DCP automates:

Verification of convexity and transformation to solvable form Gradient computation Population-based search

Chapter 1: Canonical Form

A DCP problem has this structure:

minimize convex objective
subject to: convex ≤ concave, affine = affine, affine ∈ convex set

The key grammar rules for constraints ensure that the feasible set is always convex: a convex function ≤ a concave function defines a convex region, and affine equalities define hyperplanes (also convex).

Key insight: The grammar is conservative. Some convex problems cannot be expressed in DCP form (like sqrt(exp(x)), which is convex but the composition rules cannot verify it). The tradeoff: DCP sacrifices some expressiveness for guaranteed automatic verification.

In DCP, inequality constraints must have the form:

convex ≤ concave concave ≤ convex Any form is allowed

Chapter 2: Atom Library

The building blocks of DCP expressions are atoms — functions and sets with known curvature, monotonicity, and range:

Atom	Curvature	Monotonicity	Range
exp(x)	Convex	Increasing	≥ 0
log(x), x > 0	Concave	Increasing	R
x^p, x ≥ 0, p > 1	Convex	Increasing	≥ 0
max(x, y)	Convex	Increasing in both	R
x + y	Affine	Increasing in both	R

The library is extensible — domain experts can add new atoms with verified curvature properties.

Think of it this way: Atoms are like LEGO bricks with labeled connectors. The label says "convex" or "concave" or "affine." The composition rules tell you which bricks you can snap together while preserving convexity.

An atom in the DCP library must specify:

Its curvature (convex/concave/affine), monotonicity, and range Only its gradient Only its range

Chapter 3: Sign Rules

A product-free expression has the form a + b^>x + c₁f₁(·) + ... + c_qf_q(·). The sign rules determine when such an expression is convex or concave based on the signs of the constants c:

f_j curvature	For c_jf_j to be convex	For c_jf_j to be concave
Convex	c_j ≥ 0	c_j ≤ 0
Concave	c_j ≤ 0	c_j ≥ 0
Affine	Any sign	Any sign

The intuition: Scaling a convex function by a positive constant preserves convexity. Scaling it by a negative constant flips it to concave. Affine functions are both convex and concave, so any scaling works.

The expression −3·exp(x) is:

Concave (negative constant times a convex function) Convex Neither

Chapter 4: Composition Rules

The composition rules determine the curvature of f(g(x)) from the properties of f and g:

f curvature	f monotonicity	g curvature	f(g(x)) curvature
Convex	Nondecreasing	Convex	Convex
Convex	Nonincreasing	Concave	Convex
Concave	Nondecreasing	Concave	Concave
Concave	Nonincreasing	Convex	Concave

Key insight: The composition rules are sufficient but not necessary. exp(sin(x)) for x ∈ [−π, 0] is convex (composition rules confirm: exp is convex+nondecreasing, sin is convex on this domain). But sqrt(exp(x)) is also convex, yet the rules are inconclusive (sqrt is concave). This is the conservatism tradeoff.

exp(g(x)) is convex when g is:

Convex (because exp is convex and nondecreasing) Concave Affine only

Chapter 5: Verification

DCP verification is a recursive tree walk. Starting from the root expression, apply the sign rules and composition rules at each node. If every node passes, the expression is verified as convex (or concave).

Range analysis propagates bounds upward through the expression tree, using interval arithmetic to determine whether the argument of each atom falls within a domain where its curvature holds.

Think of it this way: Verification is like type-checking in a programming language. Each expression gets a "type" (convex, concave, affine, constant). The rules define valid type combinations. If the type-check passes, the program (optimization problem) is guaranteed to be valid (convex).

DCP verification is analogous to:

Type-checking in a programming language Gradient computation Random sampling

Chapter 6: Canonicalization

Once verified, the problem must be transformed into a standard form that a solver can handle (typically a conic program or semidefinite program). Each atom has a canonicalization recipe that introduces auxiliary variables and constraints to linearize nonlinear terms.

For example, exp(x) ≤ t is canonicalized using the exponential cone. The norm ||x|| ≤ t is canonicalized using a second-order cone constraint. The system applies these recipes recursively to flatten the entire expression tree.

Key insight: Canonicalization trades problem complexity for problem size. A compact DCP expression might expand into many auxiliary variables and constraints, but the resulting form is in a standard format that mature solvers handle efficiently.

Canonicalization transforms a DCP problem into:

A standard conic form with auxiliary variables that a solver can handle An unconstrained problem A genetic algorithm

Chapter 7: Solving

After canonicalization, the problem is passed to a conic solver such as SCS, ECOS, or Mosek. These solvers use interior point methods (Chapter 10) tailored to conic structure.

Frameworks implementing DCP include Convex.jl (Julia), CVXPY (Python), and CVX (MATLAB). These tools let you write optimization problems in a natural mathematical syntax and automatically verify, canonicalize, and solve them.

The DCP workflow: (1) Write the problem using DCP-compliant expressions. (2) The system verifies convexity by applying the grammar rules. (3) The system canonicalizes to conic form. (4) A conic solver finds the global optimum. The user never has to think about the reduction — just write the math.

CVXPY and Convex.jl are tools that implement:

Disciplined convex programming (automatic verification + solving) Genetic algorithms Neural network training

Chapter 8: Summary

Concept	Key Fact
DCP grammar	Rules that guarantee convexity of composed expressions
Atom library	Functions with known curvature, monotonicity, and range
Sign rules	Positive scaling preserves curvature; negative scaling flips it
Composition rules	f(g(x)) curvature from f's curvature + monotonicity + g's curvature
Canonicalization	Automatic transformation to conic form for solving

Looking ahead: Chapter 15 tackles multiobjective optimization — what happens when you have multiple competing objectives and must find the Pareto frontier of tradeoffs.

DCP is conservative, meaning:

Some convex problems cannot be expressed in DCP form, but all DCP problems are convex All convex problems can be expressed in DCP form DCP problems may not be convex