A Proximal Point Analysis of the Preconditioned Alternating Direction Method of Multipliers
A Proximal Point Analysis of the Preconditioned Alternating Direction Method of Multipliers
复制标题
DOI：
10.1007/s10957-017-1112-5
复制
发表时间：
2017-04
影响因子：
1.9
通讯作者：
K. Bredies;Hongpeng Sun
中科院分区：
文献类型：
--
作者：
K. Bredies;Hongpeng Sun
我们研究了非光滑优化问题的乘子型交替方向法的预处理算法。乘子交替方向法是解决一般约束优化问题的流行一阶方法。然而，它的缺点之一是需要解决隐式子问题。在各种应用中，这些子问题要么很容易解决，要么是线性的，但仍然具有挑战性。我们推导出一个预处理版本，可以对这些线性子问题进行灵活有效的预处理。原始的预处理版本被编写为原始问题的一种新的近点方法，并证明了无限（有限）维希尔伯特空间中的弱（强）收敛性。具有任意数量的内部迭代的各种有效的预处理器可以用于该预处理框架中。此外，还建立了预处理版本和最近引入的用于涉及二次线性项的一般非光滑问题的预处理 Douglas-Rachford 方法之间的联系。该方法应用于全变分去噪问题，其优点在数值实验中得到了体现。
We study preconditioned algorithms of alternating direction method of multipliers type for nonsmooth optimization problems. The alternating direction method of multipliers is a popular first-order method for general constrained optimization problems. However, one of its drawbacks is the need to solve implicit subproblems. In various applications, these subproblems are either easily solvable or linear, but nevertheless challenging. We derive a preconditioned version that allows for flexible and efficient preconditioning for these linear subproblems. The original and preconditioned version is written as a new kind of proximal point method for the primal problem, and the weak (strong) convergence in infinite (finite) dimensional Hilbert spaces is proved. Various efficient preconditioners with any number of inner iterations may be used in this preconditioned framework. Furthermore, connections between the preconditioned version and the recently introduced preconditioned Douglas–Rachford method for general nonsmooth problems involving quadratic–linear terms are established. The methods are applied to total variation denoising problems, and their benefits are shown in numerical experiments.