Kochenderfer & Wheeler, Chapter 12

Linear Programming

When the objective and constraints are all linear, the simplex algorithm finds the global optimum by walking along vertices of a polytope.

Prerequisites: Chapter 10 (Constraints), Chapter 11 (Duality).

Chapters

Simulations

Quizzes

Chapter 0: What Is an LP?

A linear program (LP) is an optimization problem where both the objective function and all constraints are linear:

minimize c^>x subject to Ax ≤ b

Linear programs arise naturally in transportation, manufacturing, economics, and operations research. Many non-linear problems can be approximated as LPs. Modern solvers handle millions of variables and millions of constraints.

The core idea: Because both the objective and constraints are linear, the feasible set forms a convex polytope (a shape with flat faces). The optimum always lies at a vertex of this polytope. The simplex algorithm exploits this by walking from vertex to vertex, always improving the objective, until it reaches the optimal vertex.

In a linear program, the optimal solution always lies at:

A vertex of the feasible polytope The center of the feasible region A saddle point

Chapter 1: Problem Forms

Linear programs can be written in three equivalent forms:

Form	Structure	Use Case
General	min c^>x s.t. A_LEx ≤ b_LE, A_EQx = b_EQ	Natural problem statement
Standard	min c^>x s.t. Ax ≤ b, x ≥ 0	Simplified for analysis
Equality	min c^>x s.t. Ax = b, x ≥ 0	Used by simplex algorithm

Converting between forms: equalities become two inequalities, unrestricted variables x become x⁺ − x⁻ (both ≥ 0), and inequalities become equalities by adding slack variables s ≥ 0: Ax + s = b.

Key insight: Many problems that don't look linear can be converted to LPs. For example, minimizing ||Ax − b||₁ (L1 norm) can be reformulated as a linear program by introducing auxiliary variables. Similarly for ||Ax − b||_∞.

A slack variable converts an inequality Ax ≤ b into an equality by:

Adding a non-negative variable s: Ax + s = b, s ≥ 0 Removing the constraint entirely Squaring both sides

Chapter 2: Geometry of LPs

The objective c^>x creates parallel contour lines perpendicular to c, increasing in the direction of c. Each inequality w^>x ≤ b defines a half-space. The feasible set is the intersection of all half-spaces — a convex polytope.

Possible outcomes:

Case	Description
Vertex optimum	A single vertex minimizes the objective (most common)
Edge/face optimum	An entire edge or face achieves the minimum (infinite solutions)
Unbounded	The objective can decrease without limit (insufficient constraints)
Infeasible	No point satisfies all constraints (over-constrained)

Think of it this way: Imagine tilting a flat board (the objective) and placing it on a crystal (the polytope). The board touches the crystal at a corner (vertex), edge, or face. The simplex algorithm is like rolling a marble along the edges of the crystal, always downhill.

The feasible set of a linear program is always:

A convex polytope (intersection of half-spaces) A sphere A nonconvex region

Chapter 3: Vertices & Partitions

In equality form (Ax = b, x ≥ 0) with A ∈ R^m×n, a vertex is defined by a partition B of m indices. The basic variables x_B = A_B⁻¹b are determined by the constraints; the remaining non-basic variables x_V are set to zero.

A partition B defines a vertex only if x_B ≥ 0 (all basic variables are non-negative). The simplex algorithm works by swapping indices between B and V, moving from one vertex to an adjacent vertex.

Think of it this way: A vertex is where enough constraints are "tight" (active) to pin down the solution. In 2D, two lines intersecting give a vertex. In 3D, three planes give a vertex. The partition B tells you which constraints are tight.

In the simplex method, a vertex is defined by a set of:

Basic indices whose corresponding variables are determined by Ax = b Random sample points Gradient directions

Chapter 4: Simplex Algorithm

At each vertex, the simplex algorithm checks whether moving to a neighboring vertex would improve the objective. The test uses the reduced cost μ_V:

μ_V = c_V − A_V^>λ, where λ = A_B^−>c_B

