69-理论方法-近似点算法

知识点：近似点算法

知识点概述

近似点算法（Proximal Point Algorithm, PPA）是求解非光滑凸优化问题 $\min g(x)$ 的一种基本算法。它通过迭代地求解一系列邻近算子问题来逼近最优解。近似点梯度法可以看作是近似点算法在复合优化问题上的应用。

详细解释

• 算法:
  1. 选择初始点 $x_0$。
  2. 迭代更新: $x_{k+1}={\text{prox}}_{{\alpha }_{k}g}(x_k)=\arg {\min }_x(g(x)+\frac{1}{2{\alpha }_k}\Vert x-x_k{\Vert }^2)$。
• 直观: 在每一步，算法不是试图直接最小化 $g(x)$，而是最小化一个加了二次正则项的近似版本。这个正则项使得子问题是强凸的，有唯一解，并且将解“拉住”在当前点 $x_k$ 附近，使得迭代过程稳定。
• 与增广拉格朗日法的关系: 可以证明，求解对偶问题的增广拉格朗日法等价于在对偶函数上应用近似点算法。
• Moreau-Yosida 正则化: 函数 $g$ 的Moreau包络 $M_{\gamma g}(x)={\inf }_v(g(v)+\frac{1}{2\gamma }\Vert v-x{\Vert }^2)$ 是一个光滑的、与原函数有相同最小值的近似。近似点算法可以被看作是在Moreau包络上进行梯度下降。

学习要点

• 掌握近似点算法的迭代公式。
• 理解其核心思想：用一个正则化的、更容易求解的子问题来迭代逼近。
• 了解近似点算法与增广拉格朗日法、Moreau正则化之间的深刻联系。

实践应用

• PPA本身更多是理论工具和构建其他算法（如ADMM）的基础，因为它要求能求解 $g$ 的邻近算子。当 $g$ 结构复杂时，直接应用PPA并不容易。

关联知识点

• 前置知识: 67-理论方法-近似点梯度法, 28-核心概念-次梯度
• 后续知识: 72-理论方法-交替方向乘子法
• 相关知识: 65-理论方法-增广拉格朗日函数法