中科大-凸優化 筆記（lec29）-Lagrange對偶（一）

全部筆記的匯總貼（視頻也有傳送門）：中科大-凸優化

min ? f 0 ( x ) s . t . ?? f i ( x ) ≤ 0 , i = 1 , ? ? , m h i ( x ) = 0 , i = 1 , ? ? , P x ∈ R n , D = ∩ i = 0 m d o m ?? f i ∩ ∩ i = 1 P d o m ?? h i P ? ?? o p t i m a l ?? c a l u e \min f_0(x)\\s.t.\;f_i(x)\le0,i=1,\cdots,m\\h_i(x)=0,i=1,\cdots,P\\x\in\R^n,D=\cap_{i=0}^m dom\;f_i\cap\cap_{i=1}^P dom\;h_i\\P^*\;optimal\;calue minf0?(x)s.t.fi?(x)≤0,i=1,?,mhi?(x)=0,i=1,?,Px∈Rn,D=∩i=0m?domfi?∩∩i=1P?domhi?P?optimalcalue

拉格朗日函式（Lagrangian function/Lagrangian）

L ( x , λ , v ) = f 0 ( x ) + ∑ i = 1 m λ i f i ( x ) + ∑ i = 1 P v i h i ( x ) L(x,\lambda,v)=f_0(x)+\sum_{i=1}^m \lambda_if_i(x)+\sum_{i=1}^P v_ih_i(x) L(x,λ,v)=f0?(x)+i=1∑m?λi?fi?(x)+i=1∑P?vi?hi?(x)

對偶函式（Lagrange Dual Function/Dual Function）

g ( λ , v ) = inf ? x ∈ D L ( x , λ , v ) g(\lambda,v)=\inf_{x\in D}L(x,\lambda,v) g(λ,v)=x∈Dinf?L(x,λ,v)

Lagrange Multiplier/Multipler

性質：

1. 對偶函式為凹函式
   sup ? x ∈ D L ( x , λ , v ) 凸 → inf ? x ∈ D L ( x , λ , v ) 凹 \sup_{x\in D}L(x,\lambda,v)凸\rightarrow\inf_{x\in D}L(x,\lambda,v)凹 x∈Dsup?L(x,λ,v)凸→x∈Dinf?L(x,λ,v)凹
2. ? λ ≥ 0 , ? v , g ( λ , v ) ≤ P ? \forall \lambda\ge0,\forall v,g(\lambda,v)\le P^* ?λ≥0,?v,g(λ,v)≤P?

證明：設 x ? x^* x?是原問題的最優解，則必可行，
則 f i ( x ? ) ≤ 0 , h i ( x ? ) = 0 f_i(x^*)\le0,h_i(x^*)=0 fi?(x?)≤0,hi?(x?)=0
當 ? λ ≥ 0 , ? v \forall \lambda\ge0,\forall v ?λ≥0,?v，有 ∑ i = 1 m λ i f i ( x ? ) + ∑ i = 1 P v i h i ( x ? ) ≤ 0 \sum_{i=1}^m\lambda_if_i(x^*)+\sum_{i=1}^Pv_ih_i(x^*)\le0 ∑i=1m?λi?fi?(x?)+∑i=1P?vi?hi?(x?)≤0
L ( x ? , λ , v ) = f 0 ( x ? ) ∑ i = 1 m λ i f i ( x ? ) + ∑ i = 1 P v i h i ( x ? ) ≤ P ? g ( λ , v ) ≤ P ? L(x^*,\lambda,v)=f_0(x^*)\sum_{i=1}^m\lambda_if_i(x^*)+\sum_{i=1}^Pv_ih_i(x^*)\le P^*\\g(\lambda,v)\le P^* L(x?,λ,v)=f0?(x?)i=1∑m?λi?fi?(x?)+i=1∑P?vi?hi?(x?)≤P?g(λ,v)≤P?

例：

