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.

\[ \begin{array}{ll} \text{minimize} & c^\top x\\ \text{subject to} & Gx \preceq h,\quad Ax = b, \end{array} \]

with variable \(x\) (length \(n\)); the data \(c, G, h, A, b\) are constant and every expression is affine in \(x\). (\(\preceq\) is the componentwise \(\le\) for vectors.)

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.

\[ \begin{array}{ll} \text{minimize} & \frac{1}{2}\,x^\top P x + q^\top x\\ \text{subject to} & Gx \preceq h,\quad Ax = b, \end{array} \]

with \(P \succeq 0\) (positive semidefinite) — that condition is exactly what makes the objective convex. Taking \(P = 0\) recovers an LP.

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.

\[ \begin{array}{ll} \text{minimize} & f^\top x\\ \text{subject to} & \| A_i x + b_i \|_2 \le c_i^\top x + d_i,\quad i = 1,\dots,m,\\ & Fx = g. \end{array} \]

Each “norm \(\le\) affine” row is a second-order cone constraint — it forces the pair \((A_i x + b_i,\; c_i^\top x + d_i)\) into the cone \(\{(y, t) : \|y\|_2 \le t\}\). 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.

\[ \begin{array}{ll} \text{minimize} & c^\top x\\ \text{subject to} & x_1 F_1 + \cdots + x_n F_n + G \;\succeq\; 0,\quad Ax = b, \end{array} \]

where \(F_1,\dots,F_n, G\) are symmetric matrices and \(\succeq 0\) means positive semidefinite; that matrix inequality is a linear matrix inequality (LMI). Equivalently, the variable can itself be a symmetric matrix \(X \succeq 0\). Here we compute the largest eigenvalue of a matrix \(M\) as \(\min\{t : tI - M \succeq 0\}\) (an LMI in the scalar \(t\)):

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).