Past exam of the mathematics course of the University of Cambridge / 2001 / iii / Paper 31 / 3

A reduction must encode primal solutions and infeasibility or unboundedness information; merely declaring a known optimum or subtracting an unknown optimum from the objective function is not a construction. The following homogeneous self-dual embedding of a linear program works without assuming the input problem has an optimum.

First remove linearly dependent equality rows by Gaussian elimination. If an eliminated row has an inconsistent right-hand side, the original problem is already certified infeasible. Return the one-variable special-form program $\min 0$ with $A^{\ast }=0$, $y=1$, and retain that certificate; no original mathematical optimization remains. Otherwise the remaining matrix has full row rank; write it as $A$ again. Put $e=1\in {\mathbb{R}}^n$ andUse nonnegative variables $x,s\in {\mathbb{R}}^n$ and $\tau ,\kappa ,\theta ,\rho \in \mathbb{R}$, with a temporary unrestricted multiplier $\lambda \in {\mathbb{R}}^m$. Impose the homogeneous linear systemAll coefficients are computable from the input. The temporary free multiplier can be eliminated without introducing cancelling positive/negative variables. DefineReplace the second equation by $(I-A^{T}H)q=0$, and substitute $Hq$ in the other equations. Because $A$ has full row rank, $A^T\lambda =q$ is equivalent to these conditions. For no remaining equality rows, simply omit $\lambda$ and its empty equations.

Let $y=(x,s,\tau ,\kappa ,\theta ,\rho )$ and $n^{\ast }=2n+4$. Collect these substituted equations into $A^{\ast }y=0$, impose $1^{T}y=1$, and let $c^{\ast }$ select the coordinate $\theta$. The resulting Karmarkar standard form isThe next two parts prove its known positive starting point and zero optimal value. Notice that normalization is legitimate for any nonzero nonnegative embedding vector because all the equations are homogeneous; it does not require a prior bound on the original optimizer.

In the unnormalized embedding, takeThen the first equation is $Ae-b+\bar{b}=0$, the second is $c-e-\bar{c}=0$, and the third is $-c^{T}e-1+\bar{z}=0$. The fourth becomesThe multiplier elimination preserves this point because $q=c-e-\bar{c}=0$ and hence $Hq=0$. Every coordinate of $y$ is one. Dividing by $n^{\ast }=2n+4$ therefore giveswhich satisfies $A^{\ast }{y}^{(0)}=0$, $1^T{y}^{(0)}=1$, and strict positivity. Its existence is independent of feasibility of the original input problem.

The objective function $\theta$ is nonnegative. We now construct a feasible zero-objective point, distinguishing the input problem's possible states.

If the primal is feasible and bounded below, strong duality and attainment for a linear program give $x_{\ast }\ge 0$, ${\lambda }_{\ast }$ and $s_{\ast }=c-A^T{\lambda }_{\ast }\ge 0$ withSet $\theta =\kappa =0$, $\tau =1$, $x=x_{\ast }$, $s=s_{\ast }$, $\lambda ={\lambda }_{\ast }$, andThe first three embedding equations hold. Substituting their equalities into the fourth gives precisely $-e^T{x}_{\ast }-e^T{s}_{\ast }-1+N\rho =0$.

If the primal is infeasible, the Farkas alternative supplies $\lambda$ with $A^T\lambda \le 0$ and $b^T\lambda >0$. Take $x=\tau =\theta =0$, $s=-A^T\lambda \ge 0$, $\kappa =b^T\lambda >0$, and $\rho =(e^{T}s+\kappa )/N$. These satisfy the same equations. If the primal is feasible and unbounded below, it has a direction in the recession cone $x\ge 0$ with $Ax=0$ and $c^{T}x<0$. Set $\lambda =s=\tau =\theta =0$, $\kappa =-c^{T}x>0$, and $\rho =(e^{T}x+\kappa )/N$. This is again a feasible nonzero embedding vector. Normalize the constructed vector by the sum of its nonnegative coordinates. In every case,The facts about optimal pairs and recession directions follow from the polyhedral alternatives of linear programming duality; they do not require knowing their values or witnesses to write the transformed coefficients.

To recover information from the transformed optimum, multiply the first three original embedding equations by ${\lambda }^T$, $x^T$, and $\tau$, respectively, and add. Their cross terms cancel; the fourth equation givesAt $\theta =0$, nonnegativity forces $x^{T}s=0$ and $\tau \kappa =0$. The equations also implyThus any normalized zero-objective point has $\rho >0$: if $\rho =0$, all these coordinates vanish, and then $q=\lambda =\theta =0$, contradicting normalization.

If $\tau >0$, division by $\tau$ gives a primal-feasible point $x/\tau$ and dual-feasible point $\lambda /\tau$ with equal objective function values; hence they are optimal. If $\kappa >0$, then $\tau =0$, $Ax=0$, $A^T\lambda =-s\le 0$, andTherefore either $b^T\lambda >0$ certifies primal infeasibility, or $c^{T}x<0$ is an improving recession direction certifying dual infeasibility and unboundedness whenever the primal is feasible. If only the latter certificate is obtained and primal feasibility is unknown, apply the same construction to the feasibility problem with objective function $c=0$; it gives either a feasible point or a direct primal infeasibility certificate.

A degenerate optimal point can have $\tau =\kappa =0$ and convey neither conclusion. Choose an optimum in the relative interior of the optimal face of a linear program. The explicit existence argument above gives a point of this face with $\tau +\kappa >0$. A nonnegative coordinate which is positive somewhere on a face of a convex set is positive throughout its relative interior, so the chosen point has $\tau +\kappa >0$ and can be decoded. The assertion follows because a small relative-interior displacement in the direction opposite a positive-coordinate point would otherwise make that coordinate negative. Equivalently one may obtain a maximum-support optimum; choosing an arbitrary degenerate boundary optimum is insufficient.

This reduction is useful because an interior-point method now has a known strictly feasible start, a compact standard simplex slice, and a known target objective function. Projective rescalings can recenter positive iterates, and the transformed problem supplies optimality or infeasibility information without a separate guessed optimum. Polynomial bit-complexity claims need rational data with a finite encoding length. The printed bound $U$ on arbitrary real coefficients by itself does not bound denominators or the size of nonzero determinants; it is not a substitute for that encoding assumption.