= Solution
Let the finite primal supremum be $v$. First it is attained. The set
$$
K=\{(Ax+s,c^Tx-t):x,s,t\geq0\}
$$
is a <finitely generated cone>, hence closed by the argument in the root Solution. For a sequence of primal <feasible points> whose values approach $v$, the pairs $(b,c^Tx)$ belong to $K$. Their limit $(b,v)$ therefore belongs to $K$. It gives a <feasible point> $x_*$ with $c^Tx_*\geq v$, so necessarily $c^Tx_*=v$.
Let $I$ index the tight primal inequalities at $x_*$ and let $Z$ index its zero coordinates. Consider the closed <convex cone> generated by $A_i^T$ for $i\in I$ and $-e_j$ for $j\in Z$. If $c$ were outside this cone, <separation from a closed convex cone> would give a direction $d$ with
$$
A_id\leq0\ (i\in I),\qquad d_j\geq0\ (j\in Z),\qquad c^Td>0.
$$
For sufficiently small positive $\delta$, $x_*+\delta d$ remains a <feasible point>: the active constraints have the required signs, and every inactive constraint retains its positive slack. Its larger objective contradicts optimality. Therefore there are $y_i\geq0$, supported on $I$, and $\mu_j\geq0$, supported on $Z$, such that
$$
c=A^Ty-\mu.
$$
This makes $y$ a dual <feasible point>. Moreover, the support restrictions give
$$
b^Ty=y^TAx_*=c^Tx_*+\mu^Tx_*=v.
$$
Together with <weak duality>, this proves <strong duality> and dual attainment:
$$
\boxed{D\text{ is feasible, has minimum }v,\text{ and is bounded below}.}
$$
Back to article page
