Optimization Online


Inertial primal-dual algorithms for structured convex optimization

Raymond Chan(rchan***at***math.cuhk.edu.hk)
Shiqian Ma(sqma***at***se.cuhk.edu.hk)
Junfeng Yang(jfyang***at***nju.edu.cn)

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.

Keywords: structured convex optimization, primal-dual algorithm, inertial primal-dual algorithm, linearized alternating direction method of multipliers, proximal point method, total variation, image reconstruction

Category 1: Convex and Nonsmooth Optimization

Citation: Raymond H. Chan, S. Q. Ma, and J. F. Yang, Inertial primal-dual algorithms for structured convex optimization, Technical Report TR14-67, Department of Mathematics, Nanjing University.

Download: [PDF]

Entry Submitted: 09/10/2014
Entry Accepted: 09/10/2014
Entry Last Modified: 09/10/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society