3.2. 对偶上升算法¶
3.2.1. 概念与内涵¶
对偶上升法 (Dual Ascent) [1] p5
考虑如下等式约束凸优化问题
(3.1)¶\[P_0: \begin{array}{ll}{\rm{min}_{\bm x}} & {f({\bm x})} \\ {\text { s.t. }} & {{\bm A}{\bm x} = {\bm b}}\end{array}
\]
其中, \({\bm x}\in{\mathbb R}^{N\times 1}\), \({\bm A}\in{\mathbb R}^{M\times N}\), \(f: {\mathbb R}^{N\times 1} \rightarrow {\mathbb R}\) 为凸函数. 问题 \(P_0\) ( 式.3.1) 的拉格朗日函数形式为
\[L({\bm x}, {\bm \lambda}) = f({\bm x}) + {\bm \lambda}^T({\bm{Ax}-{\bm b}})
\]
其对偶函数为
\[{D}: {\rm max}\ g({\bm x}) = {\rm inf}_{\bm x} L({\bm x}, {\bm \lambda}) = -f^{*}(-{\bm A}^T{\bm \lambda}) - {\bm b}^T{\bm \lambda},
\]
其中, \({\bm \lambda}\) 为对偶变量也是拉格朗日乘子变量, \(f^{*}\) 是函数 \(f\) 的凸共轭.
对偶上升法迭代更新过程为
\[\begin{aligned} {\bm x}^{k+1} & :=\underset{{\bm x}}{\operatorname{argmin}} L\left({\bm x}, {\bm \lambda}^{k}\right) \\ {\bm \lambda}^{k+1} & :={\bm \lambda}^{k}+\mu^{k}\left({\bm A} {\bm x}^{k+1}-{\bm b}\right) \end{aligned}
\]
其中, \(k\) 为迭代次数, \({\mu}^k\) 为迭代步长. 选择合适的 \({\mu}^k\), 对偶函数每次迭代后会上升 (\(g({\bm x})\)), 因而称为对偶上升法.