Linear Programming and the Simplex Method

Suppose you're allocating capital across a handful of trades, each with a fixed expected return, subject to hard limits: total capital, a maximum position per name, a sector exposure cap. Every piece of this — the objective (total expected return) and every constraint — is a straight-line (linear) relationship in the position sizes. This is a linear program, and it has a remarkable structural fact going for it: the optimal allocation is never some interior blend that uses every constraint a little; it always sits exactly at a corner where several constraints bind simultaneously. The simplex method is the classical algorithm that exploits this fact directly, hopping from corner to corner of the feasible region until it can prove no neighboring corner is better.

The analogy: a diamond-shaped room and a flashlight

Picture the set of all allowed allocations as a many-sided polyhedral room — every wall is a constraint, and any point inside or on the walls is feasible. Now shine a flashlight from one direction representing "more objective value" and ask: where does the room get brightest? Because every wall is flat (no curved walls, since everything is linear), the brightest point is always exactly at a corner or edge, never floating in the middle of a flat wall or deep in the room's interior. The simplex method starts at one corner of this room and repeatedly checks: is there an adjacent corner, connected by an edge, that's brighter? If yes, walk there; if no, you've proven you're at the best corner in the whole room.

The mechanics, one symbol at a time

A linear program in standard form is

$$\max_{\mathbf{x}} \; \mathbf{c}^\top \mathbf{x} \quad \text{subject to} \quad A\mathbf{x} \le \mathbf{b}, \quad \mathbf{x} \ge 0,$$

where $\mathbf{x}$ is the vector of decision variables (position sizes), $\mathbf{c}$ gives each variable's contribution to the objective, and $A\mathbf{x}\le\mathbf{b}$ encodes every linear constraint at once. In words: choose position sizes to maximize a weighted sum of returns, without violating any capital, exposure, or position-limit constraint, and without taking negative positions.

The simplex method starts at a vertex (corner) of the feasible region and, at each step, checks whether moving along any edge to a neighboring vertex increases the objective. If some neighbor is strictly better, it moves there; if no neighboring vertex improves the objective, the current vertex is provably optimal — because of the flat-walled, corner-optimal structure, checking local neighbors is enough to prove global optimality, something that's emphatically not true for curved (nonlinear) optimization problems.

Worked example 1: a two-trade allocation by hand

Maximize $30x_1 + 20x_2$ (expected profit, in $thousands, from two trades) subject to $x_1 + x_2 \le 10$ (capital limit) and $x_1 \le 6$ (a per-name cap), with $x_1,x_2\ge0$. The feasible region's corners are $(0,0)$, $(6,0)$, $(6,4)$, and $(0,10)$. Evaluating the objective at each: $(0,0)\to0$; $(6,0)\to180$; $(6,4)\to 30(6)+20(4)=180+80=260$; $(0,10)\to200$. The best corner is $(6,4)$, value $260,000 — using the full per-name cap on trade 1 and whatever capital remains on trade 2. Simplex would reach this by starting at, say, $(0,0)$, moving to a better adjacent corner, and repeating until no neighbor beats $260$.

Worked example 2: reading off a binding constraint

At the optimal corner $(6,4)$ above, note both constraints are exactly binding: $x_1 = 6$ (the cap) and $x_1+x_2=10$ (full capital used). This is the general pattern — with 2 variables, an optimal corner is defined by exactly 2 binding constraints. If instead the capital limit were raised to $x_1+x_2\le 20$, the new corners would shift, and it's worth checking: the corner $(6,14)$ would now give $30(6)+20(14) = 180+280=460$, an improvement — showing directly how loosening one constraint moves the whole optimal corner, not just nudges the objective value.

Treat this as a stand-in for the boundary of a feasible region — imagine it as one wall of a many-sided flat-walled room; a genuine LP's feasible region is bounded by several such flat pieces, and the optimum sits where several of them meet at a corner.

What this means in practice

Linear programming is the workhorse behind capital allocation with hard exposure limits, index-tracking with turnover and transaction-cost caps expressed linearly, and any risk-limit problem where the objective and every constraint are genuinely linear. It's also the simplest member of a family — quadratic programming, second-order cone programming, semidefinite programming — that handles progressively more general (curved) objectives and constraints, each solved with algorithms that borrow directly from LP intuition, especially the interior-point approach that largely displaced pure simplex for large problems.