3.5. 增广拉格朗日法¶
增广拉格朗日法 (Augmented Lagrangian Method, ALM)
3.5.1. 概念与内涵¶
设有等式约束优化问题:
(3.8)¶\[{P}_0: {\rm min}_{\bm x}\ f({\bm x})\ \ {\rm s.t.}\ \ g_i({\bm x}) = 0,
\]
其中, \(g_i, i=1,2,\cdots,M\) 为 \(M\) 个等式约束. 化为无约束优化的曾广拉格朗日函数形式为
(3.9)¶\[{P}_1: {\rm min}_{\bm x}\ L({\bm x}, {\bm \lambda}, \mu) = f({\bm x}) - \sum_{i=1}^M \lambda_i g_i({\bm x}) + \frac{\mu}{2}\sum_{i=1}^M g_i({\bm x})^2,
\]
其中, \(i=1,2,\cdots,M\), \(\lambda_i\) 为 拉格朗日乘子 (Lagrange Multiplier), \(\mu\) 为增广拉格朗日乘子 (Augmented Lagrange Multiplier). 其矩阵形式为
(3.10)¶\[{P}_1: {\rm min}_{\bm x}\ L({\bm x}, {\bm \lambda}, \mu) = f({\bm x}) - {\bm \lambda}^T {\bm g} + \frac{\mu}{2} \|{\bm g}\|_2^2,
\]
其中, \({\bm \lambda} = [\lambda_1, \lambda_2, \cdots, \lambda_M]^T\) 为 \(M\) 个拉格朗日乘子构成的向量, \({\bm x} = [x_1, x_2, \cdots, x_N]^T\) 为 \(N\) 个变量构成的向量, \({\bm g} = [g_1({\bm x}), g_2({\bm x}),\cdots, g_M(\bm x)]^T\) 为 \(M\) 个约束构成的向量. \(\|\|_2^2\) 表示向量的 \(\ell_2\) 范数.
即增广拉格朗日在拉格朗日的基础上加上了一个光滑惩罚项 \(\|{\bm g}\|_2^2\).
与对偶上升法类似 (对偶上升算法), 其迭代迭代更新规则为
\[\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 {\bm g}({\bm x}^{k+1}) \end{aligned}
\]