[Study Notes] Dual Theorem of Linear Programming

注：Vectors are not necessarily marked in bold,尤其是 $x,y$,Because their bold is so ugly.

Definition. 向量比较 $x<y$ 等价于 $\forall i,x_i<y_i$,That is, a numerical comparison is made on each component.

半空间（$\text{affine halfspaces}$）：形如 $\{x:{\mathbf{a}}^{\mathsf{T}}x⩽b\}$,其中 $x\in {\mathbb{R}}^{\dim \mathbf{a}}$ .

polyhedron（$\text{polyhedra/polyhedron}$）：A limited half-space intersection.它等价于 $P=\{x:\mathcal{A}x⩽\mathbf{b}\}$,其中 $\mathcal{A}$ 是 $m\times n$ 矩阵,$\mathbf{b}\in {\mathbb{R}}^m$ 而 $x\in {\mathbb{R}}^n$ .

多胞体（$\text{polytope}$）：The convex hull generated by a finite number of vectors.Equivalent to finite size $\mathrm{polyhedron}$ .

Comment. I'm not sure what the Chinese translations of the above things should be.

Proposition. 若 $x\notin P$ 其中 $P$ 是 $\mathrm{polyhedra}$,There is a half space $C$ 使得 $P\subseteq C$ 且 $x\notin C$ .

The proof of the theorem is difficult to separate from the support of geometry：需要找到 $y\in P$ 使得 $\Vert x-y\Vert$ 最小,而 $y$ The existence of is guaranteed by its geometrically intuitive properties.But if you admit the use of geometry in it,Then the theorem is obvious.Therefore, no proof is given here.

Lemma.（$\text{Farkas’ lemma}$） $\mathcal{A}x=\mathbf{b}$ 有 $x⩾0$ 的解,当且仅当 ${\mathcal{A}}^{\mathsf{T}}y⩾0\wedge {\mathbf{b}}^{\mathsf{T}}y<0$ 无 $y\in {\mathbb{R}}^n$ 的解.

Proof. 当 $\mathcal{A}x=\mathbf{b}$ 有解时,Counter-evidence $y$ 有解,则
$$0>{\mathbf{b}}^{\mathsf{T}}y=(\mathcal{A}x{)}^{\mathsf{T}}\cdot y=x^{\mathsf{T}}({\mathcal{A}}^{\mathsf{T}}y)⩾0$$

当 $\mathcal{A}x=\mathbf{b}$ 无解时,设 $a_1,a_2,\dots ,a_n$ 为 $\mathcal{A}$ 的列向量,令 $C$ for their convex hull,则 $x$ Unsolved is equivalent to $\mathbf{b}\notin C$,So there is a half plane division $\mathbf{b}$ 和 $C$,That is, there is a vector $y$ 使得 ${\mathbf{b}}^{\mathsf{T}}y<0$ 且 $x^{\mathsf{T}}y⩾0(x\in C)$,The latter contains ${\mathcal{A}}^{\mathsf{T}}y⩾0$ .$■$

Corollary. 设 $P=\{x:\mathcal{A}x⩽\mathbf{b}\}\ne \varnothing$,则 $\forall x\in P,{\mathbf{c}}^{\mathsf{T}}x⩽\delta$ 等价于 $\exists y⩾0,{\mathcal{A}}^{\mathsf{T}}y=c\wedge {\mathbf{b}}^{\mathsf{T}}y⩽\delta$ .

Proof. 充分性：若 $y$ 存在,there is immediately
$$\mathcal{A}x⩽\mathbf{b}*y^{\mathsf{T}}\mathcal{A}x⩽y^{\mathsf{T}}\mathbf{b}*{\mathbf{c}}^{\mathsf{T}}x⩽y^{\mathsf{T}}\mathbf{b}*{\mathbf{c}}^{\mathsf{T}}x⩽\delta$$

必要性：It's essentially solving equations
$$\left(\begin{array}{cc}{y}^{\mathsf{T}}& \lambda \end{array}\right)\left(\begin{array}{cc}A& b\\ 0& 1\end{array}\right)=\left(\begin{array}{cc}{\mathbf{c}}^{\mathsf{T}}& \delta \end{array}\right)$$

的 $y^{\mathsf{T}},\lambda ⩾0$ 的解.由 $\text{Farkas’ lemma}$ 可知存在 $z,\mu \in \mathbb{R}$ 使得
$$\left(\begin{array}{cc}A& b\\ 0& 1\end{array}\right)\left(\begin{array}{c}z\\ \mu \end{array}\right)⩾0\text{and}\left(\begin{array}{cc}{\mathbf{c}}^{\mathsf{T}}& \delta \end{array}\right)\left(\begin{array}{c}z\\ \mu \end{array}\right)<0$$

Known by the former $\mu ⩾0$ .讨论 $\mu =0$ 和 $\mu >0$ 的情况,分别取 $x=x_0-\gamma z(\gamma \to +\infty )$ 和 $x=-{\mu }^{-1}z$ Contradictions can be drawn,完成证明.Leave it as an exercise.$■$

Theorem.（$\text{Duality theorem of linear programming}$） 令 $\mathcal{A}$ 为 $m\times n$ 矩阵,$\mathbf{b}\in {\mathbb{R}}^m,\mathbf{c}\in {\mathbb{R}}^n$,则
$$\max \{{\mathbf{c}}^{\mathsf{T}}x:\mathcal{A}x⩽\mathbf{b}\}=\min \{y^{\mathsf{T}}\mathbf{b}:y⩾0\wedge {\mathcal{A}}^{\mathsf{T}}y=\mathbf{c}\}$$

Proof. Let the left form be $\delta$,根据 $\text{Corollary}$ 立刻有 $\exists y⩾0$ 使得 ${\mathcal{A}}^{\mathsf{T}}y=\mathbf{c}\wedge {\mathbf{b}}^{\mathsf{T}}y⩽\delta$ .This shows that the right-hand form is at most $\delta$ .

The left does not exceed the right,因为 ${\mathbf{c}}^{\mathsf{T}}x=(y^{\mathsf{T}}\mathcal{A})⩽y^{\mathsf{T}}\mathbf{b}$ .$■$

In the usual linear programming duality $x⩾0$,If unified to $\mathcal{A}x⩽\mathbf{b}$ 中,不难发现有
$$\max \{{\mathbf{c}}^{\mathsf{T}}x:x⩾0\wedge \mathcal{A}x⩽\mathbf{b}\}=\min \{{\mathbf{b}}^{\mathsf{T}}y:y⩾0\wedge {\mathcal{A}}^{\mathsf{T}}y⩾\mathbf{c}\}$$

This is a special form of the duality theorem,It is also the usual duality.$\text{crashed}$ 指出：The mutual relaxation theorem is obvious.Therefore omitted.