非凸规划的分布式增广拉格朗日型方法：理论、算法及应用

The problems that arise in practical applications such as signal and image processing, machine learning, statistics, and finance are non-convex and nonsmooth. And because of its huge data, some problems can amount to billions variables, this project will design more efficient distributed augmented Lagrangian based algorithms. Under the frame of the augmented Lagrangian method, the outer iteration will use a convergent symmetric alternating method of multipliers. Meanwhile, the original problem will be divided into smaller scale inner problems solved by parallel computing. Based on non-convex optimization theory and duality theory, the optimal conditions will be given by analyzing the property of primal problem and its augmented Lagrangian dual. In terms of algorithm design and theory, non-smooth analysis and semi-algebraic function characteristics are used to prove the convergence and convergent rate of the proposed methods. And combining with coordinate descent methods, alternating direction methods of multipliers, and proximal point methods to design parallel and distributed algorithms with computer clusters. For numerical experiment, we not not only use the benchmark examples of convex programming, but also some practical application with real data from gene expression analysis and recommendation systems by using Matlab, C++ and Python language on computer clusters with CPUs and GPUs, to verify the effectiveness and practicability of the proposed algorithms.

在信号和图像处理、机器学习、统计和金融等实际应用领域往往产生的问题都是非凸非光滑的，并且因其数据巨大，有些问题可达上百亿个变量，所以本项目将对该类问题设计快速有效的分布式增广拉格朗日型算法。本项目将基于增广拉格朗日型方法框架，外层算法用收敛的对称乘子交替型方法，并把问题拆分成规模较小的规划问题，运用并行的思想进行求解。在非凸优化理论和对偶理论的基础上，考虑原问题及其增广拉格朗日对偶问题的性质，给出问题的最优性条件。在算法设计和理论方面，将利用非光滑分析和半代数函数特性，结合坐标下降算法、乘子交替方向法和临近点方法思想，设计并行和分布式算法并用计算机集群进行求解，并证明算法的收敛性和收敛率。在数值方面，不仅利用非凸规划基准算例，还要结合基因b表示分析和推荐系统等应用领域的实际数据，运用Matlab、C++和Python语言利用带GPUs和CPU的机群进行计算，以此来验证算法的有效性和实用

本项目深入研究了在信号和图像处理、机器学习、统计和金融等实际应用领域产生的非凸非光滑的问题，并且因其数据巨大，有些问题可达上百亿个变量，所以分别针对不同类型问题研究了适合的快速有效的增广拉格朗日型方法理论、算法或应用。在增广拉格朗日算法理论方面，对非线性凸规划问题的增广拉格朗日方法进行收敛速度分析，设计的实用相对误差准则工具。同时，对于非线性锥优化问题提出了二阶增广拉格朗日型求解算法，并提出同意算法收敛性分析框架。还系统地总结了在凸矩阵优化问题对偶的温和二次增长条件下，求解凸矩阵优化问题的增广拉格朗日方法生成的序列KKT残差的R超线性收敛性及实现技巧。最近，还介绍了最新强变分充分性条件在非多面体问题的增广拉格朗日算法的收敛性分析中的重要作用。在增广拉格朗日方法实现及应用方面，针对带边界约束的大规模半定规划问题，提出基于不精确对称Gauss-Seidel半临近增广拉格朗日型算法，设计了友好的模型输入解释器和更简单的终止条件，并通过嵌入Mex文件提升了Matlab运行效率，升级优化了SDPNAL+求解器。其次，提出了与组合优化中经典的二次指派问题(QAP)等价的新模型--带秩约束的双非负锥问题，并在DC方法框架下，设计了一种高效的松弛模型--半临近DC算法来求解带秩约束的双非负锥问题的松弛问题。最后，针对统计和机器学习中产生的非凸优化问题--带异常误差的噪声观察问题，提出了一种基于矩阵优化的嵌入模型。 此项目中积累的研究成果和经验，将有助于我们解决工程实际问题，对国家急需的优化求解器研发工作有着一定的推动作用。