×

zbMATH — the first resource for mathematics

A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms. (English) Zbl 1272.90110
Summary: We propose a new first-order splitting algorithm for solving jointly the primal and dual formulations of large-scale convex minimization problems involving the sum of a smooth function with Lipschitzian gradient, a nonsmooth proximable function, and linear composite functions. This is a full splitting approach, in the sense that the gradient and the linear operators involved are applied explicitly without any inversion, while the nonsmooth functions are processed individually via their proximity operators. This work brings together and notably extends several classical splitting schemes, like the forward-backward and Douglas-Rachford methods, as well as the recent primal-dual method of Chambolle and Pock designed for problems with linear composite terms.

MSC:
90C48 Programming in abstract spaces
90C25 Convex programming
Software:
UNLocBoX; TFOCS
PDF BibTeX Cite
Full Text: DOI
References:
[1] Sidky, E.Y.; Jørgensen, J.H.; Pan, X., Convex optimization problem prototyping for image reconstruction in computed tomography with the chambolle-pock algorithm, Phys. Med. Biol., 57, 3065-3091, (2012)
[2] Mercier, B.: Topics in Finite Element Solution of Elliptic Problems. Lectures on Mathematics, vol. 63. Tata Institute of Fundamental Research, Bombay (1979) · Zbl 0445.65100
[3] Lions, P.L.; Mercier, B., Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal., 16, 964-979, (1979) · Zbl 0426.65050
[4] Passty, G.B., Ergodic convergence to a zero of the sum of monotone operators in Hilbert space, J. Math. Anal. Appl., 72, 383-390, (1979) · Zbl 0428.47039
[5] Eckstein, J.: Splitting methods for monotone operators with applications to parallel optimization. Ph.D. Thesis, MIT, Cambridge, MA (1989) · Zbl 0949.90095
[6] Eckstein, J.; Bertsekas, D.P., On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., 55, 293-318, (1992) · Zbl 0765.90073
[7] Combettes, P., Solving monotone inclusions via compositions of nonexpansive averaged operators, Optimization, 53, 475-504, (2004) · Zbl 1153.47305
[8] Moreau, J.J.: Fonctions convexes duales et points proximaux dans un espace hilbertien. C. R. Math. Acad. Sci. 255, 2897-2899 (1962) · Zbl 0118.10502
[9] Combettes, P.L.; Pesquet, J.C.; Bauschke, H.H. (ed.); Burachik, R. (ed.); Combettes, P.L. (ed.); Elser, V. (ed.); Luke, D.R. (ed.); Wolkowicz, H. (ed.), Proximal splitting methods in signal processing, (2010), New York
[10] Goldstein, T.; Osher, S., The split Bregman method for L1-regularized problems, SIAM J. Imaging Sci., 2, 323-343, (2009) · Zbl 1177.65088
[11] Chambolle, A.; Caselles, V.; Cremers, D.; Novaga, M.; Pock, T., An introduction to total variation for image analysis, No. 9, 263-340, (2010), Berlin · Zbl 1209.94004
[12] Becker, S.; Candès, E.; Grant, M., Templates for convex cone problems with applications to sparse signal recovery, Math. Program. Comput., 3, 165-218, (2011) · Zbl 1257.90042
[13] Monteiro, R.D.C., Svaiter, B.F.: Iteration-complexity of block-decomposition algorithms and the alternating minimization augmented Lagrangian method (2010). Preprint, submitted to Math. Program. · Zbl 1206.90117
[14] 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
[15] Esser, E.; Zhang, X.; Chan, T., A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science, SIAM J. Imaging Sci., 3, 1015-1046, (2010) · Zbl 1206.90117
[16] Zhang, X.; Burger, M.; Osher, S., A unified primal-dual algorithm framework based on Bregman iteration, J. Sci. Comput., 46, 20-46, (2010) · Zbl 1227.65052
[17] He, B.S.; Yuan, X.M., 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
[18] Pesquet, J.C.; Pustelnik, N., A parallel inertial proximal optimization method, Pac. J. Optim., 8, 273-305, (2012) · Zbl 1259.47080
[19] Briceño-Arias, L.M.; Combettes, P.L., A monotone + skew splitting model for composite monotone inclusions in duality, SIAM J. Optim., 21, 1230-1250, (2011) · Zbl 1239.47053
[20] Combettes, P.L.; Dũng, D.; Vũ, B.C., Proximity for sums of composite functions, J. Math. Anal. Appl., 380, 680-688, (2011) · Zbl 1223.47120
[21] Combettes, P.L.; Pesquet, J.C., Primal-dual splitting algorithm for solving inclusions with mixtures of composite, Lipschitzian, and parallel-sum type monotone operators, Set-Valued Var. Anal., 20, 307-330, (2012) · Zbl 1284.47043
[22] Svaiter, B.F., On weak convergence of the Douglas-Rachford method, SIAM J. Control Optim., 49, 280-287, (2011) · Zbl 1220.47064
[23] Raguet, H., Fadili, J., Peyré, G.: Generalized forward-backward splitting (2011). Preprint. arXiv:1108.4404 · Zbl 0823.90097
[24] Vũ, B.C.: A splitting algorithm for dual monotone inclusions involving cocoercive operators. Adv. Comput. Math. (2011, to appear). Preprint. arXiv:1110.1697. doi:10.1007/s10444-011-9254-8 · Zbl 0127.28309
[25] Gabay, D.; Fortin, M. (ed.); Glowinski, R. (ed.), Applications of the method of multipliers to variational inequalities, Amsterdam, Netherlands
[26] Tseng, P., Applications of splitting algorithm to decomposition in convex programming and variational inequalities, SIAM J. Control Optim., 29, 119-138, (1991) · Zbl 0737.90048
[27] Chen, H.G.: Forward-backward splitting techniques: theory and applications. Ph.D. Thesis, University of Washington, Seattle, WA (1994)
[28] Combettes, P.L.; Wajs, V.R., Signal recovery by proximal forward-backward splitting, Multiscale Model. Simul., 4, 1168-1200, (2005) · Zbl 1179.94031
[29] Rockafellar, R.T.: Conjugate Duality and Optimization. SIAM, Philadelphia (1974) · Zbl 0296.90036
[30] Robinson, S.M., Composition duality and maximal monotonicity, Math. Program., 85, 1-13, (1999) · Zbl 0949.90095
[31] Pennanen, T., Dualization of generalized equations of maximal monotone type, SIAM J. Optim., 10, 809-835, (2000) · Zbl 0963.90070
[32] Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, New York (2011) · Zbl 1218.47001
[33] Rockafellar, R.T., Minimax theorems and conjugate saddle-functions, Math. Scand., 14, 151-173, (1964) · Zbl 0127.28309
[34] McLinden, L., An extension of fenchel’s duality theorem to saddle functions and dual minimax problems, Pac. J. Math., 50, 135-158, (1974) · Zbl 0245.90032
[35] Chaux, C.; Pesquet, J.C.; Pustelnik, N., Nested iterative algorithms for convex constrained image recovery problems, SIAM J. Imaging Sci., 2, 730-762, (2009) · Zbl 1186.68520
[36] Dupé, F.X.; Fadili, M.J.; Starck, J.L., A proximal iteration for deconvolving Poisson noisy images using sparse representations, IEEE Trans. Image Process., 18, 310-321, (2009) · Zbl 1371.94117
[37] Fadili, J.M.; Peyré, G., Total variation projection with first order schemes, IEEE Trans. Image Process., 20, 657-669, (2011) · Zbl 1372.94077
[38] Chen, G.; Teboulle, M., A proximal-based decomposition method for convex minimization problems, Math. Program., 64, 81-101, (1994) · Zbl 0823.90097
[39] Ogura, N.; Yamada, I., Non-strictly convex minimization over the fixed point set of an asymptotically shrinking nonexpansive mapping, Numer. Funct. Anal. Optim., 23, 113-137, (2002) · Zbl 1178.90346
[40] Polyak, B.T.: Introduction to Optimization. Optimization Software, Inc., Publications Division, New York, USA (1987) · Zbl 0708.90083
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.