中科大凸优化笔记（lec40）松弛对偶

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

例&＃xff1a;Boolen LP问题

例&＃xff1a;Boolen LP等价问题

{min⁡cTxs.t.Ax≤bxi(xi−1)&＃61;0,i&＃61;1,⋯,n⇒L(x,λ,v)&＃61;cTx&＃43;λT(Ax−b)&＃43;∑i&＃61;1nvixi2−∑i&＃61;1nvixi&＃61;∑i&＃61;1nvixi2&＃43;(c&＃43;AλT−v)Tx−λTb⇒g(λ,v)&＃61;inf⁡xL(x,λ,v)&＃61;{−λTb−14∑i&＃61;1n(ci&＃43;aiTλ−vi)2vi,v≥0−∞,otherwise(D)max⁡−λTb−14∑i&＃61;1n(ci&＃43;aiTλ−vi)2vis.t.λ≥0,v≥0max⁡λ,vf(λ,v)&＃61;max⁡λmax⁡vf(λ,v)\begin{cases} \min c^Tx \\ s.t. \;\;Ax\le b\\\;\;\;\;\;\;\;x_i(x_i-1)&＃61;0,i&＃61;1,\cdots,n \end{cases}\\\;\\\Rightarrow L(x,\lambda,v)&＃61;c^Tx&＃43;\lambda^T(Ax-b)&＃43;\sum_{i&＃61;1}^nv_ix_i^2-\sum_{i&＃61;1}^nv_ix_i\\&＃61;\sum_{i&＃61;1}^nv_ix_i^2&＃43;(c&＃43;A\lambda^T-v)^Tx-\lambda^Tb\\\;\\\Rightarrow g(\lambda,v)&＃61;\inf_x L(x,\lambda,v)&＃61;\begin{cases} -\lambda^Tb-\frac14\sum_{i&＃61;1}^n\frac{(c_i&＃43;a_i^T\lambda-v_i)^2}{v_i},v\ge0\\ -\infty,\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;otherwise \end{cases}\\\;\\(D)\;\max -\lambda^Tb-\frac14\sum_{i&＃61;1}^n\frac{(c_i&＃43;a_i^T\lambda-v_i)^2}{v_i}\\s.t.\;\;\lambda\ge0,v\ge0\\\max_{\lambda,v}f(\lambda,v)&＃61;\max_\lambda\max_vf(\lambda,v)⎩⎪⎨⎪⎧​mincTxs.t.Ax≤bxi​(xi​−1)&＃61;0,i&＃61;1,⋯,n​⇒L(x,λ,v)&＃61;cTx&＃43;λT(Ax−b)&＃43;i&＃61;1∑n​vi​xi2​−i&＃61;1∑n​vi​xi​&＃61;i&＃61;1∑n​vi​xi2​&＃43;(c&＃43;AλT−v)Tx−λTb⇒g(λ,v)&＃61;xinf​L(x,λ,v)&＃61;{−λTb−41​∑i&＃61;1n​vi​(ci​&＃43;aiT​λ−vi​)2​,v≥0−∞,otherwise​(D)max−λTb−41​i&＃61;1∑n​vi​(ci​&＃43;aiT​λ−vi​)2​s.t.λ≥0,v≥0λ,vmax​f(λ,v)&＃61;λmax​vmax​f(λ,v)

例&＃xff1a;带等式约束的可微凸优化问题

下一章传送门&＃xff1a;中科大-凸优化 笔记&＃xff08;lec41&＃xff09;-可微凸优化问题的罚函数形式