44.05.02 · optimization-control / 05-conic-semidefinite

Linear-Programming Duality and the Simplex Method

shipped3 tiersLean: none

Anchor (Master): Bertsimas & Tsitsiklis 1997 Introduction to Linear Optimization (Athena Scientific) Ch. 3-Ch. 5; Schrijver 1986 Theory of Linear and Integer Programming (Wiley) §7-§11; Chvátal 1983 Linear Programming (Freeman); Boyd & Vandenberghe 2004 Convex Optimization (Cambridge) §4.3, §5.2

Intuition Beginner

A linear program is the simplest kind of planning problem with a clean shape. You have some quantities to decide — how many of each product to make, how much of each ingredient to buy. Each decision is a number that cannot go below zero. There are limits: only so much labour, only so much material. Every limit is a straight-line budget, and your goal — total profit, total cost — is also a straight measure. You want the best plan that respects every limit.

The set of all plans that respect the limits is a flat-sided region, like a cut gemstone. Because both the limits and the goal are straight, the best plan never hides in the middle of a face. It always sits at a corner of the gemstone. This is the single most useful fact about linear programs: to find the best plan, you only ever need to look at corners, and there are finitely many of them.

The second idea is that every planning problem has a hidden twin. If your problem is "make the most profit without breaking any limit," the twin asks "what is the cheapest set of prices to attach to each limited resource so that no product looks underpriced?" These two problems, the primal and the dual, always meet in the middle: the best profit you can earn exactly equals the cheapest resource bill the twin can post. Not "less than," not "close to" — exactly equal.

That exact match is no accident. It means the price the twin attaches to a resource is the true marginal worth of one more unit of it. The plan and the prices certify each other: the plan proves the prices are not too high, and the prices prove the plan cannot be beaten.

Visual Beginner

Picture a feasible region as a polygon in the plane. The goal is a direction — "more profit this way." Push a straight ruler across the polygon in that direction; the last point it touches before leaving is the best plan, and that point is always a corner. The simplex method is the strategy of starting at one corner and walking along edges, always to a neighbour that improves the goal, until no neighbouring corner is better.

        goal direction --->
        c2
         \         best corner (optimum)
          \        *
           +-------+
          /         \
   start /  feasible \
   corner   polygon   \
   *----+-------------+
    \   ^ walk along edges, corner to corner,
     \  | each step improving the goal
      \ |
       \+

   At the optimum, no neighbouring corner is better:
   the ruler (goal) cannot be pushed any further.

Worked example Beginner

A workshop makes chairs and tables. Each chair earns $3$ and each table earns $5$ . A chair needs $1$ hour of carpentry; a table needs $2$ hours; only $8$ carpentry hours are available. A chair needs $2$ hours of finishing; a table needs $1$ hour; only $7$ finishing hours are available. How many of each should we make to earn the most? Let $x$ be chairs and $y$ tables, both at least $0$ .

The limits. Carpentry: $x + 2 y \leq 8$ . Finishing: $2 x + y \leq 7$ . Goal: make $3 x + 5 y$ as large as possible.

Find the corners. The corners of the feasible region are where limits meet. Setting $x = 0$ : carpentry gives $y = 4$ , so $(0, 4)$ earns $3 \cdot 0 + 5 \cdot 4 = 20$ . Setting $y = 0$ : finishing gives $x = 3.5$ , so $(3.5, 0)$ earns $10.5$ . Where both limits bind, solve $x + 2 y = 8$ and $2 x + y = 7$ : subtract to get $x = 2, y = 3$ , so $(2, 3)$ earns $3 \cdot 2 + 5 \cdot 3 = 21$ . The origin $(0, 0)$ earns $0$ .

Compare the corners. The earnings are $0$ , $10.5$ , $20$ , and $21$ . The largest is $21$ , at the corner $(2, 3)$ : make $2$ chairs and $3$ tables.

What this tells us. Checking every corner found the best plan, $21$ . The twin problem attaches prices to the two resources; those prices turn out to be $\frac{7}{3}$ per carpentry hour and $\frac{1}{3}$ per finishing hour, and the resource bill is $\frac{7}{3} \cdot 8 + \frac{1}{3} \cdot 7 = \frac{56 + 7}{3} = 21$ — the same number, as the twin always promises.

Check your understanding Beginner

Exercise (easy, multiple choice).

For a linear program with a finite best value, where is an optimal plan always guaranteed to be found?

A. In the exact centre of the feasible region. B. At a corner (vertex) of the feasible region. C. Strictly outside the feasible region. D. Only at points where the goal is zero.

Hint

Think about pushing a straight ruler across a gemstone-shaped region.

Answer

B. At a corner of the feasible region.

Feedback-correct: correct — because the goal is a straight measure and the region is flat-sided, the best value is attained at a corner (and possibly along a whole edge or face, which still includes corners). Feedback-wrong: the centre and the interior are never forced to hold the optimum; a straight goal is optimised at the boundary, specifically at a corner.

