全部笔记的汇总贴（视频也有传送门）：中科大-凸优化
一、敏感性分析
性质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)}=xinfg(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∈Dsupf(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∑Pvi∗hi(x )≤f0(x )+(λ∗)Tu+(v∗)Tw=P∗(u,w)+(λ∗)Tu+(v∗)Tw
- 若 λ i ∗ \lambda^*_i λi∗很大，且加紧第 i i i项不等式约束 u i < 0 u_i<0 ui<0，则 P ∗ ( u , w ) P^*(u,w) P∗(u,w)急剧增加；
- 若 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)急剧增加；
- 若 λ i ∗ \lambda^*_i λi∗很小，且 u i > 0 u_i>0 ui>0，则 P ∗ ( u , w ) P^*(u,w) P∗(u,w)下降不大；
- 若 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）-松弛对偶