min ? X T X s . t . ?? A x = b , x ∈ R n , b ∈ R P , A ∈ R P ? n ? L ( x , v ) = X T X + V T ( A x ? b ) ? g ( v ) = inf ? x ∈ D L ( x , v ) = inf ? x ∈ D X T X + V T A x ? V T b 對 x 偏 導 ???? 2 x + A T V = 0 , x = ? A T y 2 代 回 去 求 最 優 值 1 4 ( V T A A T V ) ? 1 2 ( V T A A T V ) ? V T b = ? 1 4 V T A A T V ? b T V ?????? 凹 （ 其 中 A A T 半 正 定 ） \min X^TX\\s.t.\;Ax=b,x\in\R^n,b\in\R^P,A\in\R^{P*n}\\\Rightarrow L(x,v)=X^TX+V^T(Ax-b)\\\Rightarrow g(v)=\inf_{x\in D}L(x,v)=\inf_{x\in D}X^TX+V^TAx-V^Tb\\對x偏導\;\;2x+A^TV=0,x=-\frac{A^Ty}2代回去求最優值\\\frac14(V^TAA^TV)-\frac12(V^TAA^TV)-V^Tb=-\frac14V^TAA^TV-b^TV\;\;\;凹（其中AA^T半正定） minXTXs.t.Ax=b,x∈Rn,b∈RP,A∈RP?n?L(x,v)=XTX+VT(Ax?b)?g(v)=x∈Dinf?L(x,v)=x∈Dinf?XTX+VTAx?VTb對x偏導2x+ATV=0,x=?2ATy?代回去求最優值41?(VTAATV)?21?(VTAATV)?VTb=?41?VTAATV?bTV凹（其中AAT半正定）

例：

min ? C T x s . t . ?? A x ≥ b ?? x ≥ 0 （ A x ? b = 0 ???? ? x ≤ 0 ） ? L ( x , λ , v ) = C T x ? λ T x + V T ( A x ? b ) = ? b T V + ( C + A T V ? λ ) x ? g ( λ , v ) = inf ? x ∈ D L ( x , λ , v ) = { ? b t V ???? C T + A T V ? λ = 0 + ∞ ?????? o t h e r w i s e \min C^Tx\\s.t.\;Ax\ge b\;x\ge0\\（Ax-b=0\;\;-x\le0）\\\Rightarrow L(x,\lambda,v)=C^Tx-\lambda^Tx+V^T(Ax-b)\\=-b^TV+(C+A^TV-\lambda)x\\\Rightarrow g(\lambda,v)=\inf_{x\in D}L(x,\lambda,v)=\left\{ \begin{array}{l} -b^tV\;\;C^T+A^TV-\lambda=0 \\ \\+\infty\;\;\;otherwise \end{array} \right. minCTxs.t.Ax≥bx≥0（Ax?b=0?x≤0）?L(x,λ,v)=CTx?λTx+VT(Ax?b)=?bTV+(C+ATV?λ)x?g(λ,v)=x∈Dinf?L(x,λ,v)=?????btVCT+ATV?λ=0+∞otherwise?

例：

min ? X T W X s . t . ?? X i = ± 1 , i = 1 , ? ? , m X i 2 ? 1 = 0 （ 二 次 約 束 ） ? L ( x , λ ) = X T W X + ∑ i = 1 m v i ( x i 2 ? 1 ) = X T ( W + d i a g { v } ) x ? 1 T v ? g ( v ) = inf ? x ∈ D X T ( W + d i a g { v } ) X ? 1 T v = { ? 1 T v ?????? W + d i a g { v } ? 0 ? ∞ ?????? o t h e r w i s e \min X^TWX\\s.t.\;X_i=\pm 1,i=1,\cdots,m\\X_i^2-1=0（二次約束）\\\Rightarrow L(x,\lambda)=X^TWX+\sum_{i=1}^mv_i(x_i^2-1)\\=X^T(W+diag\{v\})x-1^Tv\\\Rightarrow g(v)=\inf_{x\in D}X^T(W+diag\{v\})X-1^Tv=\left\{ \begin{array}{l} -1^Tv\;\;\;W+diag\{v\}\succeq0 \\ \\-\infty\;\;\;otherwise \end{array} \right. minXTWXs.t.Xi?=±1,i=1,?,mXi2??1=0（二次約束）?L(x,λ)=XTWX+i=1∑m?vi?(xi2??1)=XT(W+diag{v})x?1Tv?g(v)=x∈Dinf?XT(W+diag{v})X?1Tv=?????1TvW+diag{v}?0?∞otherwise?

下一章傳送門：中科大-凸優化 筆記（lec30）-Lagrange對偶（二）