凸优化分裂收缩算法的统一框架

Many problems in the fields of signal processing, pattern recognition, machine learning, image restoration (including inverse problems in mathematical physics), can be reformulated as large-scale optimization problems with separable structures. With appropriate reconstruction and modeling, a lot of "Big Data" problems can also be reformulated as optimization problems. After years of research and practice, academia has gradually reached a consensus on the use of the first-order method for solving large-scale optimization problems. Over the past few years, for some classic problems emerged in the field of engineering, we proposed a number of basic algorithms and established a unified algorithmic framework by using variational inequalities as a tool. This framework provides an easy access to prove the algorithmic convergence and rate. The improvement on convergence rate relies on the prediction methodology and correction selection. Under the guidance of the unified algorithmic framework, we research on a prediction method to solve the sub-problem easily and a correction step simple to practice so as to speed up the convergence rate.. The objective of this research project is to further systematize the unified algorithmic framework, so that the “splitting contraction methods under the guidance of variational inequalities” becomes well known in both academic and industial fields as “basic methods with high performance in scientific computing”.

信号处理，模式识别，机器学习，图像重建（包括数学物理中反问题研究）等领域的许多问题，往往归结为具有分离结构的大规模优化问题。“大数据”问题中的相当一部分，最后也归结为一个“去伪存真，去粗存精”的优化问题。研究实践对利用一阶方法求解大规模优化问题已渐成共识。过去的几年中，对工程领域中常出现的一些典型问题，我们提出了一些基本算法，并以变分不等式为工具建立了算法的统一框架。这个框架为方法的收敛性以及收敛速率的证明提供了一条简明的途径。而收敛效率的提高，还取决于预测方法和校正过程的选取。我们在统一框架指导下，研究子问题求解简单的预测，和容易实现的校正，以使算法收敛速度提高。 .该项目的研究目标是要进一步使算法框架系统化，做到让《以变分不等式指导下的分裂收缩算法》 成为一个学术界有所耳闻，相关工程界（解决工程问题的学者）乐意采用的 《高性能科学计算的基础算法》。

以交替方向乘子法（ADMM）为代表的分裂收缩方法（简称SCM），被广泛用求解可分离结构凸优化问题。这类算法要求每步迭代成功求解一个“简单”的子问题。在某些实际问题中, 子问题的求解并不那么简单, 因此采取线性化加正则化解决。线性化和正则化是一对矛盾, 线性化使得子问题变得简单, 正则化为保证收敛。为保证理论上收敛, 已有的工作都要求正则化因子能大到保证正定性。这种正则化要求影响了实际收敛速度。该项目的主要成果, 称之为 Positive Indefinite Regularization (不定正则化), 可以对SCM中的一些常用算法中以往认为必要的正则化因子在 0.6--0.8 范围内成比例的缩小, 提高了实际计算的收敛速度, 同时在理论上仍然保证收敛性和 O(1/t) 的迭代复杂性。