Linear programming is the case where both objective and constraints are linear. It is the oldest, best-developed area of optimisation, and the family of problems for which the strongest theoretical and algorithmic results exist. In finance, LP shows up in arbitrage detection, transportation/logistics-style problems, and as the linchpin of many decomposition methods.
Standard LP form
minimize cᵀ xsubject to A x = bx ≥ 0
Convert inequality constraints to equalities by adding slack variables: Ax ≤ b ⟹ Ax + s = b, s ≥ 0. Convert unrestricted variables x_free = x⁺ - x⁻ with x⁺, x⁻ ≥ 0. Standard form is what every LP solver expects internally.
Polyhedral feasible set
The feasible set {x : Ax = b, x ≥ 0} is a polyhedron (intersection of half-spaces). Vertices (corner points) are basic feasible solutions; the optimum is attained at a vertex (when bounded). The simplex method exploits this fact.
Simplex method
Dantzig (1947). Start at a vertex. Identify a non-basic variable whose entry would improve the objective. Pivot — bring it into the basis, displace one current basic variable. Continue until no improving pivot exists. Worst-case exponential but typically linear in problem size; spectacularly fast on most real problems.
Interior-point methods
Karmarkar (1984). Walk through the interior of the polyhedron rather than along edges, following the central path that solves a barrier-penalised LP. Polynomial-time complexity. Faster than simplex on very large problems; the standard for LPs with > 10⁵ variables.
LP duality
Primal: Dual:min cᵀx max bᵀys.t. Ax = b s.t. Aᵀy ≤ cx ≥ 0
Strong duality holds for any feasible LP. The dual multiplier on the primal's constraint i is the shadow price of resource i. Solving the dual is sometimes much cheaper than solving the primal — large primals may have small duals, or vice versa.
Farkas' lemma — arbitrage in two lines
Either Ax = b has a solution x ≥ 0 OR there exists y with Aᵀy ≤ 0 and bᵀy > 0 — but not both. In asset-pricing: either there exist non-negative state prices that price every asset OR there exists an arbitrage portfolio. Farkas' lemma IS the no-arbitrage theorem; the equivalence of state prices and absence of arbitrage is a 1-line linear-algebra fact.
Arbitrage detection as LP
Given n assets with payoffs in m states, P ∈ Rᵐˣⁿ, and prices p ∈ Rⁿ. Find portfolio x with current cost ≤ 0 and non-negative payoff in every state — and strict positivity somewhere. Formulate: find x s.t. Px ≥ 0, pᵀx ≤ 0, with at least one strict. An arbitrage is precisely a feasible solution; LP solvers can detect this and recover the arbitrage portfolio when one exists.
L¹ regression as LP
min ‖y - Xβ‖₁ = min Σ |yᵢ - xᵢᵀβ|. Convert to LP by introducing slack variables uᵢ ≥ |yᵢ - xᵢᵀβ|, equivalently uᵢ ≥ yᵢ - xᵢᵀβ and uᵢ ≥ -(yᵢ - xᵢᵀβ). Minimise Σ uᵢ subject to these and any β bounds. The L¹ regression (robust to outliers) is then a standard LP — solvable instantly even for n in the thousands.
Other LP applications in finance
- Cash-flow matching: dedicate a portfolio of bonds to match liabilities exactly at minimum cost.
- Linear transaction-cost models: portfolio rebalancing with per-share fees.
- Asset-liability matching for insurers and pension funds.
- Network flow problems: order routing, capital allocation across desks.
Exercise
Two bonds pay payoffs (10, 5) and (4, 8) across two states; their current prices are 8 and 5 respectively. (1) Set up the LP that finds an arbitrage if one exists. (2) Solve.