Week 4: LP, QP, and Conic Form

Linear programs#

A linear program (LP) minimises a linear function over a polyhedron defined by linear inequalities:

where $c \in \mathbb{R}^d$, $A \in \mathbb{R}^{m \times d}$, $b \in \mathbb{R}^m$. The feasible set $\{x \mid Ax \leq b\}$ is a convex polyhedron — the intersection of $m$ half-spaces.

Standard forms. There are several equivalent representations. Any LP can be converted between them:

• Inequality form: $Ax \leq b$ (as above).
• Equality form: $\min c^T x$ s.t. $Ax = b$, $x \geq 0$. Introduce slack variables $s = b - Ax \geq 0$.
• Symmetric cone form: Both inequalities and nonnegativity on subsets of variables.

Why LPs are easy. The objective is linear, the constraints are linear — the optimum (if it exists) lies at a vertex (extreme point) of the polyhedron. The simplex method crawls along edges from vertex to vertex; interior-point methods (Week 6) cut through the interior. Both are highly reliable for problems with thousands of variables and constraints.

Worked example — Diet problem:

Rewrite in inequality form ($\leq$): $-3x_1 - x_2 \leq -10$, $-x_1 - 2x_2 \leq -8$, $-x_1 \leq 0$, $-x_2 \leq 0$.

Solving: vertices are intersections of binding constraints. The vertex $(x_1, x_2) = (2.4, 2.8)$ from binding the two nutrient constraints gives cost $2(2.4) + 3(2.8) = 13.2$.

Quadratic programs#

A quadratic program (QP) adds a quadratic term in the objective:

with $Q \in \mathbb{R}^{d \times d}$ symmetric. The classification depends on $Q$:

• $Q \succeq 0$ (PSD): convex QP — the objective is convex, the feasible set is a polyhedron. Any local minimum is global; KKT is necessary and sufficient.
• $Q \succ 0$: strictly convex QP — unique solution; KKT system reduces to solving a linear complementarity problem.
• $Q$ indefinite: nonconvex QP — NP-hard in general. Multiple local minima; standard solvers only guarantee a local KKT point.

Equality-constrained QP. When $Ax = b$ (only equalities), the KKT conditions form a linear system:

$\begin{pmatrix} Q & A^T \\ A & 0 \end{pmatrix} \begin{pmatrix} x \\ \nu \end{pmatrix} = \begin{pmatrix} -c \\ b \end{pmatrix}$

This is the KKT matrix or saddle-point system — it appears everywhere from Newton's method (Week 8) to IPM steps (Week 6).

Worked example — Portfolio optimisation:

$\min_w \; \tfrac{1}{2} w^T \Sigma w \quad \text{s.t.} \quad \mathbf{1}^T w = 1,\; w \geq 0$

where $\Sigma$ is the covariance matrix of asset returns ($\Sigma \succeq 0$), $w$ is the weight vector. This is a convex QP: minimise risk subject to budget and no-shorting constraints.

From QP to geometry#

The QP objective's level sets are ellipsoids (when $Q \succ 0$) centred at the unconstrained minimiser $-Q^{-1}c$. The constraints carve a polyhedron from $\mathbb{R}^d$. The optimum is the point in the polyhedron that lies on the smallest ellipsoid — a purely geometric problem of finding the closest point (in the $Q$-norm) to the unconstrained centre, subject to linear inequalities.

When $Q = I$ and $c = 0$, the unconstrained minimiser is the origin, and the QP reduces to projecting the origin onto the polyhedron — equivalently, finding the minimum-norm point in the set. This interpretation is powerful: many constrained problems are projections in disguise, and projected gradient descent (intermediate Optim Week 9) is a primal first-order method for them.

Contrast with unconstrained GD. An unconstrained convex QP with $Q \succ 0$ is solved in one Newton step (Week 8). A constrained QP requires iterative methods — either active-set, IPM, or first-order projected methods. The constraints are what make the problem interesting.

Second-order cones#

A second-order cone program (SOCP) generalises LP and convex QP by allowing constraints of the form:

$\|A_i x + b_i\|_2 \leq c_i^T x + d_i$

where $A_i \in \mathbb{R}^{n_i \times d}$, $b_i \in \mathbb{R}^{n_i}$, $c_i \in \mathbb{R}^d$, $d_i \in \mathbb{R}$. The set $\{(y, t) \mid \|y\|_2 \leq t\}$ is the second-order cone (also called the Lorentz cone or ice-cream cone). SOCP constraints express Euclidean norm bounds.

Why SOCP is powerful. Many problems that look nonlinear become SOCP-representable:

• Robust least-squares: $\min_x \|Ax - b\|_2$ with bounded uncertainty in $A$ can often be cast as an SOCP.
• Huber loss: The Huber penalty can be represented as a projection onto a second-order cone.
• Quadratically constrained QP (QCQP): $\min x^T Q_0 x$ s.t. $x^T Q_i x \leq r_i$ with $Q_i \succeq 0$ is SOCP-representable (each constraint is $\|Q_i^{1/2} x\|_2 \leq \sqrt{r_i}$).

Worked example — Robust constraint:

Suppose we want $\min \|x\|_2^2$ subject to $a^T x \geq b$, where $a$ is uncertain: $a = \bar{a} + \Delta a$ with $\|\Delta a\|_2 \leq \rho$. The robust version requires $(\bar{a} + \Delta a)^T x \geq b$ for all admissible $\Delta a$. The worst case is $\min_{\|\Delta a\| \leq \rho} (\bar{a} + \Delta a)^T x = \bar{a}^T x - \rho\|x\|_2$. The robust constraint becomes:

$\rho \|x\|_2 \leq \bar{a}^T x - b$

which is an SOCP constraint: $\|x\|_2 \leq (\bar{a}^T x - b)/\rho$.

Modeling checklist#

When facing a structured optimisation problem, ask:

1. Is the objective quadratic? If yes and $Q \succeq 0$, you have a convex QP. If constraints are linear, IPM solvers are fast and reliable.
2. Do constraints involve Euclidean norms? Check if the problem can be written as an SOCP — many robust formulations, quadratically constrained problems, and regularised models fit.
3. Is the problem an LP? If the objective and constraints are all linear, simplex or IPM solve it exactly. Do not use gradient descent on an LP.
4. Is the structure richer? If you see matrix variables with PSD constraints, think SDPSemidefinite Program (Week 5). If the constraints are generic nonlinear, you are in the domain of general nonlinear programming — first-order methods or Newton-based approaches from Weeks 8–10 apply.

The skill this course teaches is recognising when a problem has structure that specialised solvers can exploit, versus when you must fall back to general-purpose gradient-based methods.

Knowledge Check#

Browser lab#

Project the origin onto the polytope $\{ (x,y) \mid x + y \geq 2,\; x \geq 0,\; y \geq 0 \}$ using projected gradient descent. This is a poor-man's QP: $\min \|(x,y)\|_2^2$ subject to linear inequalities. Compare the PG iterate to the analytic solution.

import numpy as np
import matplotlib.pyplot as plt

# Problem: min ||x||^2 s.t. x + y >= 2, x >= 0, y >= 0
# Analytic solution: (1, 1) — projection of origin onto x + y = 2 in first quadrant

def project_onto_simplex(xy):
    """Project onto constraints: x >= 0, y >= 0, x + y >= 2"""
    x, y = xy
    # Project onto individual nonnegativity
    x = max(x, 0)
    y = max(y, 0)
    # If x + y < 2, project onto the line x + y = 2 in positive orthant
    if x + y < 2:
        # Project (x, y) onto hyperplane x + y = 2, then clip again
        deficit = 2 - (x + y)
        x = x + deficit / 2
        y = y + deficit / 2
        x = max(x, 0)
        y = max(y, 0)
        # Re-check — may need one more pass for corner cases
        if x + y < 2 - 1e-8:
            if x <= 0:
                y = 2.0
            else:
                x = 2.0
    return np.array([x, y])

# Projected gradient descent
eta = 0.5
n_steps = 30
xy = np.array([-2.0, 3.0])  # infeasible start
path_pg = [xy.copy()]

for _ in range(n_steps):
    grad = 2 * xy  # gradient of ||x||^2
    xy = xy - eta * grad
    xy = project_onto_simplex(xy)
    path_pg.append(xy.copy())

path_pg = np.array(path_pg)
print(f"Final PG iterate: ({path_pg[-1,0]:.4f}, {path_pg[-1,1]:.4f})")
print(f"Analytic solution: (1.0, 1.0)")
print(f"Distance to optimum: {np.linalg.norm(path_pg[-1] - np.array([1, 1])):.6f}")

# Visualise
xs = np.linspace(-0.5, 3.5, 200)
ys = np.linspace(-0.5, 3.5, 200)
X, Y = np.meshgrid(xs, ys)
Z = X**2 + Y**2

fig, ax = plt.subplots(figsize=(6, 5.5))
ax.contour(X, Y, Z, levels=20, cmap="viridis", alpha=0.6)

# Feasible region
poly_x = [0, 2, 3, 0]
poly_y = [2, 0, 0, 3]
ax.fill(poly_x, poly_y, alpha=0.15, color="green", label="feasible region")

ax.plot(path_pg[:, 0], path_pg[:, 1], "o-", color="tab:red", markersize=4, label="PG iterates")
ax.plot(1, 1, "x", color="black", markersize=12, label="optimum (1,1)")
ax.plot(0, 0, "s", color="gray", markersize=8, label="unconstrained min (0,0)")
ax.set_xlabel("x")
ax.set_ylabel("y")
ax.set_title("Projected GD: project origin onto polytope")
ax.legend()
ax.set_aspect("equal")
plt.show()

print("Notice: projected GD lands on (1.0000, 1.0000) — the projection of the origin onto x + y ≥ 2 — with distance 0.000000.")

Key takeaways#

• The convex program hierarchy is LP inside QP inside SOCP inside SDP. Moving outward buys modelling power at the cost of a harder solve.
• An LP has a linear objective and polyhedral constraints, and its optimum (when one exists) sits at a vertex; simplex and interior-point methods both solve it reliably.
• A QP is convex exactly when $Q \succeq 0$. If $Q$ is indefinite the problem is NP-hard and a solver returns only a local KKT point.
• Equality-constrained QPs reduce to the saddle-point KKT system in $x$ and the equality multipliers.
• SOCP constraints are Euclidean norm bounds $\|A_i x + b_i\|_2 \leq c_i^T x + d_i$, and many robust and quadratically constrained problems become SOCP-representable.
• Recognising structure is the skill: match the problem to LP, QP, SOCP, or SDP before reaching for a generic gradient method.

Further reading#

• Stephen Boyd & Lieven Vandenberghe, Convex Optimization (Cambridge University Press, 2004) — LP, QP, and the second-order cone in one place, with modelling examples.
• Dimitri P. Bertsekas, Convex Optimization Algorithms (Athena Scientific, 2015) — how LP and QP solvers actually work.
• Jorge Nocedal & Stephen Wright, Numerical Optimization (2nd ed., Springer, 2006) — quadratic programming in depth.