×

zbMATH — the first resource for mathematics

A primal-dual prediction-correction algorithm for saddle point optimization. (English) Zbl 1356.90160
Summary: In this paper, we introduce a new primal-dual prediction-correction algorithm for solving a saddle point optimization problem, which serves as a bridge between the algorithms proposed in [X. Cai et al., J. Glob. Optim. 57, No. 4, 1419–1428 (2013; Zbl 1282.90232)] and [B. He and X. Yuan, SIAM J. Imaging Sci. 5, No. 1, 119–149 (2012; Zbl 1250.90066)]. An interesting byproduct of the proposed method is that we obtain an easily implementable projection-based primal-dual algorithm, when the primal and dual variables belong to simple convex sets. Moreover, we establish the worst-case \(\mathcal O(1/t)\) convergence rate result in an ergodic sense, where \(t\) represents the number of iterations.

MSC:
90C47 Minimax problems in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Arrow, K., Hurwicz, L., Uzawa, H.: With contributions by H.B. Chenery, S.M. Johnson, S. Karlin, T. Marschak, and R.M. Solow. Studies in Linear and Non-Linear Programming. Stanford Mathematical Studies in the Social Sciences, vol. II. Stanford Unversity Press, Stanford (1958) · Zbl 1303.90080
[2] Cai, X; Han, D; Xu, L, An improved first-order primal-dual algorithm with a new correction step, J. Glob. Optim., 57, 1419-1428, (2013) · Zbl 1282.90232
[3] Chambolle, A., Pock, T.: On the ergodic convergence rates of a first order primal dual algorithm. Math. Program. Ser. A. doi:10.1007/s10107-015-0957-3 · Zbl 1350.49035
[4] Chambolle, A; Pock, T, A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vis., 40, 120-145, (2011) · Zbl 1255.68217
[5] Chen, Y; Lan, G; Ouyang, Y, Optimal primal dual methods for a class of saddle point problems, SIAM J. Optim., 24, 1779-1814, (2014) · Zbl 1329.90090
[6] Esser, E; Zhang, X; Chan, T, A general framework for a class of first-order primal-dual algorithms for convex optimization in imaging sciences, SIAM J. Imaging Sci., 3, 1015-1046, (2010) · Zbl 1206.90117
[7] Goldstein, T., Li, M., Yuan, X., Esser, E., Baraniuk, R.: Adaptive primal-dual hybrid gradient methods for saddle point problems (2015). arXiv:1305.0546v2 · Zbl 1282.90232
[8] Gu, G; He, B; Yuan, X, Customized proximal point algorithms for linearly constrained convex minimization and saddle-point problems: a uniform approach, Comput. Optim. Appl., 59, 135-161, (2014) · Zbl 1303.90080
[9] Han, D; Xu, W; Yang, H, An operator splitting method for variational inequalities with partially unknown mappings, Numer. Math., 111, 207-237, (2008) · Zbl 1159.65069
[10] He, B; Yuan, X, Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective, SIAM J. Imaging Sci., 5, 119-149, (2012) · Zbl 1250.90066
[11] He, BS; You, Y; Yuan, XM, On the convergence of primal dual hybrid gradient algorithm, SIAM J. Imaging Sci., 7, 2526-2537, (2015) · Zbl 1308.90129
[12] Komodakis, N; Pesquet, JC, Playing with duality: an overview of recent primal dual approaches for solving large scale optimization problems, IEEE Signal Process Mag., 32, 31-54, (2015)
[13] Nemirovski, A, Prox-method with rate of convergence \({O}(1/t)\) for variational inequalities with Lipschitz continuous monotone operator and smooth convex-concave saddle point problems, SIAM J. Optim., 15, 229-251, (2004) · Zbl 1106.90059
[14] Tian, W., Yuan, X.: Linearized primal-dual methods for linear inverse problems with total variation regularization and finite element discretization, Working Paper (2015). http://www.math.hkbu.edu.hk/ xmyuan/Paper/LPD-TV-June19.pdf
[15] Zhu, M., Chan, T.: An Efficient Primal-Dual Hybrid Gradient Algorithm for Total Variation Image Restoration. CAM Reports 08-34, UCLA (2008) · Zbl 1106.90059
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.