Formal definition Intermediate+

Work in $R^{n}$ . The standard-form linear program is

x min ⟨ c, x ⟩ subject to A x = b, x \geq 0,

with $A \in R^{m \times n}$ (assume $rank A = m \leq n$ ), $b \in R^{m}$ , $c \in R^{n}$ , and $x \geq 0$ meaning $x_{j} \geq 0$ for every coordinate. The canonical (inequality) form is $min ⟨ c, x ⟩$ subject to $A x \geq b$ ; the two are interconvertible by introducing non-negative slack variables ( $A x \geq b ⟺ A x - s = b, s \geq 0$ ) and splitting a free variable as $x = x^{+} - x^{-}$ with $x^{\pm} \geq 0$ .

Definition (basic feasible solution). Let $B \subseteq {1, \dots, n}$ with $∣ B ∣ = m$ index $m$ linearly independent columns of $A$ ; write $A_{B}$ for the resulting invertible $m \times m$ submatrix and $N = {1, \dots, n} ∖ B$ . The associated basic solution sets $x_{N} = 0$ and $x_{B} = A_{B}^{- 1} b$ . It is a basic feasible solution (BFS) when additionally $x_{B} \geq 0$ . The columns indexed by $B$ form the basis; $x_{B}$ are the basic variables and $x_{N}$ the nonbasic variables. A BFS is degenerate when some basic variable equals $0$ .

The geometric content (cross-ref 44.01.03) is that the feasible polyhedron $P = {x : A x = b, x \geq 0}$ has the basic feasible solutions as exactly its vertices (extreme points): a feasible $x$ is a vertex of $P$ if and only if the columns ${a_{j} : x_{j} > 0}$ are linearly independent, which is the BFS condition.

Definition (the dual LP). The dual of the standard-form primal is

y max ⟨ b, y ⟩ subject to A^{T} y \leq c,

with $y \in R^{m}$ free. Equivalently, writing the dual slack $z = c - A^{T} y \geq 0$ , the dual variable $y_{i}$ is the price (Lagrange multiplier) on the $i$ -th primal equality, and $z_{j}$ is the reduced cost of primal variable $j$ .

Definition (reduced costs and optimality test). Given a basis $B$ , set $y^{T} = c_{B}^{T} A_{B}^{- 1}$ (the basis prices) and define the reduced-cost vector $\overset{c}{ˉ} = c - A^{T} y$ , so $\overset{c}{ˉ}_{B} = 0$ and $\overset{c}{ˉ}_{N} = c_{N} - (A_{B}^{- 1} A_{N})^{T} c_{B}$ . The BFS for $B$ is optimal for a minimisation when $\overset{c}{ˉ} \geq 0$ (no nonbasic variable can be increased to lower the objective).

Counterexamples to common slips

Free vs. sign-constrained dual variables track the primal constraint type. A primal equality row yields a free dual variable; a primal $\leq$ inequality with non-negative primal variable yields a non-negative dual variable. Forcing every dual variable to be non-negative for an equality-constrained primal is the most common sign error.
A basic solution need not be feasible. Choosing $m$ independent columns always gives a basic solution $x_{B} = A_{B}^{- 1} b$ , but it is a basic feasible solution only when $x_{B} \geq 0$ . The simplex method moves only among feasible bases; the dual simplex moves among dual-feasible (possibly primal-infeasible) bases.
Degeneracy is a vertex with too many active constraints, not a non-vertex. A degenerate BFS (some basic variable zero) is still a genuine vertex; it is the source of cycling because several distinct bases describe the same vertex, and a pivot can change the basis without moving the point.

Key theorem with proof Intermediate+

We prove LP strong duality and complementary slackness, deriving them from Farkas' lemma 44.02.04; weak duality is the elementary half.

Theorem (LP duality and complementary slackness). Consider the primal $min {⟨ c, x ⟩ : A x = b, x \geq 0}$ and dual $max {⟨ b, y ⟩ : A^{T} y \leq c}$ .

(i) (Weak duality.) If $x$ is primal feasible and $y$ is dual feasible, then $⟨ b, y ⟩ \leq ⟨ c, x ⟩$ .

(ii) (Strong duality.) If the primal has a finite optimal value $p^{⋆}$ , then the dual has an optimal value $d^{⋆}$ and $d^{⋆} = p^{⋆}$ , each attained.

(iii) (Complementary slackness.) Feasible $x, y$ are simultaneously optimal if and only if $x_{j} (c - A^{T} y)_{j} = 0$ for every $j$ .

Proof of (i). Let $A x = b, x \geq 0$ and $A^{T} y \leq c$ . Then

⟨ b, y ⟩ = ⟨ A x, y ⟩ = ⟨ x, A^{T} y ⟩ \leq ⟨ x, c ⟩ = ⟨ c, x ⟩,

