中科大凸优化笔记（lec51）增广拉格朗日法

全部笔记的汇总贴&＃xff08;视频也有传送门&＃xff09;&＃xff1a;中科大-凸优化

αk&＃61;arg min⁡α≥0f(xk&＃43;αdk)xk&＃43;1&＃61;xk&＃43;αkdk\alpha^k &＃61; \argmin_{\alpha\ge0}f(x^k&＃43;\alpha d^k)\\x^{k&＃43;1}&＃61;x^k&＃43;\alpha^kd^kαk&＃61;α≥0argmin​f(xk&＃43;αdk)xk&＃43;1&＃61;xk&＃43;αkdk

xk&＃43;1&＃61;xk−αk(∇f(xk)&＃43;ATvk)vk&＃43;1&＃61;vk&＃43;αk(Axk−b)x^{k&＃43;1}&＃61;x^k-\alpha^k(\nabla f(x^k)&＃43;A^Tv^k)\\v^{k&＃43;1}&＃61;v^k&＃43;\alpha^k(Ax^k-b)xk&＃43;1&＃61;xk−αk(∇f(xk)&＃43;ATvk)vk&＃43;1&＃61;vk&＃43;αk(Axk−b)

Lc(x,v)&＃61;f(x)&＃43;vT(Ax−b)&＃43;C2∣∣Ax−b∣∣22min⁡f(x)&＃43;C2∣∣Ax−b∣∣22s.t.Ax&＃61;bL_c(x,v)&＃61;f(x)&＃43;v^T(Ax-b)&＃43;\frac C2||Ax-b||_2^2\;\\\;\\\;\\\min f(x)&＃43;\frac C2||Ax-b||_2^2 \\s.t.\;Ax&＃61;bLc​(x,v)&＃61;f(x)&＃43;vT(Ax−b)&＃43;2C​∣∣Ax−b∣∣22​minf(x)&＃43;2C​∣∣Ax−b∣∣22​s.t.Ax&＃61;b

KKT条件

xk&＃43;1&＃61;xk−αk∇Lc(xk,vk)vk&＃43;1&＃61;vk&＃43;αk(Axk−b)⇒xk&＃43;1&＃61;arg min⁡xLc(x,vk)&＃xff08;并不需要十分精确的解&＃xff09;vk&＃43;1&＃61;vk&＃43;c(Axk&＃43;1−b)&＃xff08;AugmentedLagrangianMethod&＃xff09;x^{k&＃43;1}&＃61;x^k- \alpha^k\nabla L_c(x^k,v^k)\\v^{k&＃43;1}&＃61;v^k&＃43;\alpha^k(Ax^k-b)\\\;\;\\\Rightarrow\;x^{k&＃43;1}&＃61;\argmin_x L_c(x,v^k)&＃xff08;并不需要十分精确的解&＃xff09;\\v^{k&＃43;1}&＃61;v^k&＃43;c(Ax^{k&＃43;1}-b)\\&＃xff08;Augmented\;Lagrangian\;Method&＃xff09;xk&＃43;1&＃61;xk−αk∇Lc​(xk,vk)vk&＃43;1&＃61;vk&＃43;αk(Axk−b)⇒xk&＃43;1&＃61;xargmin​Lc​(x,vk)&＃xff08;并不需要十分精确的解&＃xff09;vk&＃43;1&＃61;vk&＃43;c(Axk&＃43;1−b)&＃xff08;AugmentedLagrangianMethod&＃xff09;

性质&＃xff1a;

1. 若v&＃61;v∗v&＃61;v^*v&＃61;v∗&＃xff0c;则∀c>0,x∗&＃61;arg min⁡xLc(x,v∗)\forall c>0,x^*&＃61;\argmin_x L_c(x,v^*)∀c>0,x∗&＃61;xargmin​Lc​(x,v∗)
2. 若$c\to \&＃43;\infty$&＃xff0c;则∀v,x(&＃61;arg min⁡xLc(x,v)\forall v,x^(&＃61;\argmin_x L_c(x,v)∀v,x(&＃61;xargmin​Lc​(x,v)

下一章传送门&＃xff1a;中科大-凸优化 笔记&＃xff08;lec52&＃xff09;-常用技巧&＃xff08;分布式计算&＃xff09;