We prove strong duality of linear program by Farkas Lemma.

Let A∈Rm×nA \in \mathbb{R}^{m \times n}, b∈Rmb \in \mathbb{R}^m, and c,x∈Rnc, x \in \mathbb{R}^n. Consider the primal program defined as

max⁡cTxs.t.Ax=b ,x≥0. \begin{array}{ll} \max &c^T x \\ \text{s.t.} &Ax = b \,, \\ &x \ge 0 . \end{array}

Let y∈Rmy \in \mathbb{R}^m. The dual program of the primal is given by

min⁡yTbs.t.yTA≥cT. \begin{array}{ll} \min &y^T b \\ \text{s.t.} &y^T A \ge c^T. \end{array}

Theorem. If both primal and dual are feasible, then max⁡=min⁡\max = \min.

Proof 1. Note that

cTx≤(yTA)x=yT(Ax)=yTb. c^T x \le (y^T A) x = y^T (A x) = y^T b.

The first inequality follows from that yTA≥0y^T A \ge 0 and that x≥0x \ge 0. The last equality follows from that Ax=bAx = b.

This is know as weak duality. It is left to prove the reverse direction.

Assume that the dual is feasible and min⁡=α\min = \alpha. The goal is to prove that max⁡≥α\max \ge \alpha. It suffices to find an x∈Rnx \in \mathbb{R}^n satisfying

  1. x≥0x \ge 0,
  2. Ax=bAx = b and,
  3. cTx≥αc^T x \ge \alpha.

Consider the convex and closed set

P≐{(z1,z2)∈Rm×R:z1=Ax, z2≤cTx, x∈Rn, x≥0}. P \doteq \{(z_1, z_2) \in \mathbb{R}^m \times \mathbb{R}: z_1 = A x,\, z_2 \le c^T x,\, x \in \mathbb{R}^n,\, x \ge 0\}.

Let bˉ≐(b,α)\bar{ b } \doteq (b, \alpha). If bˉ∈P\bar{ b } \in P, we have done. Otherwise, we are going to prove that ∃y∈Rm\exists y \in \mathbb{R}^m, such that

yTA≥cT, and  yTb<α. y^T A \ge c^T ,\, \text{and } \, y^T b < \alpha.

Let zˉ∈Rm×R\bar{ z } \in \mathbb{R}^m \times \mathbb{R} be the projection of bˉ\bar{ b } to PP, i.e., the point in PP that minimizes its distance to bˉ\bar{ b }. Denote v=zˉ−bˉ=(v1,v2)∈Rm×Rv = \bar{ z } - \bar{ b } = (v_1, v_2) \in \mathbb{R}^m \times \mathbb{R}. Consider the supporting plane

ℓ(z)≐vT(z−zˉ). \ell(z) \doteq v^T (z - \bar{ z }).

We have ℓ(bˉ)<0\ell(\bar{ b }) < 0 and ℓ(z)≥0\ell(z) \ge 0 for all z∈Pz \in P. As 0∈P0 \in P and 2zˉ∈P2 \bar{ z } \in P, it holds that

ℓ(0)=vT(−zˉ)≥0,ℓ(2zˉ)=vT(zˉ)≥0. \ell(0) = v^T (-\bar{ z }) \ge 0, \quad \ell(2 \bar{ z }) = v^T (\bar{ z }) \ge 0.

It follows that vTzˉ=0v^T \bar{ z } = 0. Hence vTz≥0v^T z \ge 0 for all z∈Pz \in P and

vTbˉ=v1Tb+v2⋅α<0. v^T \bar{ b } = v_1^T b + v_2 \cdot \alpha < 0.

We will prove that

v1TA+v2⋅cT≥0. v_1^T A + v_2 \cdot c^T \ge 0.

If we can further prove that v2<0v_2 < 0, then y=1v2⋅v1y = \frac{1}{v_2} \cdot v_1 satisfies yTA≥cTy^T A \ge c^T and yTb<αy^T b < \alpha, which leads to a contradiction.

Lemma: vTz≥0v^T z \ge 0 ∀z∈P\forall z \in P then v1TA+v2⋅cT≥0v_1^T A + v_2 \cdot c^T \ge 0.

