增广拉格朗日函数法

在二次罚函数法中我们知道，为了保证可行性，惩罚因子必须趋于正无穷，但是此时子问题的条件数爆炸而难以求解，那么我们是否可以对二次罚函数进行某种修正使得对有限的惩罚因子，得到的逼近最优解也是可行的？增广拉格朗日函数法就是这样的一个方法

等式约束优化问题的增广拉格朗日函数法

增广拉格朗日函数法的构造

增广拉格朗日函数法的每一步构造一个增广拉格朗日函数，而该函数的构造依赖于拉格朗日函数和约束的二次罚函数，具体来说，对于等式约束优化问题 $$ \min_{x} f(x),\ \text{s.t.}\ \ c_i(x)=0,\qquad i\in E $$ 增广拉格朗日函数定义为 $$ L_{\sigma}(x,\lambda)=f(x)+\sum_{i\in E}\lambda_ic_i(x)+\frac{1}{2}\sigma\sum_{i\in E}c_i^2(x) $$ 即在拉格朗日函数的基础上，添加约束的二次罚函数。

在第 \(k\) 步迭代，给定惩罚因子 \(\sigma_k\) 和乘子 \(\lambda_k\)，增广拉格朗日函数 \(L_{\sigma_k}(x,\lambda_k)\) 的最小值点 \(x_{k+1}\) 满足 $$ \nabla_x L_{\sigma_k}(x_{k+1},\lambda_k)=\nabla f(x_{k+1})+\sum_{i\in E}(\lambda_i^k+\sigma_kc_i(x_{k+1}))\nabla c_i(x_{k+1})=0 $$

Tip

这里为书写方便，我们将第 \(k\) 步的约束函数 \(c_i(x)\) 对应的 Lagrange 乘子记为 \(\lambda_{i}^k\)

而由 KKT 条件，最优解 \(x^*\) 以及相应的乘子 \(\lambda^*\) 需要满足

\[ \nabla f(x^*)+\sum_{i\in E}\lambda_i^*\nabla c_i(x^*)=0 \]

所以为了让增广拉格朗日函数法产生的迭代序列能够收敛到 \(x^*\)，我们需要保证上述两个等式在最优解处的一致性，所以对于成分大的 \(k\)，有

\[ \lambda_i^*\approx\lambda_{i}^k+\sigma_kc_i(x_{k+1}),\forall i\in E \]

上式等价于

\[ c_i(x_{k+1})\approx \frac{1}{\sigma_k}(\lambda_i^*-\lambda_{i}^k) \]

所以当 \(\lambda_{i}^k\) 足够接近 \(\lambda_i^*\) 时，点 \(x_{k+1}\) 处的约束违反度将会远小于 \(\frac{1}{\sigma_k}\)，所以增广拉格朗日函数法通过有效地更新乘子来降低约束违反度，并且由上式我们可以得到，乘子的一个有效的更新格式为

\[ \lambda_i^{k+1}=\lambda_i^k+\sigma_kc_i(x_{k+1}),\qquad \forall i\in E \]

则我们可以得到增广拉格朗日函数法的算法伪代码如下：

下面我们看一个例子，考虑优化问题 $$ \min x+\sqrt{3}y\ \text{s.t.}\ \ x^2+y^2=1 $$ 容易求出该问题最优解为 \(x^*=(-\frac{1}{2},-\frac{\sqrt{3}}{2})^T\)，相应的 Lagrange乘子 \(\lambda^*=1\)，我们考虑增广拉格朗日函数 $$ L_{\sigma}(x,y,\lambda)=x+\sqrt{3}y+\lambda(x^2+y^2-1)+\frac{\sigma}{2}(x^2+y^2-1)^2 $$ 并绘制 \(L_2(x,y,0.9)\) 的等高线如下图：

图中标 * 的点为原问题的最优解 \(x^*\)，标 \({}^\circ\) 的为罚函数或增广拉格朗日函数的最优解。可以看出，增广拉格朗日函数的最优解更加接近真实解。

随着惩罚因子 \(\sigma_k\) 的变大，\(L_{\sigma_k}(x,\lambda_k)\) 关于 \(x\) 的 Hessian 矩阵的条件数也会越来越大，从而使得迭代点 \(x_{k+1}\) 的求解难度变大，但当 \(\sigma_k\) 和 \(\sigma_{k+1}\) 比较接近时，\(x_k\) 可以作为求解 \(x_{k+1}\) 的一个初始点，从而加快收敛。因此惩罚因子 \(\sigma_k\) 增长得不能太快，但如果增长得太慢，迭代点列 \(\{x_k\}\) 收敛到原问题解的速度也会变慢。

