Approximate first-order primal-dual algorithms for saddle point problems

Authors:
Fan Jiang, Xingju Cai, Zhongming Wu and Deren Han

Journal:
Math. Comp. **90** (2021), 1227-1262

MSC (2020):
Primary 65K05, 65K10, 90C25

DOI:
https://doi.org/10.1090/mcom/3610

Published electronically:
February 4, 2021

MathSciNet review:
4232223

Full-text PDF

View in AMS MathViewer

Abstract | References | Similar Articles | Additional Information

Abstract: We propose two approximate versions of the first-order primal-dual algorithm (PDA) to solve a class of convex-concave saddle point problems. The introduced approximate criteria are easy to implement in the sense that they only involve the subgradient of a certain function at the current iterate. The first approximate PDA solves both subproblems inexactly and adopts the absolute error criteria, which are based on non-negative summable sequences. Assuming that one of the PDA subproblems can be solved exactly, the second approximate PDA solves the other subproblem approximately and adopts a relative error criterion. The relative error criterion only involves a single parameter in the range of $[0, 1)$, which makes the method more applicable. For both versions, we establish the global convergence and $O(1/N)$ convergence rate measured by the iteration complexity, where $N$ counts the number of iterations. For the inexact PDA with absolute error criteria, we show the accelerated $O(1/N^2)$ and linear convergence rate under the assumptions that a part of the underlying functions and both underlying functions are strongly convex, respectively. Then, we prove that these inexact criteria can also be extended to solve a class of more general problems. Finally, we perform some numerical experiments on sparse recovery and image processing problems. The results demonstrate the feasibility and superiority of the proposed methods.

