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

一、敏感性分析

性質1：若原問題為凸問題，則 P ? ( u , w ) P^*(u,w) P?(u,w)為 ( u , w ) (u,w) (u,w)的凸函式，

證明： P ? ( u , w ) = inf ? x { f 0 ( x ) ∣ f i ( x ) ≤ u i , i = 1 , ? ? , m , h i ( x ) = w i , i = 1 , ? ? , P ( D ) } = inf ? x g ( x , u , w ) g ( x , u , w ) = Δ f 0 ( x ) , d o m ?? g = d o m ?? f 0 ∩ D ( 凸 集 f i ( x ) ? u i ≤ 0 ?? h i ( x ) ? w i = 0 ) g ( x , u , w ) 為 ( x , u , w ) 的 凸 函 數 f ( x , y ) 對 x 是 凸 的 ， 則 sup ? y ∈ D f ( x , y ) 對 ( x , y ) 是 凸 的 P^*(u,w)=\inf_x\{f_0(x)|f_i(x)\le u_i,i=1,\cdots,m,{\color{blue}h_i(x)=w_i,i=1,\cdots,P(D)}\}\\=\inf_x g(x,u,w)\\g(x,u,w)\overset{\Delta}{=}f_0(x),{\color{blue}dom\;g=dom\;f_0\cap D(凸集f_i(x)-u_i\le0\;h_i(x)-w_i=0)}\\g(x,u,w)為(x,u,w)的凸函式\\f(x,y)對x是凸的，則\sup_{y\in D}f(x,y)對(x,y)是凸的 P?(u,w)=xinf?{f0?(x)∣fi?(x)≤ui?,i=1,?,m,hi?(x)=wi?,i=1,?,P(D)}=xinf?g(x,u,w)g(x,u,w)=Δf0?(x),domg=domf0?∩D(凸集fi?(x)?ui?≤0hi?(x)?wi?=0)g(x,u,w)為(x,u,w)的凸函數f(x,y)對x是凸的，則y∈Dsup?f(x,y)對(x,y)是凸的

性質2：若原問題為凸，對偶間隙為零， λ ? , v ? \lambda^*,v^* λ?,v?為原問題對偶問題對偶最優解， P ? ( u , w ) ≥ P ? ( 0 , 0 ) ? ( λ ? ) T u ? ( v ? ) T w P^*(u,w)\ge P^*(0,0)-(\lambda^*)^Tu-(v^*)^Tw P?(u,w)≥P?(0,0)?(λ?)Tu?(v?)Tw

證明： 設 x ~ 為 干 擾 問 題 的 最 優 解 f i ( x ~ ) ≤ u i , i = 1 , ? ? , m , h i ( x ~ ) = w i , i = 1 , ? ? , P P ? ( 0 , 0 ) = g ? ( λ ? , v ? ) ≤ f 0 ( x ~ ) + ∑ i = 1 m λ i ? f i ( x ~ ) + ∑ i = 1 P v i ? h i ( x ~ ) ≤ f 0 ( x ~ ) + ( λ ? ) T u + ( v ? ) T w = P ? ( u , w ) + ( λ ? ) T u + ( v ? ) T w 設\widetilde x為干擾問題的最優解\\f_i(\widetilde x)\le u_i,i=1,\cdots,m,h_i(\widetilde x)=w_i,i=1,\cdots,P\\P^*(0,0)=g^*(\lambda^*,v^*)\\\le f_0(\widetilde x)+\sum_{i=1}^m\lambda^*_if_i(\widetilde x)+\sum_{i=1}^Pv_i^*h_i(\widetilde x)\\\le f_0(\widetilde x)+(\lambda^*)^Tu+(v^*)^Tw\\=P^*(u,w)+(\lambda^*)^Tu+(v^*)^Tw 設x 為干擾問題的最優解fi?(x )≤ui?,i=1,?,m,hi?(x )=wi?,i=1,?,PP?(0,0)=g?(λ?,v?)≤f0?(x )+i=1∑m?λi??fi?(x )+i=1∑P?vi??hi?(x )≤f0?(x )+(λ?)Tu+(v?)Tw=P?(u,w)+(λ?)Tu+(v?)Tw

1. 若 λ i ? \lambda^*_i λi??很大，且加緊第 i i i項不等式約束 u i < 0 u_i<0 ui?<0，則 P ? ( u , w ) P^*(u,w) P?(u,w)急劇增加；
2. 若 v i ? v^*_i vi??很大正值，使 w i < 0 w_i<0 wi?<0，或 v i ? v^*_i vi??絕對值很大負值，使 w i > 0 w_i>0 wi?>0，則 P ? ( u , w ) P^*(u,w) P?(u,w)急劇增加；
3. 若 λ i ? \lambda^*_i λi??很小，且 u i > 0 u_i>0 ui?>0，則 P ? ( u , w ) P^*(u,w) P?(u,w)下降不大；
4. 若 v i ? v^*_i vi??很小正值，使 w i > 0 w_i>0 wi?>0，或 v i ? v^*_i vi??絕對值很小負值，使 w i < 0 w_i<0 wi?<0，則 P ? ( u , w ) P^*(u,w) P?(u,w)下降不大，

性質3：（區域敏感性）若原問題為凸，對偶間隙為零，且 P ? ( u , w ) P^*(u,w) P?(u,w)在 ( u , w ) = ( 0 , 0 ) (u,w)=(0,0) (u,w)=(0,0)處可微， λ i ? = ? ? P ? ( 0 , 0 ) ? u i , ?????? v i ? = ? ? P ? ( 0 , 0 ) ? w i P ? ( u , w ) = P ? ( 0 , 0 ) ? ( λ ? ) T u ? ( v ? ) T w \lambda^*_i=-\frac{\partial P^*(0,0)}{\partial u_i},\;\;\;v^*_i=-\frac{\partial P^*(0,0)}{\partial w_i}\\P^*(u,w)=P^*(0,0)-(\lambda^*)^Tu-(v^*)^Tw λi??=??ui??P?(0,0)?,vi??=??wi??P?(0,0)?P?(u,w)=P?(0,0)?(λ?)Tu?(v?)Tw

下一章傳送門：中科大-凸優化 筆記（lec40）-松弛對偶