= Solution
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_*\ge0$, $\lambda_*$ and $s_*=c-A^T\lambda_*\ge0$ with
$$
Ax_*=b,\qquad c^Tx_*=b^T\lambda_*.
$$
Set $\theta=\kappa=0$, $\tau=1$, $x=x_*$, $s=s_*$, $\lambda=\lambda_*$, and
$$
\rho=\frac{e^Tx_*+e^Ts_*+1}{N}>0.
$$
The first three embedding equations hold. Substituting their equalities into the fourth gives precisely $-e^Tx_*-e^Ts_*-1+N\rho=0$.
If the primal is infeasible, the <Farkas alternative> supplies $\lambda$ with $A^T\lambda\le0$ and $b^T\lambda>0$. Take $x=\tau=\theta=0$, $s=-A^T\lambda\ge0$, $\kappa=b^T\lambda>0$, and $\rho=(e^Ts+\kappa)/N$. These satisfy the same equations. If the primal is feasible and unbounded below, it has a direction in the <recession cone> $x\ge0$ with $Ax=0$ and $c^Tx<0$. Set $\lambda=s=\tau=\theta=0$, $\kappa=-c^Tx>0$, and $\rho=(e^Tx+\kappa)/N$. This is again a feasible nonzero embedding <vector>. Normalize the constructed <vector> by the sum of its nonnegative coordinates. In every case,
$$
\boxed{\min c^{*T}y=\min\theta=0.}
$$
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 gives
$$
x^Ts+\tau\kappa=N\theta\rho.
$$
At $\theta=0$, nonnegativity forces $x^Ts=0$ and $\tau\kappa=0$. The equations also imply
$$
e^Tx+e^Ts+\tau+\kappa=N\rho.
$$
Thus 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\le0$, and
$$
b^T\lambda-c^Tx=\kappa>0.
$$
Therefore either $b^T\lambda>0$ certifies primal infeasibility, or $c^Tx<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.
Back to article page