- Kenneth J. Arrow, Leonid Hurwicz, and Hirofumi Uzawa,
*Studies in linear and non-linear programming*, Stanford Mathematical Studies in the Social Sciences, II, Stanford University Press, Stanford, Calif., 1958. With contributions by H. B. Chenery, S. M. Johnson, S. Karlin, T. Marschak, R. M. Solow. MR**0108399** - Hédy Attouch, Jérôme Bolte, Patrick Redont, and Antoine Soubeyran,
*Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kurdyka-Łojasiewicz inequality*, Math. Oper. Res.**35**(2010), no. 2, 438–457. MR**2674728**, DOI 10.1287/moor.1100.0449 - Hedy Attouch, Jérôme Bolte, and Benar Fux Svaiter,
*Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods*, Math. Program.**137**(2013), no. 1-2, Ser. A, 91–129. MR**3010421**, DOI 10.1007/s10107-011-0484-9 - Xingju Cai, Deren Han, and Lingling Xu,
*An improved first-order primal-dual algorithm with a new correction step*, J. Global Optim.**57**(2013), no. 4, 1419–1428. MR**3121803**, DOI 10.1007/s10898-012-9999-8 - Antonin Chambolle,
*An algorithm for total variation minimization and applications*, J. Math. Imaging Vision**20**(2004), no. 1-2, 89–97. Special issue on mathematics and image analysis. MR**2049783**, DOI 10.1023/B:JMIV.0000011320.81911.38 - Antonin Chambolle and Thomas Pock,
*A first-order primal-dual algorithm for convex problems with applications to imaging*, J. Math. Imaging Vision**40**(2011), no. 1, 120–145. MR**2782122**, DOI 10.1007/s10851-010-0251-1 - Antonin Chambolle and Thomas Pock,
*On the ergodic convergence rates of a first-order primal-dual algorithm*, Math. Program.**159**(2016), no. 1-2, Ser. A, 253–287. MR**3535925**, DOI 10.1007/s10107-015-0957-3 - Laurent Condat,
*A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms*, J. Optim. Theory Appl.**158**(2013), no. 2, 460–479. MR**3084386**, DOI 10.1007/s10957-012-0245-9 - Yu-Hong Dai and Roger Fletcher,
*Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming*, Numer. Math.**100**(2005), no. 1, 21–47. MR**2129700**, DOI 10.1007/s00211-004-0569-y - Damek Davis and Wotao Yin,
*A three-operator splitting scheme and its optimization applications*, Set-Valued Var. Anal.**25**(2017), no. 4, 829–858. MR**3740519**, DOI 10.1007/s11228-017-0421-z - Jonathan Eckstein and Paulo J. S. Silva,
*A practical relative error criterion for augmented Lagrangians*, Math. Program.**141**(2013), no. 1-2, Ser. A, 319–348. MR**3097289**, DOI 10.1007/s10107-012-0528-9 - Jonathan Eckstein and Wang Yao,
*Approximate ADMM algorithms derived from Lagrangian splitting*, Comput. Optim. Appl.**68**(2017), no. 2, 363–405. MR**3694773**, DOI 10.1007/s10589-017-9911-z - Jonathan Eckstein and Wang Yao,
*Relative-error approximate versions of Douglas-Rachford splitting and special cases of the ADMM*, Math. Program.**170**(2018), no. 2, Ser. A, 417–444. MR**3820481**, DOI 10.1007/s10107-017-1160-5 - Ernie Esser, Xiaoqun Zhang, and Tony F. Chan,
*A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science*, SIAM J. Imaging Sci.**3**(2010), no. 4, 1015–1046. MR**2763706**, DOI 10.1137/09076934X - D. Gabay and B. Mercier,
*A dual algorithm for the solution of nonlinear variational problems via finite element approximation*, Comput. Math. Appl.**2**, pp. 17–40 (1976) - R. Glowinski and A. Marrocco,
*Sur l’approximation, par éléments finis d’ordre un, et la résolution, par pénalisation-dualité, d’une classe de problèmes de Dirichlet non linéaires*, Rev. Française Automat. Informat. Recherche Opérationnelle Sér. Rouge Anal. Numér.**9**(1975), no. R-2, 41–76 (French, with English summary). MR**388811** - T. Goldstein, M. Li, and X.M. Yuan,
*Adaptive primal-dual splitting methods for statistical learning and image processing*, In Advances in Neural Information Processing Systems., pp. 2089–2097 (2015) - Deren Han, Hongjin He, Hai Yang, and Xiaoming Yuan,
*A customized Douglas-Rachford splitting algorithm for separable convex minimization with linear constraints*, Numer. Math.**127**(2014), no. 1, 167–200. MR**3191219**, DOI 10.1007/s00211-013-0580-2 - Bingsheng He and Xiaoming Yuan,
*Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective*, SIAM J. Imaging Sci.**5**(2012), no. 1, 119–149. MR**2902659**, DOI 10.1137/100814494 - Bingsheng He, Yanfei You, and Xiaoming Yuan,
*On the convergence of primal-dual hybrid gradient algorithm*, SIAM J. Imaging Sci.**7**(2014), no. 4, 2526–2537. MR**3284566**, DOI 10.1137/140963467 - Bingsheng He, Feng Ma, and Xiaoming Yuan,
*An algorithmic framework of generalized primal–dual hybrid gradient methods for saddle point problems*, J. Math. Imaging Vision**58**(2017), no. 2, 279–293. MR**3636590**, DOI 10.1007/s10851-017-0709-5 - Hongjin He, Jitamitra Desai, and Kai Wang,
*A primal-dual prediction-correction algorithm for saddle point optimization*, J. Global Optim.**66**(2016), no. 3, 573–583. MR**3557424**, DOI 10.1007/s10898-016-0437-1 - L.T.K. Hien, R.B. Zhao, and W.B. Haskell,
*An inexact primal-dual smoothing framework for large-scale non-bilinear saddle point problems*, arXiv preprint arXiv:1711.03669. (2017) - G. M. Korpelevič,
*An extragradient method for finding saddle points and for other problems*, Èkonom. i Mat. Metody**12**(1976), no. 4, 747–756 (Russian). MR**451121** - P.-L. Lions and B. Mercier,
*Splitting algorithms for the sum of two nonlinear operators*, SIAM J. Numer. Anal.**16**(1979), no. 6, 964–979. MR**551319**, DOI 10.1137/0716071 - Yanli Liu, Yunbei Xu, and Wotao Yin,
*Acceleration of primal-dual methods by preconditioning and simple subproblem procedures*, J. Sci. Comput.**86**(2021), no. 2, Paper No. 21, 34. MR**4197401**, DOI 10.1007/s10915-020-01371-1 - Yura Malitsky and Thomas Pock,
*A first-order primal-dual algorithm with linesearch*, SIAM J. Optim.**28**(2018), no. 1, 411–432. MR**3763097**, DOI 10.1137/16M1092015 - Benedetta Morini, Margherita Porcelli, and Raymond H. Chan,
*A reduced Newton method for constrained linear least-squares problems*, J. Comput. Appl. Math.**233**(2010), no. 9, 2200–2212. MR**2577759**, DOI 10.1016/j.cam.2009.10.006 - S. Nam, M. E. Davies, M. Elad, and R. Gribonval,
*The cosparse analysis model and algorithms*, Appl. Comput. Harmon. Anal.**34**(2013), no. 1, 30–56. MR**2981332**, DOI 10.1016/j.acha.2012.03.006 - Jorge Nocedal and Stephen J. Wright,
*Numerical optimization*, 2nd ed., Springer Series in Operations Research and Financial Engineering, Springer, New York, 2006. MR**2244940** - N. Parikh and S. Boyd,
*Proximal algorithms*, Found. Trends Optim.**1**(3), pp. 127–239 (2014) - F. Pedregosa and G. Gidel,
*Adaptive three operator splitting*, Proceedings of the 35th ICML, pp. 4085–4094 (2018) - Julian Rasch and Antonin Chambolle,
*Inexact first-order primal-dual algorithms*, Comput. Optim. Appl.**76**(2020), no. 2, 381–430. MR**4098836**, DOI 10.1007/s10589-020-00186-y - Leonid I. Rudin, Stanley Osher, and Emad Fatemi,
*Nonlinear total variation based noise removal algorithms*, Phys. D**60**(1992), no. 1-4, 259–268. Experimental mathematics: computational issues in nonlinear science (Los Alamos, NM, 1991). MR**3363401**, DOI 10.1016/0167-2789(92)90242-F - R. Tyrrell Rockafellar,
*Convex analysis*, Princeton Mathematical Series, No. 28, Princeton University Press, Princeton, N.J., 1970. MR**0274683** - M. V. Solodov and B. F. Svaiter,
*A hybrid projection-proximal point algorithm*, J. Convex Anal.**6**(1999), no. 1, 59–70. MR**1713951** - M. V. Solodov and B. F. Svaiter,
*Error bounds for proximal point subproblems and associated inexact proximal point algorithms*, Math. Program.**88**(2000), no. 2, Ser. B, 371–389. Error bounds in mathematical programming (Kowloon, 1998). MR**1783979**, DOI 10.1007/s101070050022 - B\brevgrv{a}ng Công Vũ,
*A splitting algorithm for dual monotone inclusions involving cocoercive operators*, Adv. Comput. Math.**38**(2013), no. 3, 667–681. MR**3037034**, DOI 10.1007/s10444-011-9254-8 - Jiaxin Xie, Anping Liao, and Xiaobo Yang,
*An inexact alternating direction method of multipliers with relative error criteria*, Optim. Lett.**11**(2017), no. 3, 583–596. MR**3610244**, DOI 10.1007/s11590-016-1021-9 - Jiaxin Xie,
*On inexact ADMMs with relative error criteria*, Comput. Optim. Appl.**71**(2018), no. 3, 743–765. MR**3877604**, DOI 10.1007/s10589-018-0022-2 - Ming Yan,
*A new primal-dual algorithm for minimizing the sum of three functions with a linear operator*, J. Sci. Comput.**76**(2018), no. 3, 1698–1717. MR**3833707**, DOI 10.1007/s10915-018-0680-3 - Xiaoqun Zhang, Martin Burger, and Stanley Osher,
*A unified primal-dual algorithm framework based on Bregman iteration*, J. Sci. Comput.**46**(2011), no. 1, 20–46. MR**2753250**, DOI 10.1007/s10915-010-9408-8 - Zhao Tan, Yonina C. Eldar, Amir Beck, and Arye Nehorai,
*Smoothing and decomposition for analysis sparse recovery*, IEEE Trans. Signal Process.**62**(2014), no. 7, 1762–1774. MR**3189405**, DOI 10.1109/TSP.2014.2304932 - M.Q. Zhu and T.F. Chan,
*An efficient primal-dual hybrid gradient algorithm for total variation image restoration*, UCLA CAM Report. (2008)

