复合优化问题的稳定性分析和增广拉格朗日方法

Composite optimization is a minimization problem whose objective function is the summation of a smooth function and a nonsmooth composition function. It is one of the most common and important problems in the fields of mathematical optimization, image processing, machine learning and statistics, and thus attracts more and more research interests in recent years. However, in theory the framework of optimality conditions and sensitivity analysis of composite optimization remains incomplete, in numerical the efficient second order algorithms for real world applications are quite limited. Therefore, it is of significant value to study the theory and algorithms of composite optimization. This project will substantially study the second order optimality theory and augmented Lagrangian method based on the theory of perturbation analysis and variational analysis. The research includes, establishing the second order optimality theory of composite optimization based on Moreau envelop; characterizing the strong regularity and isolated calmness of KKT solution mapping of composite optimization; constructing the augmented Lagrangian method for solving composite programs, solving the inner problems by semismooth Newton method and analyzing the global convergence and convergence rate. It is expected that the derived results in this project will make certain contributions in the development of the theory and algorithm of composite programs.

复合优化问题是目标函数为光滑函数和非光滑复合函数之和的极小化问题，它是数学规划、图像处理、机器学习和统计等领域最普遍的模型之一。近些年复合优化问题引起了人们很多的关注和兴趣，求解这类问题的一阶算法取得了重要的进展。然而，复合优化问题的最优性理论尤其是二阶最优性条件，稳定性分析和二阶算法目前还很不完善，因此研究这类问题的理论和算法具有重要的意义。本项目旨在以扰动分析和变分分析为工具，对复合优化问题的二阶最优性理论和增广拉格朗日方法进行深入的研究。具体研究内容包括：在Moreau包络的广义次微分的基础上的二阶最优性理论；基于合适的约束规范对复合优化问题KKT映射的强正则性和孤立平稳性的刻画；求解复合优化问题的增广拉格朗日方法以及收敛性和收敛速度的分析；求解增广拉格朗日方法内层子问题的半光滑牛顿算法。本项目预期的研究成果将推动复合优化问题的理论和算法的研究进展。

复合优化问题是目标函数为光滑函数和非光滑复合函数之和的极小化问题，它是数学规划、图像处理、机器学习和统计等领域最普遍的模型之一。近些年复合优化问题引起了人们的关注和兴趣，求解这类问题的一阶算法取得了重要的进展。然而，复合优化问题的最优性理论方面的研究目前还很不完善，因此研究这类问题的理论和算法具有重要的意义。本项目以扰动分析和变分分析为工具，对复合优化问题的最优性理论和相关的算法进行了深入的研究。本项目所取得的重要结果包括：（1）我们建立了一个统一的框架来研究一类小批量随机梯度方法的几乎确定的全局收敛性和期望收敛速度，这里包括了两种普遍的随机梯度——步长减少的随机梯度和样本大小增加的随机梯度。我们证明了当目标函数的梯度是Lipschitz连续时，文献中常用来研究随机梯度收敛性的标准方差一致有界假设实际上并不需要。我们还展示了此框架还可以用来分析求解随机变分不等式的小批量随机外梯度方法。（2）基于光滑方程组的三次正则化方法，我们考虑了一种求解半光滑方程组的三次正则化方法，通过引入信赖域方法的技巧调节步长，我们证明了求解半光滑方程组的三次正则化方法是全局收敛的。在子问题非精确求解和BD正则性条件成立的前提下，我们还讨论了三次正则化方法的局部收敛速度，并通过数值实验验证了所提出的算法的有效性。本项目的研究成果将为复合优化问题的理论和算法未来的研究提供新的思路和视角。