Try
Suppose a feasible region is known to lie inside the unit disk, but its center is infeasible. A separation oracle supplies a line proving that every feasible point lies in the left half-disk. Instead of searching that half directly, enclose it in a smaller-area ellipse and query its center next. The ellipsoid method repeats this geometry. A valid oracle cut preserves every feasible point; an arbitrary line drawn through a failed trial point has no such guarantee.
Predict
Predict whether simply halving the radius of the disk will enclose the left half. It will not: the cut endpoints on the vertical diameter remain far apart. The new ellipse must contract along the cut normal while expanding somewhat in transverse directions. Overall volume still shrinks. This is why the update uses a full positive-definite shape matrix rather than one scalar radius. In one dimension the analogous operation is ordinary interval halving, which needs its own formula.
Experiment
For the unit ball in dimension n≥2 cut by x₁≤0, the standard central-cut enclosing ellipsoid has center −e₁/(n+1), squared axial radius n²/(n+1)² and squared transverse radius n²/(n²−1). Inspect the two-dimensional case.
| Quantity | Value when n=2 |
|---|
| Center | (−1/3,0) |
| Squared horizontal radius | 4/9 |
| Squared vertical radius | 4/3 |
| Area ratio to original disk | 4/(3√3) |
Check containment of (−1,0), (0,1) and (0,−1). Those boundary checks motivate the shape but do not prove full containment. For that, write t=x₁ in [−1,0] and use ||x_perp||²≤1−t². Substitution into the new ellipsoid’s defining quadratic gives at most 1+2(n+1)t(t+1)/n²≤1, proving containment for every point in the half-ball.
Understand
Represent an ellipsoid by E(c,Q) consisting of x with (x−c)ᵀQ⁻¹(x−c)≤1, where Q is positive definite. For a nonzero normal a and central cut aᵀ(x−c)≤0, affine transformation of the half-ball formula gives c_new=c−Qa/((n+1)√(aᵀQa)) and Q_new=[n²/(n²−1)]·[Q−2QaaᵀQ/((n+1)aᵀQa)]. The axial and transverse calculations prove positive definiteness and containment. Its volume ratio is [n²/(n²−1)]^(n/2)√((n−1)/(n+1)), strictly below one. In dimension one, replace the interval by its retained half rather than using the singular n²−1 denominator.
If an oracle gives a stronger inequality aᵀx≤β with aᵀc>β, the weaker central cut still contains the feasible set. Repeated cuts reduce volume, but a stopping conclusion needs a target: for example, a promised feasible set containing a ball of known radius cannot remain inside an enclosure of smaller volume. Lower-dimensional sets have zero volume, so this argument alone cannot distinguish them from infeasibility.
Apply
Explain what “polynomial-time LP” means. Rational input has a bit length, and arithmetic precision, separation cost, initial bounds and exact or weak feasibility conventions must be controlled. The ellipsoid framework, with the required encoding and rounding theory, establishes polynomial-time solvability of rational LP. The geometric update alone is not a complete bit-complexity proof. The extensions below prove the rounding/encoding bridge for exact rational feasibility and optimization on a bounded feasible polytope; they name the basic-solution, Farkas and rational-reconstruction dependencies explicitly.
Compare this with simplex: some pivot rules and examples require exponentially many pivots, despite excellent practical performance on many applications. A worst-case theorem does not rank all solvers on every workload. Count oracle calls, arithmetic operations and numerical precision separately before making a computational claim.
A proved center-rounding allowance
Here is one precise finite-precision mechanism, without claiming the full rational LP complexity theorem. Suppose an exact update is E(c,Q), with Q positive definite, and a stored center c̃ satisfies the certified bound ||c̃−c|| in the Q⁻¹ norm ≤η. Keep Q exact for this lemma. For every x in E(c,Q), the triangle inequality gives ||x−c̃|| in that norm ≤1+η. Consequently E(c,Q) is contained in E(c̃,(1+η)²Q). This is an outward inflation, not permission to round the center and retain the old shape.
In dimension n, this inflation multiplies volume by (1+η)^n. It must be combined with the exact central-cut contraction factor ρₙ from the earlier derivation. A sufficient condition for retained strict contraction is ρₙ(1+η)^n<1. No numerical plot is needed for the containment proof; a numerical estimate alone is not a certified bound on center error.
Worked two-dimensional comparison. For n=2, ρ₂=4/(3√3). With η=1/100 the product is about 0.7853, below 1. With η=1/5 it is about 1.1085, above 1. In the latter case the enclosure remains valid, but this estimate no longer proves progress. Safety and progress are different obligations.
Changed written task. If the exact center is shifted along the major axis of an ellipse, which physical displacement is permitted by η? Write Q=diag(a²,b²). Feedback: the condition is (Δx/a)²+(Δy/b)²≤η², so pure horizontal displacement may be as large as aη. A Euclidean displacement tolerance used without axis scaling is not the same certificate. To extend this lemma to a rounded shape Q̃, one needs a verified matrix inequality ensuring sufficient outward enclosure as well as positive definiteness. The following sections supply a matrix enclosure, bit budget and rational thin-set reduction; those obligations cannot be skipped by using this center-only lemma.
A finite-precision theorem with an explicit promise
Here is a proved weak-feasibility contract rather than an unexplained claim about exact rational LP. Assume n≥2, an initial ball of radius R centered at zero, and a separation oracle whose rational cut normals have polynomially bounded encoding. The target convex set K is promised either empty or to contain a Euclidean ball of radius r>0. An oracle response at a center either certifies membership or supplies a valid central cut retaining K. The algorithm must return a feasible center or rule out the radius-r promise. Without that promise, a small volume does not prove emptiness.
Round both shape and center outward
Let Q be the exact shape after one central cut. Suppose rational storage produces S with ||S−Q||₂≤δ, and a center c̃ with ||c̃−c||₂≤e. Set T=S+δI. Then Q≤T≤Q+2δI in the positive-semidefinite order. If Q≥ℓI, T≤(1+2δ/ℓ)Q. The inverse order gives ||x−c|| in the T⁻¹ norm at most 1 for x in E(c,Q), while ||c−c̃|| in that norm is at most e/√ℓ. The triangle inequality therefore proves
E(c,Q) ⊆ E(c̃,(1+η)²T), provided e≤η√ℓ.
If each entry of S is rounded with error at most δ/n, then its Frobenius norm error, and hence its operator norm error, is at most δ. This is a checkable entrywise precision rule, not an assumption that entrywise upward rounding preserves matrix order. Positive definiteness follows from T≥Q>0.
Choose η=1/(32n²), δ=ℓ/(32n²). The additional volume factor is at most (1+η)^n(1+2δ/ℓ)^(n/2), whose logarithm is at most 1/(16n), using log(1+z)≤z. The exact central-cut log-volume ratio is at most−1/(2(n+1)); thus even after rounding the log ratio is at most−1/(4(n+1)). For completeness, expanding the determinant ratio gives log ρₙ=−Σ over j≥0 of 1/[2(j+1)(2j+1)n^(2j+1)]≤−1/(2n)≤−1/(2(n+1)); all series converge since n≥2. This supplies the exact bound rather than relying on a sampled contraction ratio. Consequently N>4n(n+1)log(R/r) iterations without a certified feasible center make enclosure volume smaller than the volume of a radius-r ball. That contradicts the nonempty alternative of the promise.
Why the precision budget is polynomial
An exact central cut has Q_new≥[n²/(n+1)²]Q_old≥(4/9)Q_old. Outward rounding cannot reduce this lower bound. Therefore ℓₖ=R²(4/9)^k is a valid conservative eigenvalue floor. The prescribed δ and e require O(k+log n+|log R|) fractional bits. Upper eigenvalues grow by at most a fixed constant per step under these bounded inflations; centers are sums of N bounded step lengths. Their integer-bit requirements are also polynomial in N and the input scale. Rational arithmetic and square-root approximation to these certified tolerances are finite operations. A polynomial number of iterations with polynomial-length oracle data therefore gives a polynomial bit bound for this promised-ball problem, including the rounding contract.
The enclosure is not a universal exact-LP implementation. Exact rational feasibility additionally needs the encoding reduction developed next: a small rational relaxation and certificate gap avoid the thin-set error. Bounded objective recovery also requires rational reconstruction; the final section supplies the recession alternative for arbitrary unbounded feasible sets. MIT’s nonlinear optimization lecture 5, inspected 30 October 2026, explicitly separates finite-precision details from the geometric idea.
Changed case. Let K be the segment joining(−1,0) and(1,0) in R². Can any positive r satisfy the full-dimensional promise? Feedback: no; the segment contains no Euclidean disk, though it is nonempty. Restrict to its one-dimensional affine hull and use interval reasoning, or invoke an independently justified exact-feasibility reduction. Neither many cuts nor tiny numerical residuals proves emptiness.
Reduce exact rational feasibility to the promised-ball case
The missing bridge can be made explicit for finite rational inequalities Ax≤b. Clear denominators in each row by positive multiplication, so A,b are integers of magnitude at most H≥1. Row clearing increases bit length only polynomially in the original encoding. Let m be the number of rows and n the number of variables. Handle m=0 or zero variables directly; one-variable search uses interval halving rather than the n≥2 ellipsoid update. We use two already taught linear-program facts: a nonempty standard-form polyhedron has a basic feasible solution after redundant equations are removed, and Farkas’ alternative supplies y≥0 with yᵀA=0,yᵀb<0 when the inequalities are infeasible. These are theorem dependencies, not conclusions drawn from numerical ellipsoid traces.
Write x=x⁺−x⁻ and Ax⁺−Ax⁻+s=b with nonnegative variables. A basic solution is obtained by solving an invertible r-by-r integer subsystem, r≤m, with all nonbasic variables zero. Cramer’s rule and the determinant expansion bound each numerator by r!H^r and a nonzero integer denominator below by 1. Thus if the original system is feasible, it has a point with |x_j|≤B=m!H^m. This bound is deliberately loose but log B is polynomial in the input length.
If the system is infeasible, scale a Farkas vector so yᵀb=−1. The standard-form system y≥0,Aᵀy=0,bᵀy=−1 has a basic solution. The same determinant argument, now with at most n+1 independent rows, bounds each coordinate by C=(n+1)!H^(n+1). Hence Σy_i≤mC. Choose the rational relaxation ε=1/(2 mC). Every point satisfying Ax≤b+ε1 would obey 0=yᵀAx≤−1+εΣy_i≤−1/2, a contradiction. So an infeasible original system has an empty relaxation at this explicitly chosen precision.
For a feasible original system, take its bounded point x₀ and consider K defined by Ax≤b+ε1 and |x_j|≤2B. A ball around x₀ of radius r=min(B/2, ε/(2 nH)) lies in K: each original row changes by at most nH r≤ε/2, and each coordinate remains inside the larger box. The set K lies in the ball of radius R=2 Bn about zero. Both log R and log(1/r) are polynomial in m,n and log H. An exact rational violated-row oracle is immediate. The proved rounded ellipsoid procedure therefore decides original feasibility: a point in K proves original feasibility by the Farkas gap argument, while ruling out its radius-r ball proves original infeasibility by the bounded feasible-point argument. The returned relaxed point is not itself asserted to satisfy the original inequalities.
Recover an exact point rather than rounding a near-feasible one
If exact coordinates are requested, use the exact feasibility decision as an oracle, not coordinatewise rounding. Intersect the feasible set with |x_j|≤2B. It is a nonempty bounded rational polytope. With K₀=max(H,2B), every vertex coordinate has reduced denominator at most D=n!K₀^n by Cramer’s rule. Minimize its first coordinate by bisection with feasibility queries adding x₁≤q, initially between−2B and 2B. After a polynomial number of queries, the interval width is less than 1/(2D²). Distinct rationals with denominators at most D are separated by at least 1/D², so the optimum is the unique such rational in the interval; continued-fraction rational reconstruction finds it using integer arithmetic.
Fix that exact coordinate by two inequalities and repeat for the next coordinate. Each selected minimum cuts out a nonempty exposed face of the original bounded polytope. Its vertices are still original vertices, so the original denominator bound D remains valid throughout; do not recursively inflate D as though each stage created arbitrary new vertices. After n coordinates the remaining point satisfies every original inequality exactly. Each oracle call has polynomial encoding, and the number of calls is polynomial. This completes the finite rational-feasibility reduction, with explicit reliance on basic solutions, Farkas and rational reconstruction.
For optimization over a bounded feasible rational polytope with a supplied valid bounding box, the same argument minimizes cᵀx first, using the denominator bound adjusted for the objective’s rational denominators, then fixes its value and reconstructs a point on the optimal face. The following recession/lineality proof justifies when the bounding box preserves an optimum for arbitrary unbounded input; imposing a box without that argument would be invalid. A claimed optimum always needs primal feasibility and a matching valid lower bound, not only a successful feasibility query.
Transfer check. Why does relaxing by an arbitrary decimal such as 0.001 fail as a universal exact test? Consider the inconsistent pair x≤0 and x≥δ for a positive rational δ<0.002. Relaxing both by 0.001 makes the interval nonempty. The allowed ε must depend on the input encoding/certificate bound, not a display precision selected in advance.
Finish the unbounded and lineality cases
A bounding box is safe for an optimum only after proving why it cannot discard every optimum. We now supply that argument and the exact three-way classification: infeasible, feasible with a finite attained optimum, or unbounded below. All coefficients and the objective are rational; the finite-dimensional setting matters.
Prove the standard-form decomposition
Consider P={z≥0:Bz=b}. Redundant equality rows are checked and removed. A feasible z whose positive-support columns are independent is a basic feasible solution by the earlier vertex criterion. If those columns are dependent, choose a nonzero h supported there with Bh=0.
If h has both positive and negative entries, the two directions from z along h reach nonnegative endpoints z⁺,z⁻, each with smaller positive support. The original z is their convex combination, since it lies between them on the same line. If h has one sign, reverse it if necessary so h≥0. Subtract t h with t=min over h_i>0 of z_i/h_i. Then z’=z−t h is feasible with smaller support, and z=z’+t h expresses the removed part as a nonnegative recession direction. Iterating the support decrease terminates; in the two-sided case apply it to both endpoints. Thus every feasible point is a convex combination of basic feasible points plus a sum of nonnegative null directions.
Normalize each nonzero nonnegative null direction by its coordinate sum. It lies in Q={r≥0:Br=0,Σr_i=1}. This set is bounded. Applying the same support reduction to Q yields only two-sided steps: a nonzero dependence preserving the coordinate sum has both signs. Hence every r in Q is a convex combination of its basic feasible points. There are finitely many possible bases. Call the resulting finite lists of points V and normalized rays R. We have proved
P=conv(V)+cone(R).
The reverse inclusion follows immediately from Bv=b,Br=0 and nonnegativity. This proof also establishes that nonempty P has a basic feasible point; it does not assume one exists at the start. If Q is empty, the ray list is empty. Degenerate bases may repeat points and can be discarded. For rational data these points and rays are rational because each is obtained from an invertible rational subsystem.
Derive the objective alternative
For any objective aᵀz, a negative ray aᵀr<0 gives aᵀ(v+tr)→−∞ as t→∞. If every ray has nonnegative objective, the decomposition gives aᵀz≥min over v in V of aᵀv. That minimum is attained at one of the finitely many basic feasible points. Thus there is no missing fourth case of a finite unattained infimum for a nonempty polyhedron. That phenomenon can occur for nonpolyhedral convex domains, so the proof’s finite-generator structure is essential.
Return to Ax≤b and objective cᵀx using x=x⁺−x⁻ and nonnegative slacks. A nonnegative standard-form null ray projects to d=d⁺−d⁻ with Ad≤0. A negative objective ray has cᵀd<0. Conversely, any such d sends every feasible x₀ along feasible points x₀+td with objective decreasing without bound. Scaling gives the exact rational feasibility test
Ad≤0, cᵀd≤−1.
Lineality causes no omission. A vector with Ad=0 is feasible in both ray directions; if cᵀd is nonzero, choose the decreasing sign. If cᵀd=0, objective values are constant along that line. Splitting unrestricted variables may also create rays that project to d=0; their projected objective is zero, so they cannot be mistaken for unbounded descent.
An exact polynomial classification procedure
- Apply the exact feasibility reduction to Ax≤b. If infeasible, obtain a normalized rational Farkas certificate by solving its certificate system, and verify its signs and products.
- If feasible, apply the same reduction to Ad≤0,cᵀd≤−1. A feasible result supplies a rational direction. Recover an exact feasible base point by the earlier bounded-point procedure; the pair (x₀,d) certifies unboundedness. A direction alone does not certify that an infeasible primal problem is unbounded.
- If the recession system is infeasible, the decomposition proves finite attainment. The optimal standard-form basic point obeys the same determinant coordinate bound B from the original integer-cleared constraints. Thus restricting |x_j|≤2B preserves at least one optimizer, even if the original feasible set is unbounded. The bounded-polytope optimization/reconstruction procedure now applies without discarding the optimum.
Every added feasibility system has polynomial encoding. Objective denominator clearing uses a positive factor and is reversed in the reported value. The finite bit bounds and rational reconstruction established above therefore cover all three cases. For a finite optimum, the linear duality lesson supplies matching multipliers; a valid displayed primal/dual pair independently checks the optimum, while an implementation should not substitute tiny floating residuals for these exact inequalities.
Changed certificate exercise. Minimize x₁−2x₂ subject to x₁−x₂≥1 and x₁,x₂≥0. The point(1,0) is feasible and d=(1,1) preserves x₁−x₂ while reducing the objective at rate−1, so the problem is unbounded below. Change the objective to x₁+x₂: every allowed recession direction has nonnegative coordinates and nonnegative objective, and (1,0) attains value1. Finally add x₁−x₂≤0: the constraints are inconsistent; the old descent direction does not turn this empty problem into an unbounded one. Supply a separate certificate for each version rather than reusing a numerical solver label.
Continue
Every cut must retain the feasible region, and every infeasibility conclusion must name its geometric or encoding assumptions. Continue to Gradient descent for a method whose progress depends on objective smoothness rather than shrinking an enclosing volume. Later interior-point lessons provide another route to polynomial-time LP theory, again separating a useful update formula from the theorem controlling total computational work.
