×

A customized proximal point algorithm for convex minimization with linear constraints. (English) Zbl 1287.90048

Summary: This paper demonstrates a customized application of the classical proximal point algorithm (PPA) to the convex minimization problem with linear constraints. We show that if the proximal parameter in metric form is chosen appropriately, the application of PPA could be effective to exploit the simplicity of the objective function. The resulting subproblems could be easier than those of the augmented Lagrangian method (ALM), a benchmark method for the model under our consideration. The efficiency of the customized application of PPA is demonstrated by some image processing problems.

MSC:

90C25 Convex programming

Software:

MCALab; PDCO
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Afonso, M., Bioucas-Dias, J., Figueiredo, M.: An augmented Lagrangian approach to the constrained optimization formulation of imaging inverse problems. IEEE Trans. Image Process. 20, 681-695 (2010) · Zbl 1372.94004 · doi:10.1109/TIP.2010.2076294
[2] Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2, 183-202 (2009) · Zbl 1175.94009 · doi:10.1137/080716542
[3] Bertsekas, D.P.: Constrained Optimization and Lagrange Multiplier Method. Academic Press, New York (1982) · Zbl 0572.90067
[4] Blum, E., Oettli, W.: Mathematische Optimierung, Econometrics and Operations Research XX. Springer, Berlin (1975) · Zbl 0315.90062 · doi:10.1007/978-3-642-66156-3
[5] Burke, J.V., Qian, M.J.: A variable metric proximal point algorithm for monotone operators. SIAM J. Control Optim. 37, 353-375 (1998) · Zbl 0918.90112 · doi:10.1137/S0363012992235547
[6] Chambolle, A.: An algorithm for total variation minimization and applications. J. Math. Imaging Vis. 20, 89-97 (2004) · Zbl 1366.94048 · doi:10.1023/B:JMIV.0000011320.81911.38
[7] Chen, S.S., Donoho, D.L., Saunders, M.A.: Atomic decomposition by basis pursuit. SIAM Rev. 43, 129-159 (2001) · Zbl 0979.94010 · doi:10.1137/S003614450037906X
[8] Daubechies, I., Defrise, M., Mol, C.D.: An iterative thresholding algorithm for linear inverse problems with a sparsity constraint. Commun. Pure Appl. Math. 57, 1413-1457 (2004) · Zbl 1077.65055 · doi:10.1002/cpa.20042
[9] Eckstein, J., Bertsekas, D.P.: On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Program., Ser. A 55, 293-318 (1992) · Zbl 0765.90073 · doi:10.1007/BF01581204
[10] Fadili, J., Starck, J.L., Elad, M., Donoho, D.: Mcalab: reproducible research in signal and image decomposition and inpainting. Comput. Sci. Eng. 12(1), 44-63 (2010) · doi:10.1109/MCSE.2010.14
[11] Figueiredo, M.A.T., Nowak, R.D., Wright, S.J.: Gradient projection for sparse reconstruction: application to compressed sensing and other inverse problems. IEEE J. Sel. Top. Signal Process. 1(4), 586-597 (2007) · doi:10.1109/JSTSP.2007.910281
[12] Glowinski, R., Marrocco, A.: Approximation par éléments finis d’ordre un et résolution par pénalisation-dualité d’une classe de problèmes non linéaires. RAIRO. Rech. Opér. R2, 41-76 (1975) · Zbl 0368.65053
[13] Gol’shtein, E.G., Tret’yakov, N.V.: Modified Lagrangian in convex programming and their generalizations. Math. Program. Stud. 10, 86-97 (1979) · Zbl 0404.90069 · doi:10.1007/BFb0120845
[14] Hansen, P., Nagy, J., O’Leary, D.: Deblurring Images: Matrices, Spectra, and Filtering. SIAM, Philadelphia (2006) · Zbl 1112.68127 · doi:10.1137/1.9780898718874
[15] Hestenes, M.R.: Multiplier and gradient methods. J. Optim. Theory Appl. 4, 303-320 (1969) · Zbl 0174.20705 · doi:10.1007/BF00927673
[16] 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 · doi:10.1137/100814494
[17] Malgouyres, F., Guichard, F.: Edge direction preserving image zooming: a mathematical and numerical analysis. SIAM J. Numer. Anal. 39(1), 1-37 (2001) · Zbl 1001.68174 · doi:10.1137/S0036142999362286
[18] Martinet, B.: Regularisation, d’inéquations variationelles par approximations succesives. Rev. Francaise Inf. Rech. Oper. 4, 154-159 (1970) · Zbl 0215.21103
[19] Nocedal, J., Wright, S.J.: Numerical Optimization. Springer, Berlin (1999) · Zbl 0930.65067 · doi:10.1007/b98874
[20] Powell, M. J.D.; Fletcher, R. (ed.), A method for nonlinear constraints in minimization problems, 283-298 (1969), New York
[21] Rockafellar, R.T.: Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 1, 97-116 (1976) · Zbl 0402.90076 · doi:10.1287/moor.1.2.97
[22] Rudin, L., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Physica D 60, 259-268 (1992) · Zbl 0780.49028 · doi:10.1016/0167-2789(92)90242-F
[23] Starck, J.L., Murtagh, F., Fadili, J.M.: Sparse Image and Signal Processing, Wavelets, Curvelets, Morphological Diversity. Cambridge University Press, Cambridge (2010) · Zbl 1196.94008 · doi:10.1017/CBO9780511730344
[24] Weiss, P., Aubert, G., Blanc-Féraud, L.: Some applications of l∞-constraints in image processing. INRIA Research Report (2006) · Zbl 1191.94029
[25] Yin, W., Osher, S., Goldfarb, D., Darbon, J.: Bregman iterative algorithms for l1-minimization with applications to compressed sensing. SIAM J. Imaging Sci. 1, 143-168 (2008) · Zbl 1203.90153 · doi:10.1137/070703983
[26] Zhang, X.Q., Burger, M., Osher, S.: A unified primal-dual algorithm framework based on Bregman iteration. J. Sci. Comput. 46, 20-46 (2011) · Zbl 1227.65052 · doi:10.1007/s10915-010-9408-8
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.