全部笔记的汇总贴（视频也有传送门）：中科大-凸优化

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对偶（二）