UA SIE545 优化理论基础1 例题2 Farkas定理与相关结论
UA SIE545 優化理論基礎1 例題2 Farkas定理與相關結論
- Farkas定理的證明方法
- Gordan定理
Farkas定理是分離定理的直接結果:
Farkas定理 AAA是一個m×nm\times nm×n的矩陣,下面兩個系統有且僅有一個有解:
I:Ax≤0,cTx>0II:ATy=c,y≥0I:Ax \le 0,c^Tx>0 \\ II:A^Ty=c,y \ge 0I:Ax≤0,cTx>0II:ATy=c,y≥0
Farkas定理的證明方法
Farkas定理及其類似結論有三種證明方法:反證法、分離定理法、線性規劃法;如果是Farkas定理的推論,還可以將系統改寫成能使用Farkas定理的形式,直接用Farkas定理證明。反證法的思路非常簡單,假設系統II有解,推系統I無解;假設系統II無解,推系統I有解,在推有解的時候,經常需要用分離定理來構造系統的解。下面列出經常用到的分離定理的結論:
定理二 (點與閉凸集的分離) 假設S?VS \subset VS?V是非空閉凸集,y?Sy \notin Sy∈/?S,?p,α\exists p,\alpha?p,α,?x∈S\forall x \in S?x∈S, pTy>α,pTx≤α,?x∈Sp^Ty >\alpha,p^Tx \le \alpha,\forall x \in SpTy>α,pTx≤α,?x∈S
定理三 (凸集的支撐)S?VS \subset VS?V是非空凸集,x0∈?Sx_0 \in \partial Sx0?∈?S, ?p\exists p?p, pT(x?x0)≤0,?x∈clSp^T(x-x_0) \le 0,\forall x \in clSpT(x?x0?)≤0,?x∈clS
定理四 (凸集的分離)S1,S2?VS_1,S_2\subset VS1?,S2??V是兩個無交凸集,?p∈V\exists p \in V?p∈V, inf?{pTx:x∈S1}≥sup?{pTx:x∈S2}\inf\{p^Tx:x \in S_1\} \ge \sup\{p^Tx:x \in S_2\}inf{pTx:x∈S1?}≥sup{pTx:x∈S2?}
定理五 (凸集的強分離)S1,S2?VS_1,S_2\subset VS1?,S2??V是兩個無交閉凸集,?p∈V,?>0\exists p \in V,\epsilon>0?p∈V,?>0, inf?{pTx:x∈S1}≥sup?{pTx:x∈S2}+?\inf\{p^Tx:x \in S_1\} \ge \sup\{p^Tx:x \in S_2\}+\epsiloninf{pTx:x∈S1?}≥sup{pTx:x∈S2?}+?
反證法證明Farkas定理,假設系統II無解,推系統I有解時,定義S={x:x=ATy,y≥0}S = \{x:x = A^Ty,y\ge 0\}S={x:x=ATy,y≥0},SSS是一個閉凸集,系統II無解說明c?Sc \notin Sc∈/?S,我們觀察系統1,它陳述的是用AAA定義的某個多面體與點ccc的分離,而這個多面體肯定包含SSS的,c?Sc \notin Sc∈/?S提供了ccc與SSS分離的條件,因此證明思路是對ccc和SSS用點與凸集的分離構造系統I的解。
分離定理證明Farkas定理,基本框架依然用反證法,但使用凸集的分離導出矛盾。但需要注意的是對于一般性的ATy=cA^Ty=cATy=c的問題,這個方法其實是給不出正確完整的證明的,這里提出來是因為對于ATy=0A^Ty=0ATy=0的問題,這種方法的效果是不錯的。假設系統I有解,如果?y≥0\exists y \ge 0?y≥0, ATy=cA^T y = cATy=c,則
xTATy=(Ax)Ty≤0x^TA^Ty = (Ax)^Ty\le 0xTATy=(Ax)Ty≤0
但根據假設xTATy=xTc>0x^TA^Ty = x^Tc>0xTATy=xTc>0,這就導出了矛盾,因此系統I有解時,系統II無解。
假設系統I無解,定義下面兩個非空凸集:
S1={z:Ax≤z,cTx>0},S2={z:z≤0}S_1 =\{z:Ax \le z,c^Tx> 0\},\ S_2 = \{z:z \le 0\}S1?={z:Ax≤z,cTx>0},?S2?={z:z≤0}
系統I無解說明S1∩S2=?S_1\cap S_2 = \phiS1?∩S2?=?,根據凸集的分離,?p\exists p?p, inf?{pTz:z∈S2}≥sup?{pTz:z∈S1}\inf\{p^Tz:z\in S_2\} \ge \sup\{p^Tz:z \in S_1\}inf{pTz:z∈S2?}≥sup{pTz:z∈S1?},這意味著?z∈S2,?x\forall z \in S_2,\forall x?z∈S2?,?x,
pTz≥pTAxp^Tz \ge p^TAxpTz≥pTAx
因為zzz可以是任意負值,為了保證這個不等式對任意z,xz,xz,x成立,p≥0p \ge 0p≥0。取z=0,x=ATpz=0,x = A^Tpz=0,x=ATp, 則∥ATp∥≤0\left\| A^Tp \right\| \le 0∥∥?ATp∥∥?≤0,因此ATp=0A^Tp=0ATp=0。但我們需要的是ATp=cA^Tp=cATp=c,因此這種方法其實是完不成證明的,下面我們會看到如果是Gordan定理的條件,這種操作就是可以用的。
線性規劃證明Farkas定理,基礎是線性規劃的對偶性理論:
P:min?cTxs.t.Ax=b,x≥0D:max?bTys.t.ATy≤cP:\min c^Tx \ s.t. Ax = b,x \ge 0 \\ D:\max b^Ty\ s.t. A^Ty \le c P:mincTx?s.t.Ax=b,x≥0D:maxbTy?s.t.ATy≤c
用對偶性理論證明Farkas定理最關鍵的是在Farkas的兩個系統基礎上寫出兩個線性規劃問題。記
P:min?0Tys.t.ATy=c,y≥0D:max?cTxs.t.Ax≤0P:\min 0^Ty \ s.t. A^Ty = c,y \ge 0 \\ D:\max c^Tx\ s.t. Ax \le 0 P:min0Ty?s.t.ATy=c,y≥0D:maxcTx?s.t.Ax≤0
注意到PPP不可行意味著系統II無解,因為DDD是可行的,根據Unbounded-infeasible,PPP不可行等價于系統II無解等價于DDD無界,其充要條件是?x\exists x?x, Ax≤0Ax \le 0Ax≤0, cTx>0c^Tx>0cTx>0,也就是系統I有解,因此系統I與系統II只能有一個有解。
Gordan定理
Gordan定理(Farkas定理的推論):AAA是一個m×nm\times nm×n的矩陣,下面兩個系統有且僅有一個有解:
I:Ax<0II:ATy=0,y≥0,y≠0I:Ax < 0 \\ II:A^Ty=0,y \ge 0, y \ne 0I:Ax<0II:ATy=0,y≥0,y?=0
我們用Farkas定理的這個推論演示一下這幾種證明思路:
證明方法1:Farkas定理
改寫系統I:
Ax<0?Ax+1ms=[A1m][xs]≤0,s>0Ax < 0 \Leftrightarrow Ax + 1_m s = \left[ \begin{matrix} A & 1_m \end{matrix} \right] \left[ \begin{matrix} x \\ s \end{matrix} \right] \le 0,s>0Ax<0?Ax+1m?s=[A?1m??][xs?]≤0,s>0
定義c=[0,0,?,1]∈Rn+1c = [0,0,\cdots,1] \in \mathbb{R}^{n+1}c=[0,0,?,1]∈Rn+1,則
cT[xs]>0c^T\left[ \begin{matrix} x \\ s \end{matrix} \right]>0cT[xs?]>0
改寫系統用現成的定理非常方便,需要注意的是改寫后兩個系統的有解性要與改寫前相同,改寫的邏輯是Tightening不等式靠松弛變量。
證明方法2:反證法
假設系統II有解,如果存在xxx使得Ax<0Ax < 0Ax<0,則
xTATy=(Ax)Ty<0,?y≥0,y≠0x^TA^Ty = (Ax)^Ty < 0,\forall y \ge 0,y \ne 0xTATy=(Ax)Ty<0,?y≥0,y?=0
但是xTATy=xT(ATy)=0x^TA^Ty = x^T(A^Ty)=0xTATy=xT(ATy)=0,這就出現了矛盾,因此系統II有解時,系統II無解。
假設系統II無解,定義S={x:x=ATy,y≥0,y≠0}S = \{x:x = A^Ty,y \ge 0, y\ne 0\}S={x:x=ATy,y≥0,y?=0},則0?S0 \notin S0∈/?S。注意到SSS是一個閉凸集,根據定理二,?p\exists p?p滿足?x∈S\forall x \in S?x∈S, pTx≤0p^Tx \le 0pTx≤0,?y∈S\exists y \in S?y∈S, pTATy≤0p^TA^Ty \le 0pTATy≤0,因為y≥0,y≠0y \ge 0,y \ne 0y≥0,y?=0,所以Ap≤0Ap \le 0Ap≤0,這說明系統I有解。
證明方法3:分離定理
現在用兩個凸集的分離來證明,但基本框架依然是反證法的框架,為了與方法2有所區別,我們先假設系統I有解,再假設系統II無解。
假設系統I有解,如果?y≥0,y≠0\exists y \ge 0,y \ne 0?y≥0,y?=0, ATy=0A^Ty=0ATy=0,則
xTATy=(Ax)Ty<0,?y≥0,y≠0x^TA^Ty = (Ax)^Ty < 0,\forall y \ge 0,y \ne 0xTATy=(Ax)Ty<0,?y≥0,y?=0
但是xTATy=xT(ATy)=0x^TA^Ty = x^T(A^Ty)=0xTATy=xT(ATy)=0,這就出現了矛盾。
假設系統I無解,定義
S1={z:z=Ax},S2={z:z<0}S_1 = \{z:z = Ax\}, S_2 = \{z:z < 0\}S1?={z:z=Ax},S2?={z:z<0}
系統I無解說明S1∩S2=?S_1 \cap S_2 = \phiS1?∩S2?=?,因為S1,S2S_1,S_2S1?,S2?是非空凸集,根據凸集的分離,?p\exists p?p 滿足inf?{pTz:z∈S1}≥sup?{pTz:z∈S2}\inf\{p^Tz:z \in S_1\} \ge \sup\{p^Tz:z \in S_2\}inf{pTz:z∈S1?}≥sup{pTz:z∈S2?},?x,?z∈clS2\forall x,\forall z \in cl S_2?x,?z∈clS2?,
pTAx≥pTzp^TAx \ge p^TzpTAx≥pTz
因為zzz可以任意大,如果ppp不大于0,上式可能不成立;因此p≥0p \ge 0p≥0。另外,如果取z=0z=0z=0,可以發現pTAx≥0p^TAx \ge 0pTAx≥0,取x=?ATpx = -A^Tpx=?ATp,則?∥ATp∥≥0-\left\| A^Tp\right\| \ge 0?∥∥?ATp∥∥?≥0,顯然ATp=0A^Tp = 0ATp=0,因此系統II有解。
總結
以上是生活随笔為你收集整理的UA SIE545 优化理论基础1 例题2 Farkas定理与相关结论的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: UA SIE545 优化理论基础1 凸分
- 下一篇: UA SIE545 优化理论基础1 例题