非线性规划中的增广拉格朗日法

1. 问题背景与动机
   非线性规划（NLP）的目标是在约束条件下最小化目标函数。对于问题：

\[ \min f(x) \quad \text{s.t.} \quad h_i(x) = 0, \, i \in \mathcal{E}, \quad g_j(x) \leq 0, \, j \in \mathcal{I} \]

拉格朗日法通过引入乘子处理约束，但需在无约束优化中平衡可行性与最优性。传统拉格朗日法对非凸问题可能收敛失败，需改进。

2. 增广拉格朗日函数构造
   针对等式约束 \(h(x) = 0\)，定义增广拉格朗日函数：

\[ \mathcal{L}_A(x, \lambda; \rho) = f(x) + \lambda^\top h(x) + \frac{\rho}{2} \|h(x)\|^2 \]

其中 \(\rho > 0\) 为惩罚参数，\(\lambda\) 为拉格朗日乘子。附加的二次项 \(\frac{\rho}{2} \|h(x)\|^2\) 在偏离可行域时加大惩罚，促进约束满足。

3. 不等式约束的处理
   通过引入松弛变量 \(s_j \geq 0\)，将不等式约束 \(g_j(x) \leq 0\) 转化为等式：

\[ g_j(x) + s_j = 0, \quad s_j \geq 0 \]

或使用一次近似函数（如二次罚函数结合投影）。另一种常见方法是仅对活动约束施加二次惩罚。

4. 算法流程与乘子更新
   • 步骤1：给定初始乘子 \(\lambda^k\) 和参数 \(\rho^k\)，求解无约束子问题：

\[ x^{k+1} = \arg\min_x \mathcal{L}_A(x, \lambda^k; \rho^k) \]

• 步骤2：更新乘子以强化约束满足：

\[ \lambda^{k+1} = \lambda^k + \rho^k h(x^{k+1}) \]

该更新基于对偶上升思想，当 \(h(x) \neq 0\) 时调整乘子。

• 步骤3：自适应调整 \(\rho^k\)（例如根据约束违反程度增大）。

5. 收敛性与优势分析

   • 在适当条件下（如目标函数与约束光滑、满足二阶充分条件），算法收敛至局部最优解。
   • 相比纯罚函数法，二次项的存在允许在有限 \(\rho\) 下收敛，避免数值病态。
   • 对比拉格朗日松弛法，增广项使子问题更易求解且稳定性更高。

6. 扩展与变体

   • 交替方向乘子法（ADMM）：处理可分离结构的分布式优化。
   • 自适应惩罚参数：根据迭代进度动态调整 \(\rho\) 以平衡精度与速度。
   • 非精确求解：子问题无需精确优化，节省计算成本。