If any component of μ_V is negative, moving in that direction decreases the objective. The most negative component determines which non-basic variable enters the basis. If all components are non-negative, the current vertex is optimal.

Optimality check: μ_V ≥ 0 everywhere means you are at the optimum. A negative entry in μ_V points to a neighbor with lower objective value. The simplex method is guaranteed to terminate because there are finitely many vertices and each step improves the objective (or at worst preserves it, with anti-cycling rules like Bland's rule).

The simplex algorithm terminates when:

All reduced costs are non-negative (μ_V ≥ 0) A fixed number of iterations is reached The gradient is zero

Chapter 5: Edge Transitions

When moving from one vertex to a neighbor, we travel along an edge of the polytope. We increase the entering variable x_q from zero until another basic variable hits zero (becomes non-basic). This edge transition determines how far we move and which variable leaves the basis.

The entering variable increases until:

x_q' = min_{i: d_i>0} (x_B,i / d_i)

where d = A_B⁻¹A_{q} and the minimum is taken over positive components of d. The index achieving this minimum is the leaving variable.

Think of it this way: You are sliding along an edge of the polytope. You keep going until you hit another face. The first face you hit determines the new vertex — and which old constraint becomes slack.

During an edge transition, you stop when:

A basic variable reaches zero The gradient reverses direction A fixed step size is exceeded

Chapter 6: Initialization

The simplex algorithm needs a starting vertex, but finding one can be as hard as solving the LP itself. The solution: solve an auxiliary linear program designed to find a feasible vertex.

The auxiliary LP introduces artificial variables z and minimizes their sum. If the solution has z = 0, we have found a feasible vertex for the original problem. If z ≠ 0, the original problem is infeasible.

Key insight: The auxiliary LP always has an obvious starting vertex (set x = 0 and z = |b|). So we can always start the simplex method on the auxiliary problem. Once we find a feasible vertex with z = 0, we use that vertex to start the simplex method on the original problem. This two-phase approach handles any LP.

The auxiliary LP in the simplex method is used to:

Find an initial feasible vertex for the original problem Solve the dual problem Compute the Hessian

Chapter 7: Dual Certificates

Linear programs have zero duality gap: the optimal primal value equals the optimal dual value. This means we can verify a candidate solution (x*, λ*) by checking three conditions:

Check	Condition
Primal feasibility	Ax* = b, x* ≥ 0
Dual feasibility	A^>λ* ≤ c
Equal objectives	c^>x* = b^>λ*

Why this matters: Dual certificates let you independently verify that a solution is optimal, without trusting the solver. This is invaluable for debugging, for high-stakes applications, and for certification. If all three conditions hold, the solution is provably optimal.

A dual certificate verifies optimality by checking that:

Both primal and dual are feasible, and their objective values match The gradient is zero The Hessian is positive definite

Chapter 8: Simplex Simulator

Watch the simplex algorithm walk along vertices of a 2D polytope. The blue region is the feasible set. The orange dot is the current vertex. The arrow shows the direction of the objective function c.

Simplex Algorithm (2D)

Click Step to pivot to the next vertex. The algorithm moves toward lower objective values.

Vertex 0

The simplex algorithm is guaranteed to find the global optimum of an LP because:

The feasible set is convex and the objective is linear, so any local optimum is global It evaluates every point in the feasible region It uses second-order information

Chapter 9: Summary

Concept	Key Fact
LP structure	Linear objective + linear constraints = convex polytope
Simplex algorithm	Walks vertices, each step improves or maintains objective
Vertices	Defined by partitions; m tight constraints in m-dim equality form
Initialization	Auxiliary LP finds a feasible vertex
Duality	Zero gap; dual certificates verify optimality

Looking ahead: Chapter 13 extends to quadratic programming, where the objective is quadratic but constraints remain linear. This covers least-squares problems with inequality constraints.

The simplex algorithm solves LPs by:

Moving from vertex to vertex along edges, always improving the objective Sampling random points in the feasible set Computing the gradient and following it