一类非凸优化问题分裂算法的收敛率及非精确准则的研究

The splitting method is a very efficient algorithm for solving separable optimization problems, which has the unique advantages in both theoretical analysis and numerical results, and thus it received wide attention since it appeared. This project intends to study the convergence rate, implementation and application of the existing splitting methods, and as well as design the corresponding methods for problems with special structures. First, the local convergence and the condition guaranteeing linear convergence rate of the splitting methods for nonconvex separable optimization problems are studied theoretically. Second, in order to make the splitting algorithms more practical, some relaxing inaccuracy criteria will be introduced, which will not only make the subproblems be able to be solved or easy to be solved, but also reduce the calculation cost of each iteration. In addition, this project intends to solve the optimization problems with special structures such as “semi-convex + strong convex” and uses its own properties to design the corresponding splitting methods and analyze the convergence results of them. Finally, applications of the methods to the portfolio selection, compressed sensing will be studied. The research results of this project will provide corresponding methods for the nonconvex separable optimization problems which widely appeared in practical applications, and give the theoretical analysis, which provide new ideas for the study of nonconvex problems and theoretical basis for solving some practical problems.

分裂算法是一类非常高效的用于求解可分优化问题的算法，因其在理论分析和数值效果上都有着独特的优势，故自其出现以来受到了广泛的关注。本项目针对非凸可分优化问题，研究已有分裂算法的收敛速率、算法的可实现性以及具体问题的应用，并针对特殊结构的问题进行相应的算法设计。首先，从理论上分析求解非凸可分优化问题时分裂算法的局部收敛性以及线性收敛条件；其次，为使分裂算法更加实用，拟引入宽松的非精确准则，使得子问题能够求解或更易求解，从而降低算法在每步迭代的计算量；此外，针对“半凸+强凸”这一特殊结构的优化问题，利用其自身性质，设计相应的分裂算法，并给出收敛性结果；最后，拟将算法应用到投资组合、压缩传感等实际问题中。本项目的研究结果将为实际应用中广泛出现的非凸可分优化问题提供相应的求解算法，并进行理论分析，为非凸问题的研究提供新的思路，也为一些实际问题的求解提供了理论依据。

本项目针对信号处理、图像处理等领域中产生的非凸可分优化问题，研究已有分裂算法的收敛性及收敛速度、算法的可实现性，并针对特殊结构的问题设计新的算法。首先，在误差界条件下，证明了交替方向法、对称交替方向法在求解非凸可分优化问题时函数值序列的Q线性收敛率及迭代点序列的R线性收敛率。在KL不等式条件下，证明了外推的邻近梯度算法的收敛性及收敛率。其次，将非精确策略引入已有算法，给出对称交替方向法、外推邻近梯度算法的非精确版本及收敛性结果。此外，针对目标函数包含有限和形式的优化问题，提出了增量聚合邻近交替方向法，且在非凸的情形下，给出了类邻近增量聚合梯度算法、增量聚合邻近交替方向法的收敛性分析结果。最后，将算法应用到投资组合、压缩传感、稀疏逻辑回归等实际问题中，验证理论结果的正确性以及新设计的算法的高效性。本研究的结果为非凸可分优化问题的求解提供了理论依据，也为实际应用中的优化问题提供相应的求解算法。