TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck pass

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Primal revised-simplex pivot identities and certificates

Statement

Let $B$ be a primal-feasible basis for the standard-form problem of Revised simplex standard-form linear program and Basis dictionaries and reduced costs for revised simplex, and let $j$ be a nonbasic index with reduced cost ${\overset{ˉ}{c}}_{j} < 0$ . Put $d = A_{B}^{- 1} a_{j}$ . If $d_{i} \leq 0$ for every basic row $i$ , then $r_{j} = 1$ , $r_{B} = - d$ , and $r_{k} = 0$ for the other nonbasic indices define a feasible ray with $A r = 0$ and $c^{T} r = {\overset{ˉ}{c}}_{j} < 0$ ; the LP is unbounded below. If some $d_{i} > 0$ , the step $θ = \min_{d_{i} > 0} (x_{B_{i}} / d_{i})$ is finite and nonnegative, every minimizing row gives a valid pivot, the new basic vector is feasible, and the objective change is $θ {\overset{ˉ}{c}}_{j} \leq 0$ , strictly negative exactly when $θ > 0$ . Finally, if all nonbasic reduced costs are nonnegative at a primal-feasible basis, its basic vector is optimal.

Facts & Assumptions

Given: The standard-form data, a primal-feasible basis $B$ , and a nonbasic $j$ with ${\overset{ˉ}{c}}_{j} < 0$ when considering a pivot.

[F1]

Revised simplex standard-form linear program: Its feasible set is $P (A, b) = {x \in R^{n} : A x = b, x_{j} \geq 0 for every j}$ , and a feasible $x$ is optimal if $c^{T} x \leq c^{T} z$ for every $z \in P (A, b)$ .

[F2]

Basis dictionaries and reduced costs for revised simplex: For every column $j$ , its reduced cost is ${\overset{ˉ}{c}}_{j} = c_{j} - a_{j}^{T} y (B)$ , and each basic reduced cost is zero.

[F3]

Inequality constrained programs, tangent cones, constraint qualifications, and KKT: The KKT system requires primal feasibility, nonnegative inequality multipliers, complementary products $λ_{i} g_{i} (x) = 0$ , and zero Lagrangian gradient.

[F4]

Convex KKT conditions certify a global minimum and an outward normal: On an open convex domain, a differentiable convex objective and inequalities with a feasible KKT tuple and nonnegative inequality multipliers certify a global minimum.

Proof

1.1F1F2algebra

Define $r_{j} = 1$ , $r_{B} = - d$ , and all other nonbasic components of $r$ to be zero. Since $A_{B} d = a_{j}$ , we have $A r = a_{j} - A_{B} d = 0$ ; also $c^{T} r = c_{j} - c_{B}^{T} A_{B}^{- 1} a_{j} = {\overset{ˉ}{c}}_{j}$ .

2.1givenF1step 1.1algebra

If every $d_{i} \leq 0$ , then $r \geq 0$ , so $x + λ r$ is feasible for every $λ \geq 0$ . Its cost is $c^{T} x + λ {\overset{ˉ}{c}}_{j}$ , which tends to $- \infty$ as $λ \to \infty$ ; this proves the ray branch.

2.2givenF1step 1.1choosealgebra

If some $d_{i} > 0$ , set $θ = \min_{d_{i} > 0} x_{B_{i}} / d_{i}$ . Each ratio is nonnegative, the finite nonempty index set has a minimum, and $x_{B} - θ d \geq 0$ : rows with $d_{i} > 0$ satisfy the ratio bound, while rows with $d_{i} \leq 0$ do not decrease. The entering component is $θ \geq 0$ , so $x + θ r$ is feasible.

3.1F2step 2.2algebra

For any minimizing row $i$ , replacing column $B_{i}$ by $a_{j}$ gives a basis: in coordinates of $A_{B}$ , the replacement column is $d$ , whose $i$ th entry is positive, so expansion along that column gives a nonzero determinant. The unique basic vector of the new basis is $x + θ r$ , because that vector satisfies the constraints and has zero on the remaining nonbasic variables.

3.2step 1.1step 2.2algebra

The objective change is $c^{T} (x + θ r) - c^{T} x = θ c^{T} r = θ {\overset{ˉ}{c}}_{j}$ . Since $θ \geq 0$ and ${\overset{ˉ}{c}}_{j} < 0$ , it is nonpositive and is zero exactly when $θ = 0$ , the degenerate-pivot case.

4.1givenF1F2F3F4algebra∎

If $n = 0$ , the feasible set contains only the empty vector, so its feasible basic vector is optimal. Suppose $n \geq 1$ . Set $U = R^{n}$ , $f (z) = c^{T} z$ , $h (z) = A z - b$ , $g_{j} (z) = - z_{j}$ , $ν = - y (B)$ , and $λ = c - A^{T} y (B)$ . The open convex domain is $U = R^{n}$ , and the affine functions are differentiable and convex. The vector $λ$ is the reduced-cost vector, including zero basic coordinates by [F2], so it is nonnegative; $x$ is feasible by hypothesis. For each $j$ , either $j$ is nonbasic and $x_{j} = 0$ , or $j$ is basic and $λ_{j} = 0$ , so $λ_{j} g_{j} (x) = 0$ . Since $D g = - I$ , the stationarity expression is $\nabla f (x) + A^{T} ν + D g (x)^{T} λ = c - A^{T} y (B) - λ = 0$ . These are precisely the KKT conditions of [F3], and [F4] proves that $x$ globally minimizes $c^{T} z$ over $P (A, b)$ .

Depends on

Used by

A degenerate six-pivot cycle prevented by Bland's rule Example
A one-pivot primal and dual certificate trace Example
A revised-simplex unbounded ray Example
Bland-rule finite termination and optimal-basis existence Theorem

Dependency tree · two levels

9 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Dimitris Bertsimas and John N. Tsitsiklis, Introduction to Linear Optimization, §§3.1–3.3 (standard reference, not scraped)
Michel Goemans, MIT 18.310 Lecture Notes: Linear Programming, §§2–3 (standard reference, not scraped)