大规模结构型优化问题的加速分裂算法研究

In recent years, many optimization models arising from machine learning, image processing, traffic and network management, etc., demonstrate some favorable structure and properties including separablity, sparsity, and nonsmoothness. With the rapid development of interdisciplinary research and the massive data processing models, designing fast and efficient algorithms for structured problems is one of the hottest research topics in the area of scientific computing. Based on the classical splitting methods, in this project, we will design and study accelerated splitting methods for structured optimization problems. Specifically, our research includes: Developing some inexact partially parallel splitting methods for some convex programs with cumbersome subproblems, by incorporating the spirit of inexact rule and nonmonotone linesearch technique, and analyzing their convergence properties; Designing accelerated partially parallel splitting methods and inexact versions by utilizing inertial proximal points and Nesterov accelerated technique, and establishing their convergence；Proposing some augmented Lagrangian-based parallel splitting methods and inertial accelerated versions for multi-block non-convex problems, and establishing the theoretical results of the convergence and convergence rate by using K-L inequality, error bound conditions, and potential function, etc. Our results will be of great significance for further enriching the branch of splitting methods. More importantly, our methods would play important roles in big data processing.

近年来，机器学习、图像处理、交通和网络管理等应用领域呈现出大量带有特殊结构，如可分离、稀疏、非光滑等特点的优化模型。随着跨学科研究的兴起和海量数据处理模型的骤增，设计快速有效的求解算法成为科学计算领域中热门的研究课题之一。本项目拟在经典的分裂算法基础上，设计和研究加速的分裂算法求解结构型优化问题，具体研究内容包括：针对部分子问题不容易求解的凸优化问题，提出一些非精确的部分并行分裂算法，结合非精确准则、非单调线搜索技术，分析相关收敛性质； 借助惯性步、 Nesterov加速技巧，设计加速的部分并行分裂算法及其非精确形式，并证明算法收敛性；针对多块非凸优化问题，使用K-L不等式、误差界条件和势函数等工具，设计基于增广拉格朗日的并行分裂算法及其加速形式，建立算法的收敛性和收敛速率等理论结果。 本项目研究可以丰富分裂算法的理论结果和研究内涵，对推动分裂算法在大规模数据中应用具有重要的研究意义。

近年来，机器学习、图像处理、交通和网络管理等应用领域呈现出大量带有特殊结构，如可.分离、稀疏、非光滑、非凸性等特点的优化模型。随着跨学科研究的兴起和海量数据处理模.型的骤增，设计快速有效的求解算法成为科学计算领域中热门的研究课题之一。本报告在.经典的分裂算法基础上，设计和研究高效的分裂算法求解结构型优化问题，具体研究内容.包括：针对双线性鞍点问题，分析了在两种假设方案下一般形式的原始对偶算法和广义的.原始对偶混合梯度算法的线性收敛性；此外，提出了一种双外推原始对偶混合梯度算法，.分析了算法相关的收敛性、次线性收敛性和线性收敛性， 并且将算法应用到图像去噪、图.像恢复和矩阵优化等实际问题， 数值模拟验证了算法可行性和有效性；针对部分子问题不.容易求解的双线性鞍点问题，提出部分非精确的原始对偶混合梯度算法，结合非精确准则，.同样分析算法的相关收敛性、次线性收敛性和两种方案下线性收敛性；针对带耦合项的结.构型非凸优化问题，结合非线性正则化和惯性加速技术，提出一种惯性的交替邻近梯度下.降算法， 使用 K-L 不等式和势函数等工具，分析了算法在非渐近意义下次线性收敛性和全.局收敛性。 本项目研究进一步丰富分裂算法的理论结果和研究内涵，对推动分裂算法在大.规模数据中应用具有重要的研究意义.