收敛性

一个自然的问题是，增广拉格朗日函数的极小值点和原问题的极小值点之间有什么关系？我们假设 \(x^*\) 和 \(\lambda^*\) 分别为等式约束问题的局部极小解和对应点乘子，并且二阶充分条件成立，则可以证明，在已知 \(\lambda^*\) 的情况下，对于有限大的 \(\sigma\)，\(x^*\) 也为增广拉格朗日函数 \(L_{\sigma}(x,\lambda^*)\) 的严格局部极小解。当 \(\lambda^*\) 未知时，对于足够接近 \(\lambda^*\) 的 \(\lambda\) 以及足够大的 \(\sigma\)，增广拉格朗日函数 \(L_{\sigma}(x,\lambda)\) 的局部极小解会与 \(x^*\) 足够接近。我们有如下定理

定理 设 \(x^*,\lambda^*\) 分别为等式约束问题的局部极小解和相应的乘子，并且在点 \(x^*\) 处 LICQ 和二阶充分条件成立，则存在一个有限大的常数 \(\overline{\sigma}\)，使得对任意的 \(\sigma\geq \overline{\sigma}\)，\(x^*\) 都是 \(L_{\sigma}(x,\lambda^*)\) 的严格局部极小解。反之，如果 \(x^*\) 为 \(L_{\sigma}(x,\lambda^*)\) 的局部极小解且满足 \(c_i(x^*)=0,i\in E\)，那么 \(x^*\) 为等式约束问题的局部极小解

并且对于上述算法，我们通过进一步假设乘子点列的有界性和收敛点处的约束品性，可以证明算法迭代产生的点列 \(\{x_k\}\) 会有子列收敛到等式约束问题的一阶稳定点

增广拉格朗日函数法的收敛性 假设乘子列 \(\{\lambda_k\}\) 是有界的，惩罚因子 \(\sigma_k\to +\infty,k\to \infty\)，算法 7.5 中精度 \(\eta_k\to 0\)，迭代点列 \(\{x_k\}\) 的一个子序列 \(x_{k_j+1}\) 收敛到 \(x^*\)，并且在点 \(x^*\) 处 LICQ 成立，则存在 \(\lambda^*\)，满足

\[\begin{align} \lambda_{k_j+1}\to \lambda^*,\ j\to \infty\\ \nabla f(x^*)+\nabla c(x^*)\lambda^*=0,\ \ c(x^*)=0 \end{align}\]

一般约束优化问题的增广拉格朗日函数法

对于一般约束优化问题

\[\begin{align} \min f(x)\\ \text{s.t.} \ c_i(x)=0,i\in E\\ c_i(x)\geq 0,i\in I \end{align}\]

我们也可以定义其增广拉格朗日函数以及设计相应的增广拉格朗日函数法。这里我们先通过引入松弛变量将不等式约束转化为等式约束和简单的非负约束，再对保留非负约束形式的拉格朗日函数添加等式约束的二次罚函数来构造增广拉格朗日函数

增广拉格朗日函数

对于上述一般约束优化问题，我们通过引入松弛变量可以得到如下等价形式

\[\begin{align} \min_{x,s} f(x),\\ \text{s.t.}\ c_i(x)=0,i\in E\\ c_i(x)-s_i=0,i\in I\\ s_i\geq 0,i\in I \end{align}\]

保留非负约束，我们可以构造拉格朗日函数

\[ L(x,s,\lambda,\mu)=f(x)+\sum_{i\in E}\lambda_ic_i(x)+\sum_{i\in I}\mu_i(c_i(x)-s_i), \ s_i\geq 0,i\in I \]

记一般约束优化问题中的等式约束的二次反函数为 \(p(x,s)\)，则有

\[ p(x,s)=\sum_{i\in E}c_i^2(x)+\sum_{i\in I}(c_i(x)-s_i)^2 \]

我们构造增广拉格朗日函数如下：

\[ L_{\sigma}(x,s,\lambda,\mu)=f(x)+\sum_{i\in E}\lambda_ic_i(x)+\sum_{i\in I}\mu_i(c_i(x)-s_i)+\frac{\sigma}{2}p(x,s),\ \ s_i\geq 0,i\in I \]

其中 \(\sigma\) 为惩罚因子

增广拉格朗日函数法

在第 \(k\) 步迭代中，给定乘子 \(\lambda_k\) 和 \(\mu_k\) 和惩罚因子 \(\sigma_k\)，我们需要求解如下问题

