3 Disciplined Convex Programming

What you’ll be able to do

Read the sign and curvature of any CVXR expression, understand the one composition rule that decides whether CVXR accepts a problem, recognize the two legal objective forms and three legal constraint forms, reformulate a rejected problem into an equivalent accepted one, and use visualize() to locate a violation.

3.1 Why was that problem rejected?

At the end of Chapter 2, CVXR refused to Maximize(x^2 + y^2). It was not being fussy: maximizing a bowl-shaped (convex) function has no finite solution in general, and more importantly CVXR will only accept problems it can certify are convex. The certificate is a small rule set called Disciplined Convex Programming (DCP). This chapter is the one piece of theory in the book — everything else rests on it. The good news: the rules are mechanical, and CVXR checks them for you.

For an interactive companion, see dcp.stanford.edu.

3.2 Expressions carry a sign and a curvature

A CVXR expression is built from variables, constants, the arithmetic operators + - * %*% /, and a library of atoms (abs, sqrt, square, p_norm, …). DCP tags every (sub)expression with a sign and a curvature, computed from its parts. Both tags are always correct, though the simple analysis sometimes says “unknown” when a deeper argument could do better.

3.2.1 Sign

Each expression is flagged nonnegative, nonpositive, zero, or unknown:

x <- Variable()
expr_sign(x)            # a free variable could be anything

[1] "UNKNOWN"

expr_sign(abs(x))       # absolute value is nonnegative

[1] "NONNEGATIVE"

expr_sign(Constant(-3)) # constants are read off their value

[1] "NONPOSITIVE"

3.2.2 Curvature

Each expression is constant, affine, convex, concave, or unknown. The picture to keep in mind:

convex = upward-curving, concave = downward-curving, affine = flat.
constant \(\subset\) affine \(\subset\) both convex and concave.

curvature(x)                # a variable is affine

[1] "AFFINE"

curvature(abs(x))           # convex

[1] "CONVEX"

curvature(sqrt(x))          # concave

[1] "CONCAVE"

curvature(2 * x + 1)        # affine

[1] "AFFINE"

There are also yes/no predicates, handy in code:

c(convex  = is_convex(abs(x)),
  concave = is_concave(sqrt(x)),
  affine  = is_affine(2 * x + 1))

 convex concave  affine 
   TRUE    TRUE    TRUE

3.3 The one rule: composition

Every curvature tag comes from a single composition rule. To conclude that \(f(e_1,\ldots,e_n)\) is convex, \(f\) must be convex and for each argument \(e_i\) one of these holds:

\(f\) is increasing in \(e_i\) and \(e_i\) is convex, or
\(f\) is decreasing in \(e_i\) and \(e_i\) is concave, or
\(e_i\) is affine or constant.

(The mirror image gives concave.) Whether \(f\) is increasing or decreasing can depend on sign — abs increases for positive arguments and decreases for negative ones, which is exactly why sign analysis matters.

Let’s watch it work on sqrt(1 + square(x)):

curvature(square(x))            # square is convex

[1] "CONVEX"

curvature(1 + square(x))        # affine(+) of convex -> convex

[1] "CONVEX"

curvature(sqrt(1 + square(x)))  # sqrt needs a CONCAVE argument -> UNKNOWN

[1] "UNKNOWN"

square(x) is convex, so 1 + square(x) is convex. But sqrt is concave and increasing, so by the rule it can only accept a concave argument. Handed a convex one, DCP cannot certify the result — so it reports unknown.

3.4 When DCP says no but the function is fine: reformulate

Here is the subtle part. sqrt(1 + square(x)) genuinely is a convex function of x — DCP just can’t see it through that particular expression. The fix is to rewrite it as something DCP recognizes. The same quantity is the Euclidean norm of the vector \([1, x]\):

curvature(p_norm(vstack(1, x), 2))   # CONVEX -- now certified

[1] "CONVEX"

Same value, accepted formulation. Reformulating a rejected expression into an equivalent accepted one is the core CVXR skill — you will do it often, and the atom function reference is your toolbox.

3.5 DCP problems

A problem is DCP — and therefore convex and solvable — when its objective has one of two forms and every constraint has one of three:

Objective	Constraints
`Minimize(convex)`	`affine == affine`
`Maximize(concave)`	`convex <= concave`
	`concave >= convex`

Check any problem, objective, or constraint with is_dcp():

y <- Variable()

prob1 <- Problem(Minimize((x - y)^2), list(x + y >= 0))
prob2 <- Problem(Maximize(sqrt(x - y)), list(2 * x - 3 == y, x^2 <= 2))
c(prob1 = is_dcp(prob1), prob2 = is_dcp(prob2))

prob1 prob2 
 TRUE  TRUE

# A non-DCP objective and a non-DCP constraint:
c(max_sq   = is_dcp(Maximize(x^2)),
  bad_con  = is_dcp(sqrt(x) <= 2))

 max_sq bad_con 
  FALSE   FALSE

Call psolve() on a non-DCP problem and CVXR stops you:

