A New Primal–Dual Algorithm for Minimizing the Sum of Three Functions with a Linear Operator

By Ming Yan. 2016

140 citations recorded by the source corpus.

In this paper, we propose a new primal–dual algorithm for minimizing f(x)+g(x)+h(Ax)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f({\mathbf {x}})+g({\mathbf {x}})+h({\mathbf {A}}{\mathbf {x}})$$\end{document}, where f, g, and h are proper lower semi-continuous convex functions, f is differentiable with a Lipschitz continuous gradient, and A\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbf {A}}$$\end{document} is a bounded linear operator. The proposed algorithm has some famous primal–dual algorithms for minimizing the sum of two functions as special cases. E.g., it reduces to the Chambolle–Pock algorithm when f=0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f=0$$\end{document} and the proximal alternating predictor–corrector when g=0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$g=0$$\end{document}. For the general convex case, we prove the convergence of this new algorithm in terms of the distance to a fixed point by showing that the iteration is a nonexpansive operator. In addition, we prove the O(1 / k) ergodic convergence rate in the primal–dual gap. With additional assumptions, we derive the linear convergence rate in terms of the distance to the fixed point. Comparing to other primal–dual algorithms for solving the same problem, this algorithm extends the range of acceptable parameters to ensure its convergence and has a smaller per-iteration cost. The numerical experiments show the efficiency of this algorithm.

Subfields: Computational Mechanics, Computational Theory and Mathematics, Numerical Analysis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computational Theory and Mathematics

In Numerical Analysis

Citations in the corpus

Distributed Fixed Point Methods with Compressed Iterates (2019, methodology): “The PDHG algorithm [7,8], Primal–Dual 3 Operators (PD3O) and Primal–Dual Davis–Yin (PDDY) splitting The PD3O [47] and the PDDY [39] algorithms are similar to the Condat–”
A Decentralized Proximal-Gradient Method With Network Independent Step-Sizes and Separated Convergence Rates (2017, methodology): “As explained in Section II, NIDS is equivalent to the primaldual algorithm [56] applied to problem”
Distributed Proximal Splitting Algorithms with Rates and Acceleration (2020, background): “It turns out that the obtained algorithm is not new but is a nonstationary version of the PD3O algorithm [23].”
Proximal Splitting Algorithms: A Tour of Recent Advances, with New Twists. (2020, methodology): “This analysis is inspired by the one of O’Connor and Vandenberghe [48], showing that the Chambolle– Pock algorithm is a primal–dual Douglas–Rachford algorithm (in a diﬀerent way than in Section 7.1 with 𝑄 = 0, mentioned by Yan [53]).”
Dualize, Split, Randomize: Fast Nonsmooth Optimization Algorithms (2020, methodology): “In this case, by taking κ = 1, we obtain whereas Theorem 3 in [17] provides the rate max Without the smoothness assumption on R , we still guarantee linear convergence for the Stochastic PD3O Algorithm: Theorem 7 ( M strongly monotone) .”