UA SIE545 優化理論基礎1 例題2 Farkas定理與相關結論

• • Farkas定理的證明方法
  • Gordan定理

Farkas定理是分離定理的直接結果：
Farkas定理 $A$是一個$m\times n$的矩陣，下面兩個系統有且僅有一個有解：
$$\begin{gathered} I:Ax\le 0,c^{T}x>0 \\ II:A^{T}y=c,y\ge 0 \end{gathered}$$

Farkas定理的證明方法

Farkas定理及其類似結論有三種證明方法：反證法、分離定理法、線性規劃法；如果是Farkas定理的推論，還可以將系統改寫成能使用Farkas定理的形式，直接用Farkas定理證明。反證法的思路非常簡單，假設系統II有解，推系統I無解；假設系統II無解，推系統I有解，在推有解的時候，經常需要用分離定理來構造系統的解。下面列出經常用到的分離定理的結論：
定理二 (點與閉凸集的分離) 假設$S?V$是非空閉凸集，$y\in /S$，$?p,\alpha$，$?x\in S$, $p^{T}y>\alpha ,p^{T}x\le \alpha ,?x\in S$
定理三 (凸集的支撐)$S?V$是非空凸集，$x_0\in ?S$, $?p$, $p^T(x?x_0)\le 0,?x\in clS$
定理四 （凸集的分離）$S_1,S_2?V$是兩個無交凸集，$?p\in V$, $\inf \{p^{T}x:x\in S_1\}\ge \sup \{p^{T}x:x\in S_2\}$
定理五 （凸集的強分離）$S_1,S_2?V$是兩個無交閉凸集，$?p\in V,?>0$, $\inf \{p^{T}x:x\in S_1\}\ge \sup \{p^{T}x:x\in S_2\}+?$

反證法證明Farkas定理，假設系統II無解，推系統I有解時，定義$S=\{x:x=A^{T}y,y\ge 0\}$，$S$是一個閉凸集，系統II無解說明$c\in /S$，我們觀察系統1，它陳述的是用$A$定義的某個多面體與點$c$的分離，而這個多面體肯定包含$S$的，$c\in /S$提供了$c$與$S$分離的條件，因此證明思路是對$c$和$S$用點與凸集的分離構造系統I的解。

分離定理證明Farkas定理，基本框架依然用反證法，但使用凸集的分離導出矛盾。但需要注意的是對于一般性的$A^{T}y=c$的問題，這個方法其實是給不出正確完整的證明的，這里提出來是因為對于$A^{T}y=0$的問題，這種方法的效果是不錯的。假設系統I有解，如果$?y\ge 0$, $A^{T}y=c$，則
$$x^T{A}^{T}y=(Ax{)}^{T}y\le 0$$

但根據假設$x^T{A}^{T}y=x^{T}c>0$，這就導出了矛盾，因此系統I有解時，系統II無解。

假設系統I無解，定義下面兩個非空凸集：
$$S_1=\{z:Ax\le z,c^{T}x>0\},S_2=\{z:z\le 0\}$$

系統I無解說明$S_1\cap S_2=?$，根據凸集的分離，$?p$, $\inf \{p^{T}z:z\in S_2\}\ge \sup \{p^{T}z:z\in S_1\}$，這意味著$?z\in S_2,?x$,
$$p^{T}z\ge p^{T}Ax$$

因為$z$可以是任意負值，為了保證這個不等式對任意$z,x$成立，$p\ge 0$。取$z=0,x=A^{T}p$, 則$\Vert A^{T}p\Vert \le 0$，因此$A^{T}p=0$。但我們需要的是$A^{T}p=c$，因此這種方法其實是完不成證明的，下面我們會看到如果是Gordan定理的條件，這種操作就是可以用的。

線性規劃證明Farkas定理，基礎是線性規劃的對偶性理論：
$$\begin{gathered} P:\min c^{T}xs.t.Ax=b,x\ge 0 \\ D:\max b^{T}ys.t.A^{T}y\le c \end{gathered}$$

