# A new primal-dual algorithm for minimizing the sum of three functions with a linear operator

arXiv: https://arxiv.org/abs/1611.09805 · HTML: https://mlsanity.com/paper/1611.09805/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Nov 2016.

## Built on by (most cited first, 9 of 9)

- [Adaptive proximal algorithms for convex optimization under local Lipschitz continuity of the gradient](https://mlsanity.com/paper/2301.04431/) (2023)
- [Decentralized Composite Optimization with Compression](https://mlsanity.com/paper/2108.04448/) (2021)
- [DISA: A Dual Inexact Splitting Algorithm for Distributed Convex Composite Optimization](https://mlsanity.com/paper/2209.01850/) (2022)
- [Decentralized Inexact Proximal Gradient Method With Network-Independent Stepsizes for Convex Composite Optimization](https://mlsanity.com/paper/2302.03238/) (2023)
- [Federated Learning Using Three-Operator ADMM](https://mlsanity.com/paper/2211.04152/) (2022)
- [A primal-dual algorithm for image reconstruction with input-convex neural network regularizers](https://mlsanity.com/paper/2410.12441/) (2024)
- [Stochastic Gradient Methods with Compressed Communication for Decentralized Saddle Point Problems](https://mlsanity.com/paper/2205.14452/) (2022)
- [BALPA: A Balanced Primal-Dual Algorithm for Nonsmooth Optimization with Application to Distributed Optimization](https://mlsanity.com/paper/2212.02835/) (2022)
- [Inverse Covariance and Partial Correlation Matrix Estimation via Joint Partial Regression](https://mlsanity.com/paper/2502.08414/) (2025)

## Abstract (arXiv)

In this paper, we propose a new primal-dual algorithm for minimizing f(x) + g(x) + h(Ax), where f, g, and h are proper lower semi-continuous convex functions, f is differentiable with a Lipschitz continuous gradient, and A 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 and the proximal alternating predictor-corrector when g = 0. 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.