非凸优化问题Douglas-Rachford分裂方法的研究

Large-scale separable optimization problem is one of the most popular research topics among the field of optimization, which has important applications in many fields, such as bio-informatics, machine learning and statistics and so on. The Douglas-Rachford splitting method (DRSM), as one of the classical splitting methods, gets great progress in studying convex optimization problems in recent years, especially the famous algorithm--the alternating direction method of multipliers (ADMM), which is one of the applications of the DRSM. However, the research on nonconvex optimization problems is in its infancy. This project aims to apply the DRSM to solve nonconvex optimization problems: First of all, we study the convergence of ADMM for minimizing sum of two separable nonconvex functions with linear constraints, overcoming the existing conclusion that either one of the constraint matrices is a unit matrix or stronger assumptions. Then, we study its large stepsize counterpart. Furthermore, we consider the convergence of ADMM for multi-block nonconvex separable optimization problems with linear constraints and prove its convergence under weaker conditions. Finally, when the constant of strongly convex function equals the constant of weakly convex function, we try to prove the convergence of DRSM for solving the “strongly+weakly” convex optimization problems without any differentiability assumption of the objective function or illustrate its divergence by a counter-example. This research provides a theoretical support for the further applications of DRSM.

大规模可分优化在生物信息学、机器学习、统计学等很多领域中都有重要的应用，已经成为优化领域的一个热点问题。Douglas-Rachford分裂方法(DRSM)作为经典的分裂方法之一，对于凸优化问题的研究，近年来取得了巨大的进展，特别是作为其应用得到的著名算法--乘子交替方向法(ADMM)。然而，对于非凸优化问题的研究才刚刚起步。本项目主要研究求解非凸优化问题的DRSM：首先，研究求解线性约束两块可分非凸优化问题的ADMM的收敛性，克服现有结论中需要某一约束矩阵为单位矩阵或较强的、复杂的假设；接着，研究其对应的大步长算法；进一步，考虑采用ADMM求解线性约束多块可分非凸优化问题，并在较弱条件下证明算法的收敛性；最后，在不假设目标函数可微性的情况下，当强凸系数等于弱凸系数时，证明DRSM求解“强凸+弱凸”问题的收敛性或给出反例说明其不收敛。该项目的研究结果将为DRSM更广泛的应用提供理论保障。

首先，对于非凸优化问题：我们研究了广义乘子交替方向法求解两类优化问题，在一定的假设下，证明了该算法的收敛性及收敛速度；对于具有特殊结构的非凸优化问题，我们研究了邻近次梯度算法求解该问题的线性收敛率；对于具有半代数邻近正则性的非凸多重集分裂问题，我们提出了一类非精确均值投影算法并证明了其收敛性。其次，对于凸优化问题：我们证明了对数二次邻近正则的严格收缩Peaceman-Rachford分裂算法求解线性约束两块可分凸优化问题在大步长意义下的全局收敛性，并应用于交通网络均衡问题。再次，对于算子问题：利用负均值算子的性质，我们简洁且优雅地证明了松弛向前向后分裂算法求解两个极大单调算子和的零点问题的线性收敛性；对于非扩张映射的不动点问题，我们提出了两类逼近算法并证明了其收敛性。最后，对于变分不等式问题：我们部分解决了著名优化专家Censor提出关于双次梯度外梯度算法的收敛性；提出了具有移动邻近中心的非对称邻近点算法，在精确和非精确的情况下我们证明了算法的收敛性及收敛速度。