the inequality using $x \geq 0$ coordinatewise against $A^{T} y \leq c$ . So every dual-feasible value is a lower bound for every primal-feasible value.

Proof of (ii). Let $p^{⋆}$ be the finite primal optimum. For any scalar $γ < p^{⋆}$ the system

A x = b, x \geq 0, ⟨ c, x ⟩ \leq γ

is infeasible (a solution would beat the optimum). Write this as a single standard-form feasibility by adding a slack $s \geq 0$ to the last row: $⟨ c, x ⟩ + s = γ$ . Infeasibility of ${[A; c^{T}] (x) = (b; γ), x \geq 0, s \geq 0}$ is, by the affine Farkas alternative 44.02.04, the solvability of a dual certificate: there exist $y \in R^{m}$ and $λ \in R$ with

A^{T} y + λ c \leq 0, λ \leq 0, ⟨ b, y ⟩ + λγ > 0.

Suppose $λ = 0$ . Then $A^{T} y \leq 0$ and $⟨ b, y ⟩ > 0$ , which is the Farkas certificate that $A x = b, x \geq 0$ is itself infeasible — contradicting primal feasibility (the optimum $p^{⋆}$ is finite, so a feasible point exists). Hence $λ < 0$ ; rescale by $- 1/ λ > 0$ and rename, setting $\overset{y}{^} = - y / λ$ . The conditions become $A^{T} \overset{y}{^} \leq c$ and $⟨ b, \overset{y}{^} ⟩ > γ$ . So for every $γ < p^{⋆}$ there is a dual-feasible $\overset{y}{^}$ with dual value exceeding $γ$ . Letting $γ ↑ p^{⋆}$ yields dual-feasible points with value approaching $p^{⋆}$ from below, so $d^{⋆} \geq p^{⋆}$ ; weak duality gives $d^{⋆} \leq p^{⋆}$ . Thus $d^{⋆} = p^{⋆}$ .

Attainment: the dual feasible region ${y : A^{T} y \leq c}$ is a polyhedron and the objective $⟨ b, \cdot ⟩$ is bounded above on it by $p^{⋆}$ ; by the vertex-attainment principle for polyhedra 44.01.03 the supremum is attained at a vertex (after factoring lineality), and symmetrically the primal optimum is attained at a vertex of $P$ .

Proof of (iii). With $x, y$ feasible, the weak-duality computation gives

⟨ c, x ⟩ - ⟨ b, y ⟩ = ⟨ x, c - A^{T} y ⟩ = j \sum x_{j} (c - A^{T} y)_{j} \geq 0,

a sum of products of non-negative terms ( $x_{j} \geq 0$ and $(c - A^{T} y)_{j} \geq 0$ ). The duality gap $⟨ c, x ⟩ - ⟨ b, y ⟩$ is zero — equivalently, by (ii), $x$ and $y$ are both optimal — exactly when every product vanishes, $x_{j} (c - A^{T} y)_{j} = 0$ . This is complementary slackness: a variable is positive only where its reduced cost is zero, and a reduced cost is positive only where the variable is zero. $□$

Bridge. Strong duality builds toward the optimality test of the simplex method and the polynomial-time interior-point analysis, and the complementary-slackness pairing appears again in the Karush-Kuhn-Tucker conditions of nonlinear programming, where reduced costs become Lagrange multipliers. This is exactly the Farkas dichotomy with an objective attached: the alternative "either the value- $< γ$ system is feasible or a separating multiplier exists" becomes "either you can improve or you hold a dual certificate of optimality," so the foundational reason the primal and dual values coincide is the closedness of the finitely generated cone underlying Farkas. The duality pairing is dual to the geometry of 44.01.03: a primal vertex and a dual vertex certify each other, and the central insight is that the reduced-cost vector $\overset{c}{ˉ} = c - A^{T} y$ is simultaneously the simplex optimality test and the dual feasibility residual. Putting these together, LP duality generalises to conic duality over a general closed convex cone (the orthant replaced by $K$ , the price vector constrained to the dual cone $K^{*}$ ), and the bridge is complementary slackness, the exact-equality condition that survives, in a relaxed Slater-regularised form, into the conic and nonlinear theory.

Exercises Intermediate+

Exercise 4 (medium, symbolic).

Derive the simplex ratio test. Given a feasible basis $B$ with $x_{B} = A_{B}^{- 1} b \geq 0$ and an entering nonbasic index $q$ with reduced cost $\overset{c}{ˉ}_{q} < 0$ , let $d = A_{B}^{- 1} a_{q}$ . Show the largest step $θ \geq 0$ keeping feasibility is $θ = min_{i : d_{i} > 0} (x_{B})_{i} / d_{i}$ , and identify the leaving variable.

Hint

