非光滑优化加速束方法的研究及应用

In recent years, many nonsmooth optimization problems arise in practical fields, such as image reconstruction, signal processing, multicommodity flow and optimal control, etc., so the nonsmooth optimization methods have been widely studied and applied. This project mainly studies the accelerated prox-level bundle method, accelerated doubly stabilized bundle method, quasi-Newton type accelerated bundle method and their applications for solving nonsmooth optimization problems. The research contents and innovation are: (1) to propose the accelerated proximal-level bundle method based on inexact oracles, in order to achieve a satisfied approximate optimal solution of the practical problems whose function values and subgradients are unable or difficult to be calculated accurately; (2) to propose the accelerated doubly stabilized bundle method based on the ideas of multi-step acceleration scheme and doubly stabilized bundle method, in order to reduce the computational cost and accelerate the rate of convergence; (3) to propose the quasi-Newton-type accelerated bundle method for solving nonsmooth and nonconvex optimization problems, which combines the local convexification technique and quasi-Newton method idea, and takes quasi-Newton step as the acceleration step, aiming at overcoming the shortcoming of the existing methods that can handle convex optimization problems only; (4) to analyze the convergence property and computational complexity of the proposed methods; (5) to set up a large number of numerical experiments to verify the effectiveness of the algorithms, and try to apply these new approaches into practical problems, such as image reconstruction, signal processing and optimal control, etc.

近年来，在图像重构、信号处理、多物资网络流和最优控制等实际领域出现了大量的非光滑优化问题，因此非光滑优化方法得到了广泛的研究和应用。本项目主要研究求解非光滑优化问题的加速邻近水平束方法、加速双稳定束方法和拟牛顿型加速束方法及其实际应用。研究内容与创新主要有：（1）针对函数值和次梯度不能或不易精确计算的实际问题，提出基于非精确数据的加速邻近水平束方法，以期快速获得问题较满意的近似最优解；（2）基于多步加速策略和双稳定束方法思想，提出加速双稳定束方法，旨在减小传统方法的计算量、加快收敛速度；（3）针对非凸非光滑优化问题，结合局部凸化技术和拟牛顿法思想，将拟牛顿步作为加速步，提出拟牛顿型加速束方法，以克服现有方法只能求解凸优化问题的缺陷；（4）理论上分析论证提出方法的收敛性和计算复杂度；（5）进行大量数值试验，验证算法的有效性，并探索将新方法应用于图像重构、信号处理和最优控制等实际问题。

非光滑优化是数学规划领域研究的重要分支，广泛应用于最优控制，图像处理, 数据挖掘和机器学习等实际领域。本项目主要研究求解非光滑优化问题的加速束方法，旨在加快现有方法的收敛速度，并且能处理大规模问题、非精确数据问题和非凸问题等。研究成果主要有：（1）针对函数值和次梯度不能或不易精确计算的问题，提出了按需精度的邻近-投影束方法、广义交替线性化束方法和基于非精确数据的改进水平束方法。在不同的非精确情况下，建立了算法的全局收敛性。（2）基于多步加速策略和双稳定束方法思想，提出了多步加速双稳定束方法。该方法产生三个迭代序列，分别用于建立割平面模型、产生稳定中心及新的迭代点序列。通过提出一种新的下降测试准则，并利用多步法的优点，建立了该方法的全局收敛性，且数值效果显著优于传统方法。（3）针对非凸非光滑优化问题，结合局部凸化技术和拟牛顿法思想，提出了拟牛顿型加速束方法。基于BFGS公式构造搜索方向，并利用Armijo型线搜索技术确定步长。建立了算法的全局收敛性和超线性收敛性。数值结果表明，该方法优于现有重分布束方法。（4）提出求解非光滑不等式约束优化问题的有限存储水平束方法、可行方向束方法和两阶段束方法。充分利用束集管理和束集修正等策略，提升束集的质量，减少计算量，加快收敛速度。（5）提出求解约束Minimax问题的邻近-投影部分束方法和改进的可行下降束方法。提出求解结构非光滑优化的改进加速水平束方法和交替线性化束方法。（6）对提出的算法均进行了全局收敛性分析，部分进行了计算复杂度分析。开展了大量数值试验，以验证算法的有效性。数值试验程序已制成软件包，并应用于求解两阶段随机规划、最大特征值、Lovasz容量等问题。