Linear, Quadratic, and Semidefinite Programming

Hierarchy of Convex Problems

Convex programming is a "family" of optimization problems of varying complexity. Linear programming (LP) is the simplest: linear objective, linear constraints. Quadratic programming (QP) involves a quadratic objective. Second-order cone programming (SOCP) has conic constraints. Semidefinite programming (SDP) has matrix constraints. Each subsequent class strictly generalizes the previous one. Understanding this hierarchy allows one to choose the right tool for a specific problem.

Linear Programming (LP)

Standard form: min $c^\mathrm{T}x$ subject to $Ax \leq b$, $x \geq 0$.

Here $c \in \mathbb{R}^n$ is the vector of objective coefficients, $A \in \mathbb{R}^{m \times n}$ is the constraint matrix, $b \in \mathbb{R}^m$ is the right-hand sides.

Geometry: the feasible region is a convex polyhedron (polytope). The linear objective function attains its minimum at a vertex of the polyhedron. The simplex method (Dantzig, 1947) "moves" from vertex to vertex until it finds the optimum. The interior point method moves through the interior.

Duality in LP: the primal problem min $c^\mathrm{T}x$ subject to $Ax \geq b$, $x \geq 0$ has a dual max $b^\mathrm{T}y$ subject to $A^\mathrm{T}y \leq c$, $y \geq 0$. Strong duality always holds (if both problems are feasible).

Example — Diet Problem: minimize the cost of a set of products while ensuring sufficient nutrients. This is a classic LP problem, solved back in the 1940s.

Quadratic Programming (QP)

Standard form: min $(1/2)x^\mathrm{T}Px + q^\mathrm{T}x$ subject to $Ax \leq b$

$P \in \mathbb{R}^{n \times n}$ is the matrix for the quadratic term; it must be $\succeq 0$ (positive semidefinite) for the problem to be convex.

Why $\succeq 0$? The quadratic form $x^\mathrm{T}Px$ is convex if and only if $P \succeq 0$. Criterion: all eigenvalues are $\geq 0$.

Application: Markowitz Portfolio Optimization

Given a set of assets with expected returns $\mu_i$ and a covariance matrix $\Sigma$. The problem: minimize risk $w^\mathrm{T}\Sigma w$ subject to achieving a target return $\mu^\mathrm{T}w \geq r^*$ and a budget constraint $\Sigma w_i = 1$.

min $(1/2)w^\mathrm{T}\Sigma w$ subject to $\mu^\mathrm{T}w \geq r^*$, $1^\mathrm{T}w = 1$, $w \geq 0$

This is QP! The covariance matrix $\Sigma$ is inherently $\succeq 0$.

Application: SVM

min $(1/2)|w|^2$ subject to $y_i(w^\mathrm{T}x_i + b) \geq 1$ — strictly convex QP with a unique solution.

Second-Order Cone Programming (SOCP)

SOCP constraint: $|A_i x + b_i| \leq c_i^\mathrm{T}x + d_i$ — the norm of a vector is bounded by a linear function of $x$.

Geometrically: the feasible set is the intersection of second-order cones and affine subspaces.

Includes LP and QP: LP is a special case (when $A_i = 0$, degenerates to linear). QP with $P \succeq 0$ allows an SOCP formulation.

Example: Robust Linear Programming

Suppose we have LP, but the matrix $A = \bar{A} + \delta A$ contains an error. Problem: min $c^\mathrm{T}x$ subject to $(\bar{A} + \delta A)x \leq b$ for all $|\delta A|_F \leq \rho$.

Robust constraint: $\bar{A}_i^\mathrm{T}x + \rho|x_i| \leq b_i$ — this is an SOCP constraint!

Semidefinite Programming (SDP)

SDP problem: $\min_{X} \mathrm{tr}(CX)$ subject to $\mathrm{tr}(A_i X) = b_i$, $i=1,...,m$, $X \succeq 0$

where $X$ is a symmetric $n \times n$ matrix, $X \succeq 0$ means positive semidefinite.

Variable — matrix $X$! This generalizes LP (variable — vector $x$) to the matrix case.

Why is this a convex problem? The set of $\succeq 0$ matrices is a convex cone. The objective function $\mathrm{tr}(CX)$ is linear.

Complete Analysis: SDP Relaxation of the MAX-CUT Problem

Problem: graph $G = (V, E)$. Partition the vertices into two sets $S$ and $V \setminus S$, maximizing the number of edges between them.

ILP formulation: $x_i \in {-1, +1}$. Cut: $(1/4)\sum_{(i,j)\in E} (1 - x_i x_j)$. NP-hard.

SDP relaxation (Goemans-Williamson, 1995): replace $x_i \in {\pm 1}$ by vectors $v_i \in \mathbb{R}^n$ with $|v_i| = 1$. Product $x_i x_j \rightarrow$ scalar product $v_i^\mathrm{T} v_j$. Matrix $Y_{ij} = v_i^\mathrm{T} v_j \succeq 0$!

max $(1/4)\sum_{(i,j)\in E}(1 - Y_{ij})$ subject to $Y_{ii} = 1$, $Y \succeq 0$

Solution: this is SDP! Randomized rounding (random hyperplane) yields a $0.878$-approximation of MAX-CUT.

What does this mean: the algorithm is guaranteed to find a cut constituting at least $87.8%$ of the optimum. This is the best known polynomial algorithm.

Solvers

In practice, problems are solved by specialized packages:

• CVXPY (Python): high-level language for describing problems
• MOSEK: commercial, very fast for LP/QP/SOCP/SDP
• SCS: open, scalable for large SDP
• ECOS: efficient for embedded systems

Example in CVXPY: x = cp.Variable(n); prob = cp.Problem(cp.Minimize(0.5*cp.quad_form(x,P) + q.T@x), [A@x <= b]); prob.solve()

Hierarchy of Problem Classes

There exists a natural hierarchy of convex conic programs by expressive power and complexity: $LP \subset QP \subset SOCP \subset SDP$

Each subsequent class is strictly more powerful: SDP can express SOCP via standard embedding, SOCP includes QP with positive semidefinite matrices, QP includes LP. Complexity also increases: LP solved in $O(n^{3.5})$ by simplex or interior point, QP in $O(n^3)$, SOCP in $O(n^{3.5})$, SDP in $O(n^{6.5})$ for general problems, though structured ones may be much faster.

Industrial Solvers

• LP: Gurobi, CPLEX, MOSEK, HiGHS (open source) — millions of variables in seconds
• QP: OSQP, qpOASES (for real-time control), Gurobi
• SOCP: ECOS, MOSEK, SCS — widely used in finance for robust portfolios
• SDP: SDPT3, SeDuMi, MOSEK, COSMO — for problems up to several thousand variables
• Universal modeling languages: CVXPY, JuMP, YALMIP — allow writing the problem in natural form and automatically reducing to canonical for the solver

Modern Applications

• LP in aviation: American Airlines solves problems with millions of variables for crew assignments
• QP in robotics: quadratic regulators (LQR) and MPC (Model Predictive Control) — foundation for controlling manipulators and quadcopters
• SOCP in finance: Goldfarb-Aiyengar robust portfolios account for uncertainty in return estimates using ellipsoidal sets
• SDP in quantum computing: quantum tomography problems, estimation of quantum channels are formulated via SDP
• SDP in combinatorics: Goemans-Williamson’s MAX-CUT relaxation yields a $0.878$-approximation via SDP — a record in theoretical computer science