求解可分凸规划的并行分裂算法研究

项目名称： 求解可分凸规划的并行分裂算法研究

项目编号： No.11301280

项目类型： 青年科学基金项目

立项/批准年度： 2014

项目学科： 数理科学和化学

项目作者： 陶敏

作者单位： 南京大学

项目金额： 22万元

中文摘要： 大量实际问题，如压缩感知，数据挖掘中的主成份分析，分布式网络问题，最终都归结为一类具有等式约束的可分凸规划问题。由于目标函数含有多个算子（指多于两个），这给经典的分裂算法的直接应用带来困难。又因为这些问题来源实际，问题的规模庞大，数据集结构复杂，因而设计行之有效的一阶算法已经迫在眉睫。我们将利用算法分裂的思想和松弛的技巧，在充分考虑这类问题的特殊结构的基础上，设计适合大规模问题的一阶算法。通过降维和松弛的思想，并行计算等手段，将此类可分凸规划问题转化为一系列易于求解的低维子问题。当这些低维子问题不具有显式解时，我们采用适度松弛的方法，非精确求解它，使得松弛后的子问题具有显式解。同时，我们也会根据各类实际问题的需要，设计适用于问题需要的并行分裂算法。最后，我们从理论上分析算法的全局收敛性和收敛速率，进一步考虑加速策略。从而解决了求解大规模凸规划问题尚无成熟有效的并行算法的难题。

中文关键词： 可分凸规划；分裂算法；并行算法；；

英文摘要： A large number of practical problems, such as compressive sensing, principal component analysis in data mining, distributed network problems, can be captured by the task of solving separable convex programming problems. Because the objective function is expressed as the sum of multi-operators, the classical splitting algorithm, such as forward-backward algorithm, Douglas-Rachford algorithm, can not directly handle it whenever the number of individual operators is greater than two. The difficulty of high dimensionality excludes direct applications of some state-of-the-art yet generally-purposed solvers such as SeDuMi, SDPT3. The purpose of the proposal is to design efficientive parallel splitting algorithm to solve the large scale separable convex problem. By exploring the special structure and parital ralaxed technique, we can alleviate the hardness brought by high dimensionality. Study on different splitting techniques, and establish the global convergence property. Moreover, we will study the convergence rate to perspective the opportunity of achieving accelerated speed. Finally, we will develop some generally- purposed practical software by applying our splitting algorithms.

英文关键词： separable convex programming；splitting algorithm；parallel algorithm；；