[proofplan] We encode the primal feasible values as the last coordinate of a finitely generated cone in $\mathbb{R}^{m+1}$. The attained optimum gives a boundary point $(b,\alpha)$ of this cone in the downward vertical direction. A separating hyperplane applied to the tangent cone at this boundary point gives a supporting normal with positive vertical component. After normalising that component to $1$, the horizontal part of the normal becomes a dual feasible vector whose objective value is exactly $\alpha$. [/proofplan] [step:Build the primal value cone and locate the optimal boundary point] For each $j \in \{1,\dots,n\}$, let $A_j \in \mathbb{R}^m$ denote the $j$th column of $A$, and let $c_j \in \mathbb{R}$ denote the $j$th coordinate of $c$. Define the vertical vector $e \in \mathbb{R}^{m+1}$ by \begin{align*} e := (0,\dots,0,1). \end{align*} Define the finitely generated cone $K \subset \mathbb{R}^{m+1}$ by \begin{align*} K := \{(Ax,c^\top x+r) : x \in \mathbb{R}^n,\ x \ge 0,\ r \in \mathbb{R},\ r \ge 0\}. \end{align*} Equivalently, \begin{align*} K = \operatorname{cone}\{(A_1,c_1),\dots,(A_n,c_n),e\}. \end{align*} Since finitely generated cones in finite-dimensional Euclidean space are closed convex polyhedral cones, $K$ is closed and convex. Let $x_* \in \mathbb{R}^n$ be a primal optimal solution, so $Ax_* = b$, $x_* \ge 0$, and $c^\top x_* = \alpha$. Then \begin{align*} u := (b,\alpha) \end{align*} belongs to $K$, by taking $x=x_*$ and $r=0$. If $t < \alpha$ and $(b,t) \in K$, then there exist $x \in \mathbb{R}^n$ and $r \in \mathbb{R}$ with $x \ge 0$, $r \ge 0$, $Ax=b$, and \begin{align*} t = c^\top x+r. \end{align*} Hence $c^\top x \le t < \alpha$, contradicting the definition of $\alpha$ as the minimum primal value. Therefore \begin{align*} (b,t) \notin K \quad \text{for every } t < \alpha. \end{align*} On the other hand, if $t \ge \alpha$, then \begin{align*} (b,t) = (Ax_*,c^\top x_* + (t-\alpha)) \in K. \end{align*} Thus $u=(b,\alpha)$ is the lower endpoint of the vertical section of $K$ above $b$. [/step] [step:Separate the downward vertical direction from the tangent cone] Let $T_K(u) \subset \mathbb{R}^{m+1}$ denote the tangent cone of the polyhedral cone $K$ at $u$, defined by \begin{align*} T_K(u) := \{d \in \mathbb{R}^{m+1} : u+\varepsilon d \in K \text{ for all sufficiently small } \varepsilon > 0\}. \end{align*} Because $K$ is polyhedral, $T_K(u)$ is a closed convex cone. The downward vertical direction $-e$ does not belong to $T_K(u)$: if $-e \in T_K(u)$, then $u-\varepsilon e=(b,\alpha-\varepsilon)$ would belong to $K$ for all sufficiently small $\varepsilon>0$, contradicting the conclusion of the previous step. By the finite-dimensional separating hyperplane theorem for a closed convex cone and a point outside it (citing a result not yet in the wiki: Separating Hyperplane Theorem), there exists a vector \begin{align*} w=(p,q) \in \mathbb{R}^m \times \mathbb{R} \end{align*} such that \begin{align*} w \cdot d \ge 0 \quad \text{for every } d \in T_K(u) \end{align*} and \begin{align*} w \cdot (-e) < 0. \end{align*} Since $w \cdot (-e)=-q$, this gives $q>0$. For every $k \in K$, the vector $k-u$ belongs to $T_K(u)$, because $K$ is convex and \begin{align*} u+\varepsilon(k-u)=(1-\varepsilon)u+\varepsilon k \in K \end{align*} for every $\varepsilon \in [0,1]$. Hence \begin{align*} w \cdot k \ge w \cdot u \quad \text{for every } k \in K. \end{align*} Taking $k=0 \in K$ gives $0 \ge w \cdot u$. Taking $k=2u \in K$, which is valid because $K$ is a cone, gives $2w \cdot u \ge w \cdot u$, hence $w \cdot u \ge 0$. Therefore \begin{align*} w \cdot u = 0 \end{align*} and \begin{align*} w \cdot k \ge 0 \quad \text{for every } k \in K. \end{align*} [guided] The geometric point is that the cone $K$ contains all points $(b,t)$ with $t \ge \alpha$, but contains no point $(b,t)$ with $t<\alpha$. Thus the direction $e$ points into $K$ from $u=(b,\alpha)$, while the direction $-e$ immediately points outside $K$. We formalise this using the tangent cone. Define \begin{align*} T_K(u) := \{d \in \mathbb{R}^{m+1} : u+\varepsilon d \in K \text{ for all sufficiently small } \varepsilon > 0\}. \end{align*} Because $K$ is a polyhedral cone, this tangent cone is itself a closed convex cone. The vector $-e$ is not in $T_K(u)$, since membership would imply that for all sufficiently small $\varepsilon>0$, \begin{align*} u-\varepsilon e=(b,\alpha-\varepsilon) \in K, \end{align*} which contradicts the already proved fact that no point $(b,t)$ with $t<\alpha$ belongs to $K$. We now separate the closed convex cone $T_K(u)$ from the point $-e$ outside it. By the finite-dimensional separating hyperplane theorem for a closed convex cone and an exterior point (citing a result not yet in the wiki: Separating Hyperplane Theorem), there exists \begin{align*} w=(p,q) \in \mathbb{R}^m \times \mathbb{R} \end{align*} such that \begin{align*} w \cdot d \ge 0 \quad \text{for every } d \in T_K(u) \end{align*} and \begin{align*} w \cdot (-e) < 0. \end{align*} Since $e=(0,\dots,0,1)$, the last inequality says $-q<0$, so $q>0$. This positivity is the essential point: it lets us divide by the vertical component and convert the supporting normal into a dual vector. It remains to turn this tangent-cone separation into a supporting inequality for the original cone $K$. Fix any $k \in K$. Since $K$ is convex and $u \in K$, the segment from $u$ to $k$ lies in $K$: \begin{align*} (1-\varepsilon)u+\varepsilon k \in K \quad \text{for every } \varepsilon \in [0,1]. \end{align*} Equivalently, \begin{align*} u+\varepsilon(k-u) \in K \quad \text{for every } \varepsilon \in [0,1], \end{align*} so $k-u \in T_K(u)$. Applying the separating inequality to $d=k-u$ gives \begin{align*} w \cdot (k-u) \ge 0. \end{align*} Thus \begin{align*} w \cdot k \ge w \cdot u \quad \text{for every } k \in K. \end{align*} Now we use the fact that $K$ is a cone to identify the supporting level. First, $0 \in K$, so the preceding inequality with $k=0$ gives \begin{align*} 0 \ge w \cdot u. \end{align*} Second, $2u \in K$, so the same inequality with $k=2u$ gives \begin{align*} 2w \cdot u \ge w \cdot u. \end{align*} Hence $w \cdot u \ge 0$. Combining the two inequalities yields \begin{align*} w \cdot u = 0. \end{align*} Therefore the same supporting inequality becomes \begin{align*} w \cdot k \ge 0 \quad \text{for every } k \in K. \end{align*} [/guided] [/step] [step:Normalise the supporting normal and read off dual feasibility] Since $q>0$, replace $w=(p,q)$ by $q^{-1}w$. After this rescaling, still denoted by $(p,1)$, we have \begin{align*} p^\top z+\tau \ge 0 \quad \text{for every } (z,\tau) \in K \end{align*} and \begin{align*} p^\top b+\alpha = 0. \end{align*} Define the vector $y_* \in \mathbb{R}^m$ by \begin{align*} y_* := -p. \end{align*} For each $j \in \{1,\dots,n\}$, the generator $(A_j,c_j)$ belongs to $K$. Applying the supporting inequality to this generator gives \begin{align*} p^\top A_j+c_j \ge 0. \end{align*} Equivalently, \begin{align*} A_j^\top y_* \le c_j. \end{align*} Since this holds for every $j$, we obtain \begin{align*} A^\top y_* \le c. \end{align*} Thus $y_*$ is dual feasible. The equality at $u=(b,\alpha)$ gives \begin{align*} p^\top b+\alpha = 0. \end{align*} Therefore \begin{align*} b^\top y_* = -p^\top b = \alpha. \end{align*} [/step] [step:Use weak duality to conclude optimality and equality of values] Let $x \in \mathbb{R}^n$ be any primal feasible vector, so $Ax=b$ and $x \ge 0$. Let $y \in \mathbb{R}^m$ be any dual feasible vector, so $A^\top y \le c$. Then \begin{align*} b^\top y = (Ax)^\top y = x^\top A^\top y. \end{align*} Because $x_j \ge 0$ and $(A^\top y)_j \le c_j$ for every $j \in \{1,\dots,n\}$, multiplying each coordinate inequality by $x_j$ and summing gives \begin{align*} x^\top A^\top y \le x^\top c = c^\top x. \end{align*} Hence every dual feasible value is bounded above by every primal feasible value. Applying this to the constructed dual feasible vector $y_*$ and to the primal optimal vector $x_*$ gives \begin{align*} b^\top y_* \le c^\top x_*=\alpha. \end{align*} But the previous step proved $b^\top y_*=\alpha$. Therefore $y_*$ attains the dual supremum, the dual optimal value is $\alpha$, and the primal and dual optimal values are equal. [/step]