Weak Duality: $P$的解$x$與$D$的解$y$滿足$c^{T}x\ge b^{T}y$

Unbounded-infeasible: $P$無解則$D$不可行

Strong Duality: $P,D$均可行，則它們最優解下的目標函數值相等

用對偶性理論證明Farkas定理最關鍵的是在Farkas的兩個系統基礎上寫出兩個線性規劃問題。記
$$\begin{gathered} P:\min 0^{T}ys.t.A^{T}y=c,y\ge 0 \\ D:\max c^{T}xs.t.Ax\le 0 \end{gathered}$$

注意到$P$不可行意味著系統II無解，因為$D$是可行的，根據Unbounded-infeasible，$P$不可行等價于系統II無解等價于$D$無界，其充要條件是$?x$, $Ax\le 0$, $c^{T}x>0$，也就是系統I有解，因此系統I與系統II只能有一個有解。

Gordan定理

Gordan定理（Farkas定理的推論）：$A$是一個$m\times n$的矩陣，下面兩個系統有且僅有一個有解：
$$\begin{gathered} I:Ax<0 \\ II:A^{T}y=0,y\ge 0,y=0 \end{gathered}$$

我們用Farkas定理的這個推論演示一下這幾種證明思路：

證明方法1：Farkas定理
改寫系統I：
$$Ax<0?Ax+1_{m}s=\left[\begin{array}{cc}A& 1_m\end{array}\right]\left[\begin{array}{c}x\\ s\end{array}\right]\le 0,s>0$$

定義$c=[0,0,?,1]\in {\mathbb{R}}^{n+1}$，則
$$c^T\left[\begin{array}{c}x\\ s\end{array}\right]>0$$

改寫系統用現成的定理非常方便，需要注意的是改寫后兩個系統的有解性要與改寫前相同，改寫的邏輯是Tightening不等式靠松弛變量。

證明方法2：反證法
假設系統II有解，如果存在$x$使得$Ax<0$，則
$$x^T{A}^{T}y=(Ax{)}^{T}y<0,?y\ge 0,y=0$$

但是$x^T{A}^{T}y=x^T(A^{T}y)=0$，這就出現了矛盾，因此系統II有解時，系統II無解。

假設系統II無解，定義$S=\{x:x=A^{T}y,y\ge 0,y=0\}$，則$0\in /S$。注意到$S$是一個閉凸集，根據定理二，$?p$滿足$?x\in S$, $p^{T}x\le 0$，$?y\in S$, $p^T{A}^{T}y\le 0$，因為$y\ge 0,y=0$，所以$Ap\le 0$，這說明系統I有解。

證明方法3：分離定理
現在用兩個凸集的分離來證明，但基本框架依然是反證法的框架，為了與方法2有所區別，我們先假設系統I有解，再假設系統II無解。

假設系統I有解，如果$?y\ge 0,y=0$, $A^{T}y=0$，則
$$x^T{A}^{T}y=(Ax{)}^{T}y<0,?y\ge 0,y=0$$

但是$x^T{A}^{T}y=x^T(A^{T}y)=0$，這就出現了矛盾。

假設系統I無解，定義
$$S_1=\{z:z=Ax\},S_2=\{z:z<0\}$$

系統I無解說明$S_1\cap S_2=?$，因為$S_1,S_2$是非空凸集，根據凸集的分離，$?p$ 滿足$\inf \{p^{T}z:z\in S_1\}\ge \sup \{p^{T}z:z\in S_2\}$，$?x,?z\in cl{S}_2$,
$$p^{T}Ax\ge p^{T}z$$

因為$z$可以任意大，如果$p$不大于0，上式可能不成立；因此$p\ge 0$。另外，如果取$z=0$，可以發現$p^{T}Ax\ge 0$，取$x=?A^{T}p$，則$?\Vert A^{T}p\Vert \ge 0$，顯然$A^{T}p=0$，因此系統II有解。

總結

以上是生活随笔為你收集整理的UA SIE545 优化理论基础1 例题2 Farkas定理与相关结论的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。