\[ \min_{x,s} L_{\sigma_k}(x,s,\lambda_k,\mu_k),\ \text{s.t.}\ \ s\geq 0 \]

以得到 \(x_{k+1},s_{k+1}\)，求解上述问题的一个有效地方法是梯度投影法（这里不做介绍），另一种方法是消去 \(s\)，求解只关于 \(x\) 的优化问题，具体来说，固定 \(x\)，关于 \(s\) 的子问题可以表示为

\[ \min_{s\geq 0}\sum_{i\in I}\mu_i(c_i(x)-s_i)+\frac{\sigma_k}{2}\sum_{i\in I}(c_i(x)-s_i)^2 \]

根据凸优化问题的最优性理论，\(s\) 是上述问题的一个全局最优解当且仅当

\[ s_i=\max\{\frac{\mu_i}{\sigma_k}+c_i(x),0\},i\in I \]

将 \(s_i\) 的表达式代入 \(L_{\sigma_k}\)，则可以得到

\[ L_{\sigma_k}(x,\lambda_k,\mu_k)=f(x)+\sum_{i\in E}\lambda_ic_i(x)+\frac{\sigma_k}{2}\sum_{i\in E}c_i^2(x)+\frac{\sigma_k}{2}\sum_{i\in I}(\max\{\frac{\mu_i}{\sigma_k}-c_i(x),0\}^2-\frac{\mu_i^2}{\sigma_k^2}) \]

其为关于 \(x\) 的连续可微函数，故 \(\min_{x,s} L_{\sigma_k}(x,s,\lambda_k,\mu_k),\ \text{s.t.}\ \ s\geq 0\) 等价于

\[ \min_{x\in R^n} L_{\sigma_k}(x,\lambda_k,\mu_k) \]

可以利用梯度法进行求解。

对于一般约束最优化问题，其最优解 \(x^*,s^*\) 和乘子 \(\lambda^*,\mu^*\) 需要满足 KKT 条件：

\[ 0=\nabla f(x^*)+\sum_{i\in E}\lambda_i^*\nabla c_i(x^*)+\sum_{i\in I}\mu_i^*\nabla c_i(x^*),\\ \mu_i^*\geq 0,i\in I\\ s_i^*\geq 0,i\in I \]

而 \(\min_{x,s} L_{\sigma_k}(x,s,\lambda_k,\mu_k),\ \text{s.t.}\ \ s\geq 0\) 的最优解 \(x_{k+1},s_{k+1}\) 满足

\[ 0=\nabla f(x_{k+1})+\sum_{i\in E}(\lambda_i^k+\sigma_kc_i(x_{k+1}))\nabla c_i(x_{k+1})+\sum_{i\in I}(\mu_i^k+\sigma_k(c_i(x_{k+1})-s_i^{k+1}))\nabla c_i(x_{k+1})\\ s_i^{k+1}=\max\{\frac{\mu_i^k}{\sigma_k}+c_i(x_{k+1}),0\},\ \ i\in I \]

对比则可以得到乘子的更新格式为

\[ \lambda_i^{k+1}=\lambda_i^k+\sigma_kc_i(x^{k+1}),\ \ i\in E\\ \mu_i^{k+1}=\max\{\mu_i^k-\sigma_kc_i(x_{k+1}),0\},\ \ i\in I \]

对于等式约束，约束违反度定义为

\[ v_k(x_{k+1})=\sqrt{\sum_{i\in E}c_i^2(x_{k+1})+\sum_{i\in I}(c_i(x_{k+1})-s_i^{k+1})^2} \]

消去 \(s\)，约束违反度为

\[ v_k(x_{k+1})=\sqrt{\sum_{i\in E}c_i^2(x_{k+1})+\sum_{i\in I}\max\{-c_i(x_{k+1}),\frac{\mu_i^k}{\sigma_k}\}^2} \]

综上我们给出约束优化问题 \(\min_{x,s} L_{\sigma_k}(x,s,\lambda_k,\mu_k),\ \text{s.t.}\ \ s\geq 0\) 的增广拉格朗日函数法，其给出了算法参数的一种具体更新方式，即在每次计算出子问题的近似解 \(x_{k+1}\) 后，算法需要判断约束违反度 \(v_k(x_{k+1})\) 是否满足精度要求，如果满足，则进行乘子的更新，并提高子问题求解精度，此时惩罚因子不变；如果不满足，就不进行乘子的更新，并适当增大惩罚因子以便得到约束违反度更小的解。

开摆

后面的内容我赌不考

---

评论