Increasing $x_{q}$ to $θ$ changes the basics by $x_{B} \mapsto x_{B} - θ d$ ; keep every basic variable $\geq 0$ .

Answer

Set $x_{q} = θ \geq 0$ and keep other nonbasics at $0$ . Feasibility $A x = b$ forces $x_{B} = A_{B}^{- 1} (b - θ a_{q}) = (A_{B}^{- 1} b) - θ (A_{B}^{- 1} a_{q}) = x_{B}^{0} - θ d$ . Non-negativity of each basic variable requires $(x_{B}^{0})_{i} - θ d_{i} \geq 0$ . For $d_{i} \leq 0$ this holds for all $θ \geq 0$ ; for $d_{i} > 0$ it requires $θ \leq (x_{B}^{0})_{i} / d_{i}$ . The binding limit is $θ^{⋆} = min_{i : d_{i} > 0} (x_{B}^{0})_{i} / d_{i}$ , attained at some row $r$ whose basic variable hits $0$ and leaves the basis (entering: $q$ , leaving: the basic variable of row $r$ ). If $d \leq 0$ entirely, $θ$ is unbounded and the objective $\to - \infty$ : the LP is unbounded.

Exercise 6 (hard, symbolic).

State Bland's rule and prove it prevents cycling, so the simplex method terminates in finitely many pivots even under degeneracy.

Hint

Bland's rule: among eligible entering/leaving candidates always pick the one with the smallest index. Argue that a cycle would force a contradictory reduced-cost sign on the largest index that leaves and re-enters.

Answer

Bland's rule: among nonbasic variables with negative reduced cost choose the entering variable of smallest index; in the ratio test, among rows attaining the minimum ratio choose the leaving variable of smallest index. Termination: the objective is non-increasing each pivot, so a non-terminating run must cycle through a finite set of bases all describing one degenerate vertex with constant objective. Let $t$ be the largest index that both enters and leaves during a cycle. Consider the pivot where $t$ leaves, with entering variable $q < t$ (largest-index-leaves means any larger index is fixed across the cycle), and a later pivot where $t$ enters. Build the vector $w = x_{B}^{0} - θ d$ from the entering step. Pairing the reduced-cost vectors of the two configurations and using $\overset{c}{ˉ}_{q} < 0$ (so $q$ was eligible), $\overset{c}{ˉ}_{t}^{'} < 0$ (so $t$ later entered), while complementary positivity of the pivot column forces the matching coordinate of $t$ to carry the opposite sign, yields $0 >$ a quantity shown $\geq 0$ — a contradiction. Hence no cycle exists; with finitely many bases the method terminates.

Exercise 7 (hard, symbolic).

Describe the two-phase initialisation and prove it correctly decides primal feasibility. Then state how the big-M method achieves the same in one pass.

Hint

Phase I minimises the sum of artificial variables; the original LP is feasible iff that minimum is zero.

Answer

Phase I. Assume $b \geq 0$ (flip rows otherwise). Add artificials $u \geq 0$ giving $A x + u = b$ , and solve the auxiliary LP $min {1^{T} u : A x + u = b, x, u \geq 0}$ , which has the obvious starting BFS $x = 0, u = b \geq 0$ . Its optimum is $\geq 0$ . If the optimum is $0$ , then $u = 0$ at optimum, so the residual $x$ satisfies $A x = b, x \geq 0$ : the original is feasible and we have a starting BFS (drive any remaining zero-valued artificials out of the basis by degenerate pivots). If the optimum is $> 0$ , no $x \geq 0$ solves $A x = b$ (else $u = 0$ would be achievable), so the original is infeasible. Phase II runs the simplex method from that BFS on the true objective. Big-M: append $+ M 1^{T} u$ to the original objective with $M$ a large constant; for $M$ large enough any optimal solution drives $u = 0$ if the original is feasible, merging the two phases into one objective, at the cost of numerical sensitivity to $M$ .

Exercise 8 (hard, symbolic).

Carry out sensitivity analysis for the right-hand side: given an optimal basis $B$ , show the optimal value is a piecewise-linear convex function of $b$ , and the dual optimal $y$ is its (sub)gradient where the basis stays optimal. Give the range of a single $b_{k}$ over which $B$ remains optimal.

Hint

The basis stays optimal while $x_{B} = A_{B}^{- 1} b \geq 0$ (primal feasibility) and $\overset{c}{ˉ} \geq 0$ (unchanged by $b$ ).

Answer

