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

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.

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

大量实际问题，如压缩感知，数据挖掘中的主成分分析，分布式网络问题，最终都转化成可分凸规划问题。通常，这些起源于实际应用问题的可分凸规划问题都具有规模大，结构特殊等特点， 所以采用分裂型算法来求解是很自然的想法。这里分裂的思想是指分解和降维。采用该方法的益处是使得分解和降维以后的子问题更容易求解。对于分裂以后得到的子问题通常按照执行的顺序，大致可以将分裂型算法分成交替型算法，并行算法和部分交替，部分并行的算法。对于交替型算法，最有效的当属交替方向法。然而，采用直接推广的交替方向法求解可分凸规划问题，当可分算子等于三块时，该方法被证明有可能是发散的。对于并行算法，它有着很强的应用背景，例如，传统中央式网络具有信息传输成本高，网络架构缺乏稳健性等遗憾，所以，分布式网络应运而生。然而，分布式网络问题的求解需要采用并行分裂算法，原因是每个节点只可以利用和它相邻节点的信息。.本项目着眼于可分凸规划的分裂算法设计和分析，并取得了如下的进展：.1. 针对各类应用问题设计了四类多元分裂并行算法,根据所求解模型目标函数的可分凸算子的特性，分别设计了不同的求解子类问题的策略。并将其应用到分布式网络问题的求解当中。2. 分析了提出的四类并行算法的全局收敛性和计算复杂度。3.对于某一类可分凸规划问题，研究了不精确加速分裂算法，该算法对于目标函数可分的情形，可以并行执行各个子问题的求解。而且，该算法采用了比较松弛的不精确准则，可以自适应的选定合适的步长，这对于现存的一些分裂算法，比如交替方向法需要经验选取步长相比，无疑是一个更贴合实际的进步。4.分析了预条件交替方向法求解二次规划问题的渐进敛散性；并结合了SOR松弛的思想。 Glowinski 于1984年在他的专著Numerical Methods for Nonlinear Variational Problems中提出对于带松弛因子的交替方向法，是否可以将松弛因子的范围从(0,\frac{1+\sqrt{5}}{2})扩展到区间(0,2)，却仍然具有全局收敛性的公开问题。我们证明了当交替方向法求解线性约束的二次规划问题时，该松弛因子的范围可以取(0,2)，并且仍然具有全局收敛性。并且分析了其线性收敛性。所以，我们部分回答了Glowinski提出的公开问题。.