psolve(Problem(Minimize(sqrt(x))))

Error in `construct_solving_chain()`:
! Problem is not DCP compliant.
ℹ However, the problem is DQCP. Try `psolve(problem, qcp = TRUE)`.

3.6 Finding the violation with `visualize()`

For anything bigger than a toy, visualize() draws the expression tree with each node’s curvature, flagging the offending node so you know where to reformulate:

visualize(Problem(Minimize(sqrt(1 + square(x)))))

t_3 = Power(...)  [unknown, \mathbb{R}_+, 1x1]
\-- t_2 = AddExpression(...)  [convex, \mathbb{R}_+, 1x1]
    |-- 1  [constant, 1x1]
    \-- t_1 = Power(...)  [convex, \mathbb{R}_+, 1x1]
        \-- var1  [affine, 1x1]

  ✗ Problem is NOT DCP compliant.
  Objective (Minimize): requires convex expression
    ✗ Power: unknown  [1x1]
      arg 1: convex, increasing  (cvx-rule ✓, ccv-rule ✗)
      => Power is concave, but DCP concave composition fails at arg 1.
      Hint: var1 must be nonneg (>= 0)

  t_{1} = phi^{(.)^2}({var1})
  t_{2} = {1} + {t_{1}}
  t_{3} = phi^{(.)^{0.5}}({t_{2}})

  t_{1} >= phi^{(.)^2}({var1})
  t_{2} = {1} + {t_{1}}
  t_{3} = phi^{(.)^{0.5}}({t_{2}})

  (\frac{1+t_{1}}{2},  \frac{1-t_{1}}{2},  {var1}) in Q^3
  t_{2} = {1} + {t_{1}}
  t_{3} = phi^{(.)^{0.5}}({t_{2}})    [conic form: see canonicalizer]

See the Visualization page for the full feature set (curvature coloring, fix hints, HTML trees).

3.7 Bonus: bounds propagation

Since CVXR 1.9.1, get_bounds() propagates interval bounds through any expression — useful for sanity-checking a model:

xb <- Variable(3, bounds = list(-1, 2))
get_bounds(2 * xb + 1)   # affine map of [-1, 2]  ->  [-1, 5]

[[1]]
     [,1]
[1,]   -1
[2,]   -1
[3,]   -1

[[2]]
     [,1]
[1,]    5
[2,]    5
[3,]    5

get_bounds(abs(xb))      # through an atom        ->  [0, 2]

[[1]]
     [,1]
[1,]    0
[2,]    0
[3,]    0

[[2]]
     [,1]
[1,]    2
[2,]    2
[3,]    2

3.8 Exercises

Exercise 1. Without running it, predict the curvature of square(sqrt(x)) for x >= 0, then check with curvature(). Why does DCP report what it does?

Solution

curvature(square(sqrt(x)))

[1] "UNKNOWN"

sqrt(x) is concave; square is convex and (for nonnegative arguments) increasing, so it wants a convex argument. A concave argument breaks the rule, so DCP returns unknown — even though the composition equals x, which is affine. Reformulating (here, just writing x) would fix it.

Exercise 2. Is Problem(Maximize(-square(x) - square(y)), list(x + y == 1)) DCP? Predict, then check, then solve it.

Solution

p <- Problem(Maximize(-square(x) - square(y)), list(x + y == 1))
is_dcp(p)

[1] TRUE

psolve(p)

[1] -0.5

c(x = value(x), y = value(y))

  x   y 
0.5 0.5

-square(·) is concave and the constraint is affine == affine, so the problem is Maximize(concave) subject to a legal constraint — DCP, with optimum \(x = y = 1/2\).

Exercise 3 (⭐). The expression x^2 / y (with y > 0) is convex — the quadratic-over-linear function. DCP cannot see it from x^2 / y (division by a non-constant is rejected). Find a CVXR atom that expresses it. Hint: search the function reference for “quad over lin”.

Solution

The atom is quad_over_lin(x, y) \(= x^2/y\), certified convex:

yp <- Variable(pos = TRUE)
curvature(quad_over_lin(x, yp))

[1] "CONVEX"

This is the reformulation skill again: the function is convex; you just need the formulation DCP recognizes.

3.9 Takeaways

Every expression has a sign and a curvature, computed by one composition rule.
A problem is solvable when it is Minimize(convex) or Maximize(concave) with constraints affine == affine, convex <= concave, or concave >= convex.
is_dcp() checks it; visualize() shows where a violation is.
When a convex function is rejected, reformulate it into an equivalent atom — the single most useful habit in CVXR.

3.1 Why was that problem rejected?

3.2 Expressions carry a sign and a curvature

3.2.1 Sign

3.2.2 Curvature

3.3 The one rule: composition

3.4 When DCP says no but the function is fine: reformulate

3.5 DCP problems

3.6 Finding the violation with visualize()

3.7 Bonus: bounds propagation

3.8 Exercises

3.9 Takeaways

3.6 Finding the violation with `visualize()`