论文标题
鞍点问题的对称原始偶偶有算法框架
A symmetric primal-dual algorithmic framework for saddle point problems
论文作者
论文摘要
在本文中，我们为一类凸孔式马鞍点问题提出了一种新的原始二重式算法框架，通常是由图像处理和机器学习引起的。我们的算法框架更新了双重变量的两次计算之间的原始变量，从而出现了对称迭代方案，因此，该方案称为对称性原始偶发算法（SPIDA）。值得注意的是，我们Spida的子问题配备了Bregman近端正规化术语，这使Spida具有多种多权性，因为它拥有一个算法的框架，可以理解某些现有算法的迭代方案，例如经典的lagrangian linangian linangian linangian linanearealization Alm和jacobian for linangian linearized Alm，jacobian forlmian and linearized Alm，jacobian climections，以及问题。此外，我们的算法框架使我们能够得出一些自定义版本，从而使Spida尽可能有效地用于结构化优化问题。从理论上讲，在某些温和条件下，我们证明了SPIDA的全局收敛性，并估算了由Bregman距离定义的广义误差结合条件下的线性收敛速率。最后，基于追求，健壮的主成分分析和图像恢复的一系列数值实验表明，我们的SPIDA在合成和现实世界数据集上很好地效果很好。
In this paper, we propose a new primal-dual algorithmic framework for a class of convex-concave saddle point problems frequently arising from image processing and machine learning. Our algorithmic framework updates the primal variable between the twice calculations of the dual variable, thereby appearing a symmetric iterative scheme, which is accordingly called the symmetric primal-dual algorithm (SPIDA). It is noteworthy that the subproblems of our SPIDA are equipped with Bregman proximal regularization terms, which make SPIDA versatile in the sense that it enjoys an algorithmic framework to understand the iterative schemes of some existing algorithms, such as the classical augmented Lagrangian method (ALM), linearized ALM, and Jacobian splitting algorithms for linearly constrained optimization problems. Besides, our algorithmic framework allows us to derive some customized versions so that SPIDA works as efficiently as possible for structured optimization problems. Theoretically, under some mild conditions, we prove the global convergence of SPIDA and estimate the linear convergence rate under a generalized error bound condition defined by Bregman distance. Finally, a series of numerical experiments on the basis pursuit, robust principal component analysis, and image restoration demonstrate that our SPIDA works well on synthetic and real-world datasets.