Proof. For all x≥0x \ge 0, it holds that (Ax,cTx)∈P(Ax, c^T x) \in P. Hence, v1TAx+v2⋅cTx≥0v_1^T A x + v_2 \cdot c^T x \ge 0, which implies that

v1TA+v2⋅cT≥0. v_1^T A + v_2 \cdot c^T \ge 0.

□\square

Finally, we prove that v2<0v_2 < 0. To see this, observe that (0,−1)∈P(0, -1) \in P, since 0=A00 = A 0, and −1≤cT0-1 \le c^T 0. Now vT(0,−1)=−v2>0v^T (0, -1) = -v_2 > 0.

■\blacksquare

Proof 2. We can convert the primal into an equivalent one:

Ax=b ,cTx−z=α ,x,z≥0 . \begin{array}{r} Ax & = b \,, \\ c^T x - z &= \alpha \,, \\ x,z & \ge 0 \,. \end{array}

or in matrix form:

Aˉxˉ=bˉ ,xˉ≥0 . \begin{array}{r} \bar A \bar x &= \bar b \,,\\ \bar x & \ge 0 \,. \end{array}

where

Aˉ=[A,0cT,−1], xˉ=[xz], bˉ=[bα]. \begin{array}{r} \bar A = \begin{bmatrix} A, & 0 \\ c^T, & -1 \end{bmatrix} ,\, \bar x = \begin{bmatrix} x \\ z \end{bmatrix} , \, \bar b = \begin{bmatrix} b \\ \alpha \end{bmatrix} . \end{array}

No feasible solution implies that bˉ\bar b lies outside the conic combination of columns of Aˉ\bar A. Let zˉ∈Rm×R\bar{ z } \in \mathbb{R}^m \times \mathbb{R} be the projection of bˉ\bar{ b } to the cone formed by columns of Aˉ\bar A and let v=zˉ−bˉ=(v1,v2)∈Rm×Rv = \bar{ z} - \bar{ b } = (v_1, v_2) \in \mathbb{R}^m \times \mathbb{R}. It holds that vTAˉ≥0v^T \bar A \ge 0. Then

vT[AcT]=v1TA+v2⋅cT≥0 ,vT[0−1]=−v2≥0. \begin{array}{l} v^T \begin{bmatrix} A \\ c^T \end{bmatrix} = v_1^T A + v_2 \cdot c^T \ge 0 \,, \\ v^T \begin{bmatrix} 0 \\ -1 \end{bmatrix} = - v_2 \ge 0. \end{array}

It is left to verify that v2<0v_2 < 0. Note that

vTv=vT(zˉ−bˉ)=−vTbˉ=−v1Tb−v2⋅α>0. v^T v = v^T (\bar{ z } - \bar{ b }) = - v^T \bar{ b } = - v_1^T b - v_2 \cdot \alpha > 0.

If v2=0v_2 = 0, then v1TA≥0v_1^T A \ge 0 and v1Tb<0v_1^T b < 0. Replacing yy with v1v_1, and scaling it by positive real number, we can obtain a feasible dual solution such that yTby^T b is arbitrary small. However, this contradicts the weak duality

cTx≤yTb. c^T x \le y^T b.

See the following example in 2 dimensions.

In this example, A[:,1]=(−2,1)A[:, 1] = (-2, 1), A[:,2]=(−1,2)A[:, 2] = (-1, 2), c=(1,1)c = (1, 1), Aˉ[:,1]=(−2,1,1),Aˉ[:,2]=(−1,2,1)\bar A [:, 1] = (-2, 1, 1), \bar A[:, 2] = (-1, 2, 1). {Ax=b,x≥0}\{ Ax = b, x \ge 0 \} is feasible implies that bb is inside the cone spanned by A[:,1],A[:,2]A[:, 1], A[:, 2]. {Aˉxˉ=bˉ,x≥0}\{ \bar A \bar x = \bar b, x \ge 0 \} implies that bˉ=(b,α)\bar b = (b, \alpha) is outside the cone formed by Aˉ[:,1],Aˉ[:,2],[0,0,−1]\bar A[:, 1], \bar A[:, 2], [0, 0, -1]. The zz-dimension of vector yy must be negative.