Linear Programs#
A linear program (LP) minimises a linear function over a polyhedron defined by linear inequalities:
\min_x &\quad c^T x \\ \text{s.t.} &\quad Ax \leq b \end{aligned}$$ 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:** $$\begin{aligned} \min_x &\quad 2x_1 + 3x_2 \quad (\text{cost}) \\ \text{s.t.} &\quad 3x_1 + x_2 \geq 10 \quad (\text{protein}) \\ &\quad x_1 + 2x_2 \geq 8 \quad (\text{carbs}) \\ &\quad x_1, x_2 \geq 0 \end{aligned}$$ 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: $$\begin{aligned} \min_x &\quad \tfrac{1}{2}x^T Q x + c^T x \\ \text{s.t.} &\quad Ax \leq b \end{aligned}$$ 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 <Glossary term="SDP" /> (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. <Exercise type="multiple-choice" question="Which $Q$ makes $\min \tfrac{1}{2}x^T Q x + c^T x$ a convex QP?" options={["$Q = \\begin{pmatrix} -1 & 0 \\\\ 0 & -1 \\end{pmatrix}$", "$Q = \\begin{pmatrix} 2 & 0 \\\\ 0 & 1 \\end{pmatrix}$", "$Q = \\begin{pmatrix} 0 & 2 \\\\ 2 & 0 \\end{pmatrix}$", "$Q = \\begin{pmatrix} 1 & 3 \\\\ 3 & 1 \\end{pmatrix}$"]} correctIndex={1} explanation="$Q = \mathrm{diag}(2, 1)$ has eigenvalues $2, 1 > 0$, so $Q \succ 0$. The first is negative definite, the third has eigenvalues $\pm 2$ (indefinite; the 0 on diagonal makes it a hyperbolic saddle), and the fourth has eigenvalues $4, -2$." /> <Quiz questions={[ { type: "multiple-choice", question: "Which of these is an LP?", options: ["$\min x^2$ s.t. $x \geq 1$", "$\min 2x + 3y$ s.t. $x + y \leq 5, x, y \geq 0$", "$\min \|x\|_2$ s.t. $Ax = b$", "$\min x^T Q x$ s.t. $x \geq 0$"], correctIndex: 1, explanation: "An LP has a linear objective and linear constraints. The first has a quadratic objective; the third is SOCP; the fourth is QP." }, { type: "multiple-choice", question: "A quadratic program is convex if and only if:", options: ["The constraints are linear", "$Q$ is symmetric", "$Q \succeq 0$", "The problem has a unique solution"], correctIndex: 2, explanation: "Convexity requires $Q \succeq 0$ (PSD Hessian). Symmetry alone is not enough — $\begin{pmatrix}0 & 1 \\ 1 & 0\end{pmatrix}$ is symmetric but indefinite." }, { type: "multiple-choice", question: "Which best describes an SOCP constraint?", options: ["$\|Ax\|_\infty \leq 1$", "$\|Ax\|_2 \leq c^T x + d$", "$Ax = b$", "$x^T Q x \leq 1$"], correctIndex: 1, explanation: "SOCP constraints are Euclidean norm bounds: $\|Ax + b\|_2 \leq c^T x + d$. The $\ell_\infty$ version is an LP (polyhedral), and $x^T Q x \leq 1$ is a quadratic constraint (QCQP)." } ]} /> ## 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. ```python 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() ```