Inertial primal-dual algorithms for structured convex optimization

arXiv1409.2992MaRDI QIDQ6254537FDOQ6254537

Authors: Raymond H. Chan, Shiqian Ma, Junfeng Yang 

Publication date: 10 September 2014

Abstract: The primal-dual algorithm recently proposed by Chambolle & Pock (abbreviated as CPA) for structured convex optimization is very efficient and popular. It was shown by Chambolle & Pock in cite{CP11} and also by Shefi & Teboulle in cite{ST14} that CPA and variants are closely related to preconditioned versions of the popular alternating direction method of multipliers (abbreviated as ADM). In this paper, we further clarify this connection and show that CPAs generate exactly the same sequence of points with the so-called linearized ADM (abbreviated as LADM) applied to either the primal problem or its Lagrangian dual, depending on different updating orders of the primal and the dual variables in CPAs, as long as the initial points for the LADM are properly chosen. The dependence on initial points for LADM can be relaxed by focusing on cyclically equivalent forms of the algorithms. Furthermore, by utilizing the fact that CPAs are applications of a general weighted proximal point method to the mixed variational inequality formulation of the KKT system, where the weighting matrix is positive definite under a parameter condition, we are able to propose and analyze inertial variants of CPAs. Under certain conditions, global point-convergence, nonasymptotic $O(1/k)$ and asymptotic $o(1/k)$ convergence rate of the proposed inertial CPAs can be guaranteed, where $k$ denotes the iteration index. Finally, we demonstrate the profits gained by introducing the inertial extrapolation step via experimental results on compressive image reconstruction based on total variation minimization.

This page was built for publication: Inertial primal-dual algorithms for structured convex optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6254537)