4 Types of Convex Optimization Problems

What you’ll be able to do

Recognize the standard families of convex problems — LP, QP, SOCP, SDP — see a tiny CVXR example of each, and understand that you rarely have to choose: DCP (Chapter 3) classifies your problem and CVXR routes it to a capable solver.

4.1 A hierarchy of problem classes

Convex problems come in named families of increasing generality. Each contains the previous one as a special case:

\[\text{LP} \;\subset\; \text{QP} \;\subset\; \text{SOCP} \;\subset\; \text{SDP}.\]

You usually do not pick the family by hand. You write the problem from atoms; DCP certifies it is convex; and CVXR canonicalizes it into a cone program and hands it to a solver that can handle the cones involved (you saw this chain in the verbose output of Chapter 2). Still, it helps to recognize the families — they tell you what is expressible and which solvers apply.

4.2 Linear program (LP)

Linear objective, linear constraints. The workhorse of operations research.

x <- Variable(2)
lp <- Problem(Minimize(sum(c(2, 3) * x)),
              list(x >= 0, x[1] + x[2] >= 1, x <= 5))
psolve(lp)

[1] 2

value(x)

             [,1]
[1,] 1.000000e+00
[2,] 8.824137e-10

4.3 Quadratic program (QP)

A convex quadratic objective with linear constraints. Least squares (and ridge, and the Markowitz portfolio of Chapter 9) live here.

set.seed(1)
A <- matrix(rnorm(20), 10, 2); b <- rnorm(10)
z <- Variable(2)
# constrained least squares: quadratic objective, linear constraint -> a QP
psolve(Problem(Minimize(sum_squares(A %*% z - b)), list(z >= 0)))

[1] 5.897455

value(z)

              [,1]
[1,] -2.293091e-21
[2,]  4.785967e-01

4.4 Second-order cone program (SOCP)

Adds constraints involving the Euclidean norm — “second-order cones.” Anything with a p_norm(., 2), huber, or robust-constraint flavor is typically an SOCP. Minimizing a norm subject to a budget is the canonical toy:

xs <- Variable(3)
psolve(Problem(Minimize(p_norm(xs, 2)), list(sum(xs) == 1)))

[1] 0.5773503

round(value(xs), 4)             # 1/3 each -> the min-norm point on the simplex plane

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

4.5 Semidefinite program (SDP)

The most general of the four: constraints that a matrix is positive semidefinite (\(\succeq 0\)), written with %>>%. Eigenvalue optimization, covariance/correlation problems, and relaxations of hard combinatorial problems are SDPs. Here we compute the largest eigenvalue of a matrix \(M\) as \(\min\{t : tI - M \succeq 0\}\):

M <- matrix(c(2, 1, 1, 2), 2, 2)
t <- Variable(1)
psolve(Problem(Minimize(t), list((t * diag(2) - M) %>>% 0)))   # = lambda_max(M) = 3

[1] 2.999994

Variables can themselves be matrices constrained to be PSD — e.g. finding the nearest unit-diagonal PSD matrix to \(M\):

X <- Variable(c(2, 2), PSD = TRUE)
psolve(Problem(Minimize(sum_squares(X - M)), list(diag(X) == 1)))

[1] 2

round(value(X), 3)

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

4.6 And their integer cousins

Allow some variables to be integer or boolean and each family gains a mixed-integer version (MILP, MIQP, MI-SOCP). Those are no longer convex — they are combinatorial — but CVXR expresses them the same way and hands them to an integer-capable solver. We devote Chapter 11 to them.

4.7 Takeaways

Convex problems form a hierarchy LP \(\subset\) QP \(\subset\) SOCP \(\subset\) SDP; each tiny example above is a few lines of CVXR.
You write problems from atoms, not by naming a family — DCP classifies and CVXR routes to a solver automatically.
Adding integrality gives the mixed-integer versions (Chapter 11).

For more worked basics, see the CVXR examples gallery (least squares, LP, QP, SOCP, SDP).