For a fixed optimal basis $B$ , the reduced costs $\overset{c}{ˉ} = c - A^{T} (A_{B}^{- T} c_{B})$ do not depend on $b$ , so $\overset{c}{ˉ} \geq 0$ persists; the only constraint is primal feasibility $x_{B} = A_{B}^{- 1} b \geq 0$ . On the polyhedral cone of $b$ with $A_{B}^{- 1} b \geq 0$ the value is $v (b) = c_{B}^{T} A_{B}^{- 1} b = ⟨ y, b ⟩$ , linear in $b$ with gradient $y$ — the dual optimum is the marginal value of resources. Perturbing one component $b \mapsto b + δ e_{k}$ keeps feasibility while $A_{B}^{- 1} (b + δ e_{k}) \geq 0$ , i.e. $(x_{B})_{i} + δ (A_{B}^{- 1})_{ik} \geq 0$ for all $i$ , giving $δ \in [max_{(A_{B}^{- 1})_{ik} > 0} (- (x_{B})_{i} / (A_{B}^{- 1})_{ik}), min_{(A_{B}^{- 1})_{ik} < 0} (- (x_{B})_{i} / (A_{B}^{- 1})_{ik})]$ . Outside this interval a basic variable goes negative and a (dual-simplex) pivot changes the basis, after which $v$ continues with a different slope $y^{'}$ — the breakpoints are where the gradient jumps, making $v$ piecewise linear and convex.

Advanced results Master

The simplex method as edge-following and its finiteness

A pivot replaces one basis column by another, moving from a vertex of $P = {x : A x = b, x \geq 0}$ to an adjacent vertex along an edge while never increasing $⟨ c, x ⟩$ ^{[Bertsimas-Tsitsiklis Ch. 3]}. The entering variable is any nonbasic index $q$ with reduced cost $\overset{c}{ˉ}_{q} < 0$ ; the ratio test $θ^{⋆} = min_{i : d_{i} > 0} (x_{B})_{i} / d_{i}$ with $d = A_{B}^{- 1} a_{q}$ selects the leaving variable. Each nondegenerate pivot strictly decreases the objective, so with finitely many bases the method terminates — unless degeneracy permits a sequence of zero-step pivots returning to a previous basis. Bland's rule (smallest-index entering and leaving) and the lexicographic perturbation rule both forbid such cycles; Bland's argument ^{[Bland 1977]} tracks the largest index participating in a hypothetical cycle and derives a reduced-cost sign contradiction, while the lexicographic rule perturbs $b \to b + (ε, ε^{2}, \dots)$ to make every BFS nondegenerate. Either way the method is finite.

Klee-Minty: exponential worst case versus practical efficiency

Dantzig's most-negative-reduced-cost pivot rule, and indeed every deterministic pivot rule examined, admits inputs on which the simplex method visits exponentially many vertices. The Klee-Minty cube ^{[Klee-Minty 1972]} is a perturbed $n$ -dimensional cube with $2 n$ facets whose vertices the largest-coefficient rule traverses all $2^{n}$ of, in order. Yet in practice the simplex method runs in roughly $O (m)$ to $O (m lo g n)$ pivots; Spielman and Teng's smoothed-analysis theorem (2004) explains this by proving the expected pivot count is polynomial under small random perturbations of the data, reconciling the exponential worst case with decades of empirical efficiency. The worst-case picture motivates the polynomial-time interior-point alternative (44.05.04, catalog stub), which follows the central path through the relative interior of $P$ rather than walking its boundary vertices, achieving $O (n L)$ iterations for $L$ the input bit-length.

The dual simplex method and warm starts

The dual simplex maintains dual feasibility ( $\overset{c}{ˉ} \geq 0$ ) while restoring primal feasibility, the mirror image of the primal simplex ^{[Bertsimas-Tsitsiklis Ch. 4]}. It selects a leaving variable with $(x_{B})_{i} < 0$ , then a dual ratio test on the reduced costs picks the entering variable preserving $\overset{c}{ˉ} \geq 0$ . Its decisive use is re-optimisation: after a sensitivity perturbation of $b$ , or after adding a cutting-plane constraint that the current optimum violates (the engine of branch-and-cut integer programming), the previous basis is dual-feasible but primal-infeasible, so a few dual-simplex pivots recover optimality without restarting — the algorithmic payoff of complementary slackness, since primal and dual feasibility together with $x_{j} \overset{c}{ˉ}_{j} = 0$ are exactly the optimality certificate the two simplex variants alternately repair.

Strict complementarity, the central path, and degeneracy

Goldman and Tucker's theorem guarantees a primal-dual optimal pair that is strictly complementary: for every $j$ exactly one of $x_{j} > 0$ or $\overset{c}{ˉ}_{j} > 0$ holds ^{[Schrijver §7]}. Interior-point methods converge to such a strictly complementary pair (the analytic centre of the optimal face), whereas the simplex method returns a vertex that may be degenerate and basis-ambiguous. The partition ${j : x_{j} > 0}$ versus ${j : \overset{c}{ˉ}_{j} > 0}$ given by strict complementarity is the optimal partition, an invariant of the LP independent of which optimal vertex an algorithm reports, and it is what makes sensitivity analysis well-posed even when the optimal vertex is degenerate and multiple bases describe it.

Synthesis. The simplex method, LP duality, and the vertex theory of 44.01.03 are exactly three readings of one finite-dimensional fact: a polyhedron is a finite list of vertices and recession rays, a linear objective is minimised at a vertex, and the certificate that no better vertex exists is a dual-feasible price vector. The central insight organising the unit is that the reduced-cost vector $\overset{c}{ˉ} = c - A^{T} y$ is the join of the two theories — it is the simplex optimality test, the dual feasibility residual, and the complementary-slackness partner of $x$ all at once. The foundational reason strong duality holds with no constraint qualification is that the orthant is a finitely generated cone, so Farkas 44.02.04 applies unconditionally; putting these together, the orthant case generalises to conic duality where the same pairing $⟨ x, c - A^{T} y ⟩$ governs optimality but closedness must be bought with a Slater hypothesis. The Klee-Minty worst case is dual to the practical efficiency that smoothed analysis explains, and the bridge is the central path: interior-point methods trade vertex-walking for a smooth trajectory whose limit is the strictly complementary pair, which appears again in the polynomial-time complexity theory that places LP in $P$ while leaving the combinatorial diameter of the vertex graph (the Hirsch-conjecture circle) open.

Full proof set Master

Proposition 1 (BFS ⇔ vertex). For $P = {x : A x = b, x \geq 0}$ with $rank A = m$ , a feasible point $x$ is a vertex (extreme point) of $P$ if and only if the columns ${a_{j} : x_{j} > 0}$ are linearly independent — equivalently, $x$ is a basic feasible solution.

Proof. Let $K = {j : x_{j} > 0}$ . ( $\Leftarrow$ ) Suppose ${a_{j} : j \in K}$ are independent and $x = \frac{1}{2} (u + w)$ with $u, w \in P$ . For $j \in / K$ , $x_{j} = 0$ and $u_{j}, w_{j} \geq 0$ force $u_{j} = w_{j} = 0$ . Then $A_{K} u_{K} = b = A_{K} w_{K}$ with $A_{K}$ of full column rank, so $u_{K} = w_{K} = A_{K}^{+} b$ , giving $u = w = x$ : $x$ is extreme. ( $\Rightarrow$ ) Suppose ${a_{j} : j \in K}$ are dependent: there is $λ \neq = 0$ supported on $K$ with $A λ = 0$ . For small $ε > 0$ , $x \pm ε λ$ are feasible (they satisfy $A (\cdot) = b$ and stay $\geq 0$ since the perturbed coordinates are those with $x_{j} > 0$ ), and $x = \frac{1}{2} ((x + ε λ) + (x - ε λ))$ is a midpoint of two distinct feasible points, so $x$ is not extreme. Independence of $\leq m$ columns extends to a basis $B \supseteq K$ , exhibiting $x$ as the BFS for $B$ (with $x_{j} = 0$ for the padding indices). $□$

Proposition 2 (existence of an optimal vertex). If the standard-form LP has a feasible point and the objective is bounded below on $P$ , then the optimum is attained at a vertex of $P$ .

Proof. Boundedness below means $⟨ c, d ⟩ \geq 0$ for every recession direction $d \in 0^{+} P = {d : A d = 0, d \geq 0}$ (otherwise stepping along $d$ drives the objective to $- \infty$ ). Take any optimal $x^{⋆}$ (one exists since the level set ${x \in P : ⟨ c, x ⟩ \leq ⟨ c, x_{0}^{⋆} ⟩}$ is a nonempty polyhedron with recession cone meeting $0^{+} P$ only where $⟨ c, d ⟩ \leq 0$ , hence at ${0}$ off the objective-flat directions, giving a compact slice by 44.01.03). If the support of $x^{⋆}$ is dependent, the Proposition 1 perturbation $x^{⋆} \pm ε λ$ keeps the objective unchanged on the direction with $⟨ c, λ ⟩ = 0$ , or strictly improves it for one sign otherwise — contradicting optimality unless $⟨ c, λ ⟩ = 0$ , in which case push $ε$ until a coordinate hits $0$ , reducing the support without changing the value. Iterating reaches an optimal point with independent support, a vertex. $□$

Proposition 3 (strong duality, basis form). If the primal simplex method terminates at a BFS with basis $B$ and reduced costs $\overset{c}{ˉ} \geq 0$ , then $y = A_{B}^{- T} c_{B}$ is dual optimal and $⟨ b, y ⟩ = ⟨ c, x ⟩$ .

Proof. Dual feasibility: $A^{T} y = A^{T} A_{B}^{- T} c_{B}$ , and $\overset{c}{ˉ} = c - A^{T} y \geq 0$ is precisely $A^{T} y \leq c$ . Value equality: $⟨ b, y ⟩ = ⟨ A_{B} x_{B}, y ⟩ = ⟨ x_{B}, A_{B}^{T} y ⟩ = ⟨ x_{B}, c_{B} ⟩ = ⟨ c, x ⟩$ , using $A_{B}^{T} y = c_{B}$ (since $\overset{c}{ˉ}_{B} = 0$ ) and $x_{N} = 0$ . By weak duality this common value is both the primal minimum and the dual maximum. $□$

Proposition 4 (complementary slackness characterises optimality). Feasible $x, y$ are both optimal if and only if $x_{j} (c - A^{T} y)_{j} = 0$ for all $j$ .

Proof. The duality gap is $⟨ c, x ⟩ - ⟨ b, y ⟩ = ⟨ x, c - A^{T} y ⟩ = \sum_{j} x_{j} (c - A^{T} y)_{j}$ , a sum of non-negative terms. By strong duality the gap is zero iff both are optimal, and a sum of non-negative reals is zero iff each term is zero, giving $x_{j} (c - A^{T} y)_{j} = 0$ for every $j$ . $□$

Proposition 5 (finite termination under Bland's rule). The primal simplex method with Bland's smallest-index rule performs finitely many pivots.

Proof. The objective is non-increasing, so a non-terminating run cycles among finitely many bases sharing one objective value and one degenerate vertex. Let $t$ be the largest index moving (entering at some pivot, leaving at another) during the cycle; in the pivot where $t$ leaves, the entering index is some $q$ ; in a pivot where $t$ enters, $\overset{c}{ˉ}_{t} < 0$ . Construct from the entering column the direction $d = A_{B}^{- 1} a_{q}$ and pair $\overset{c}{ˉ}$ from the $t$ -leaving configuration against the edge direction of the $t$ -entering configuration. Bland's smallest-index choices force every index $< t$ to behave monotonically across the cycle, isolating the coordinate $t$ , and the two configurations assign $t$ reduced costs of strictly opposite sign while the pivot-column entry forces a sign agreement — the inner product of a non-negative-by-eligibility vector with a non-positive-by-construction vector is shown both $> 0$ and $\leq 0$ . The contradiction rules out a cycle; finitely many bases then bound the pivot count. $□$

Connections Master

LP strong duality is the headline corollary of Farkas' lemma 44.02.04: the infeasibility of the value- $< γ$ system is, through the affine Farkas alternative, the existence of the dual certificate $(y, λ)$ , and the unconditional applicability of Farkas — no constraint qualification needed — is exactly the closedness of the finitely generated orthant cone proved there. Complementary slackness is the equality case of the same one-line pairing that gives weak duality.
The geometry rests on the recession-cone and Minkowski-Weyl theory of 44.01.03: basic feasible solutions are the vertices of the feasible polyhedron, an LP with a finite optimum attains it at a vertex because the recession cone forbids improving rays, and the simplex method is the algorithmic traversal of the vertex-edge graph that the polytope-plus-cone decomposition organises. Sensitivity analysis is the statement that the optimal value is the polyhedral support function of the right-hand side.
Linear programming is the orthant-cone special case of conic programming over a general closed convex cone (44.05.01, catalog stub for this chapter): replacing $x \geq 0$ by $x \in K$ and $A^{T} y \leq c$ by $c - A^{T} y \in K^{*}$ recovers semidefinite and second-order-cone programs, where strong duality and complementary slackness survive in a Slater-regularised form because richer cones lack the automatic closedness the orthant enjoys.
The interior-point alternative (44.05.04, catalog stub) is the polynomial-time response to the Klee-Minty exponential worst case: rather than walking vertices it follows the central path through the relative interior toward the strictly complementary optimal pair, and the complementary-slackness conditions that the simplex basis satisfies exactly are precisely the conditions the central path satisfies in the limit, tying the combinatorial and the continuous methods to one optimality system.

Historical & philosophical context Master

George Dantzig devised the simplex method in 1947 while working on planning problems for the U.S. Air Force, publishing the systematic account in Linear Programming and Extensions ^{[Dantzig 1963]} (Princeton, 1963); the duality theorem of linear programming was identified in the same period, with John von Neumann recognising in 1947 the connection between LP duality and the minimax theorem for two-person zero-sum games he had proved in 1928. Tjalling Koopmans's contemporaneous work on activity analysis in economics — for which he and Leonid Kantorovich shared the 1975 Nobel Memorial Prize in Economics — established the economic reading of dual variables as shadow prices. The exponential worst case for Dantzig's pivot rule was constructed by Victor Klee and George Minty in How good is the simplex algorithm? ^{[Klee-Minty 1972]} (1972), sharpening the question of whether linear programming admits a polynomial algorithm.

That question was resolved affirmatively by Leonid Khachiyan's 1979 ellipsoid method and, with practical force, by Narendra Karmarkar's 1984 interior-point algorithm, which reopened the projective-scaling tradition and made interior-point methods the competitive alternative to the simplex method for large instances. Robert Bland's 1977 anti-cycling rule ^{[Bland 1977]} gave the simplest finite pivot rule, settling the degeneracy problem that had complicated finiteness arguments since Dantzig's original lexicographic resolution. The combinatorial diameter of polytope graphs, governing the best possible number of simplex pivots, remains open: Warren Hirsch's 1957 conjecture that the diameter is at most $m - n$ was disproved by Francisco Santos in 2011, leaving the polynomial-diameter question — and with it the existence of a strongly polynomial LP algorithm — unresolved.

Bibliography Master

@book{bertsimas1997introduction,
  author    = {Bertsimas, Dimitris and Tsitsiklis, John N.},
  title     = {Introduction to Linear Optimization},
  publisher = {Athena Scientific},
  address   = {Belmont, MA},
  year      = {1997}
}

@book{dantzig1963linear,
  author    = {Dantzig, George B.},
  title     = {Linear Programming and Extensions},
  publisher = {Princeton University Press},
  year      = {1963}
}

@incollection{kleeminty1972howgood,
  author    = {Klee, Victor and Minty, George J.},
  title     = {How good is the simplex algorithm?},
  booktitle = {Inequalities III},
  editor    = {Shisha, Oved},
  publisher = {Academic Press},
  pages     = {159--175},
  year      = {1972}
}

@article{bland1977new,
  author  = {Bland, Robert G.},
  title   = {New finite pivoting rules for the simplex method},
  journal = {Mathematics of Operations Research},
  volume  = {2},
  number  = {2},
  pages   = {103--107},
  year    = {1977}
}

@book{schrijver1986theory,
  author    = {Schrijver, Alexander},
  title     = {Theory of Linear and Integer Programming},
  series    = {Wiley-Interscience Series in Discrete Mathematics},
  publisher = {John Wiley \& Sons},
  year      = {1986}
}

@book{chvatal1983linear,
  author    = {Chv\'atal, Va\v{s}ek},
  title     = {Linear Programming},
  publisher = {W. H. Freeman},
  year      = {1983}
}

@book{boyd2004convex,
  author    = {Boyd, Stephen and Vandenberghe, Lieven},
  title     = {Convex Optimization},
  publisher = {Cambridge University Press},
  year      = {2004}
}

@article{spielman2004smoothed,
  author  = {Spielman, Daniel A. and Teng, Shang-Hua},
  title   = {Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time},
  journal = {Journal of the ACM},
  volume  = {51},
  number  = {3},
  pages   = {385--463},
  year    = {2004}
}

Prerequisites

44.02.04
44.01.03

Tier anchors

beginner: Bertsimas & Tsitsiklis 1997 Introduction to Linear Optimization (Athena Scientific) Ch. 1, Ch. 3 — the geometry of feasible regions and corner-point optima; Boyd & Vandenberghe 2004 Convex Optimization (Cambridge) §4.3
intermediate: Bertsimas & Tsitsiklis 1997 Introduction to Linear Optimization (Athena Scientific) Ch. 2-Ch. 4 (geometry, the simplex method, duality); Boyd & Vandenberghe 2004 Convex Optimization (Cambridge) §4.3, §5.2
master: Bertsimas & Tsitsiklis 1997 Introduction to Linear Optimization (Athena Scientific) Ch. 3-Ch. 5; Schrijver 1986 Theory of Linear and Integer Programming (Wiley) §7-§11; Chvátal 1983 Linear Programming (Freeman); Boyd & Vandenberghe 2004 Convex Optimization (Cambridge) §4.3, §5.2

References

Bertsimas, D. & Tsitsiklis, J. N. — Introduction to Linear Optimization (Athena Scientific, 1997) · Ch. 1 (formulations), Ch. 2 (geometry, basic feasible solutions ↔ vertices), Ch. 3 (the simplex method, Bland's rule, two-phase), Ch. 4 (duality, complementary slackness), Ch. 5 (sensitivity analysis)
Boyd, S. & Vandenberghe, L. — Convex Optimization (Cambridge University Press, 2004) · §4.3 (linear programming, standard and inequality forms), §5.2 (the Lagrange dual of an LP)
Schrijver, A. — Theory of Linear and Integer Programming (Wiley, 1986) · §7 (Farkas and LP duality), §8 (polyhedra and vertices), §11 (the simplex method, pivot rules, complexity)
Dantzig, G. B. — Linear Programming and Extensions (Princeton University Press, 1963) · Ch. 5 (the simplex method), Ch. 6 (the duality theorem)
Klee, V. & Minty, G. J. — How good is the simplex algorithm? · Inequalities III (Academic Press, 1972), 159-175
Bland, R. G. — New finite pivoting rules for the simplex method · Mathematics of Operations Research 2 (1977), 103-107

Estimated time

beginner: 17m
intermediate: 45m
master: 76m