复合凸优化的快速邻近点算法

EFFICIENT PROXIMAL POINT ALGORITHM FOR CONVEX COMPOSITE OPTIMIZATION

在大数据时代,随着数据采集手段的不断提升,大规模复合凸优化问题大量的出现在包括统计数据分析,机器与统计学习以及信号与图像处理等应用中.本文针对大规模复合凸优化问题介绍了一类快速邻近点算法.在易计算的近似准则和较弱的平稳性条件下,本文给出了该算法的全局收敛与局部渐近超线性收敛结果.同时,我们设计了基于对偶原理的半光滑牛顿法来高效稳定求解邻近点算法所涉及的重要子问题.最后,本文还讨论了如何通过深入挖掘并利用复合凸优化问题中由非光滑正则函数所诱导的非光滑二阶信息来极大减少半光滑牛顿算法中求解牛顿线性系统所需的工作量,从而进一步加速邻近点算法.

In the Big Data era,with the advent of convenient automated data collection technologies,large-scale composite convex optimization problems are ubiquitous in many applications,such as massive data analysis,machine and statistical learning,image and signal processing.In this paper,we review a class of efficient proximal point algorithms for solving the large-scale composite convex optimization problems.Under the easy-to-implement stopping criteria and mild calmness conditions,we show the proximal point algorithm enjoys global and local asymptotic superlinear convergence.Meanwhile,based on the duality theory,we propose an efficient semismooth Newton method for handling the subproblems in the proximal point algorithm.Lastly,to further accelerate the proximal point algorithm,we fully exploit the nonsmooth second order information induced by the nonsmooth regularizer in the problem to achieve a dramatic reduction of the computational costs of solving the involved semismooth Newton linear systems.