Retrieve articles in *Mathematics of Computation*
with MSC (2020):
65K05,
65K10,
90C25

Retrieve articles in all journals with MSC (2020): 65K05, 65K10, 90C25

Additional Information

**Fan Jiang**

Affiliation:
School of Mathematical Sciences, Jiangsu Key Lab for NSLSCS, Nanjing Normal University, Nanjing 210023, People’s Republic of China

MR Author ID:
1266812

Email:
15905154902@163.com

**Xingju Cai**

Affiliation:
School of Mathematical Sciences, Jiangsu Key Lab for NSLSCS, Nanjing Normal University, Nanjing 210023, People’s Republic of China

ORCID:
0000-0002-6957-477X

Email:
caixingju@njnu.edu.cn

**Zhongming Wu**

Affiliation:
School of Management Science and Engineering, Nanjing University of Information Science and Technology, Nanjing 210044, People’s Republic of China

MR Author ID:
1246723

Email:
wuzm@nuist.edu.cn

**Deren Han**

Affiliation:
LMIB, School of Mathematical Sciences, Beihang University, Beijing 100191, People’s Republic of China

MR Author ID:
664477

Email:
handr@buaa.edu.cn

Keywords:
First-order primal-dual algorithm,
saddle point problems,
convex optimization,
inexact criteria,
global convergence

Received by editor(s):
June 16, 2019

Received by editor(s) in revised form:
March 14, 2020, May 28, 2020, and October 5, 2020

Published electronically:
February 4, 2021

Additional Notes:
The first author was supported by the Postgraduate Research & Practice Innovation Program of Jiangsu Province (No. KYCX20_1163). The second author was partially supported by the Natural Science Foundation of China (Nos. 11871279, 11571178). The third author was partially supported by the Natural Science Foundation of China (No. 12001286) and the Startup Foundation for Introducing Talent of NUIST (No. 2020r003). The fourth author was partially supported by the Natural Science Foundation of China (Nos. 11625105, 11926358).

Article copyright:
© Copyright 2021
American Mathematical Society