Approximate Customized Proximal Point Algorithms for Separable Convex Optimization

doi:10.1007/s40305-022-00412-w

Abstract

Abstract: Proximal point algorithm (PPA) is a useful algorithm framework and has good convergence properties. Themain difficulty is that the subproblems usually only have iterative solutions. In this paper, we propose an inexact customized PPA framework for twoblock separable convex optimization problem with linear constraint. We design two types of inexact error criteria for the subproblems. The first one is absolutely summable error criterion, under which both subproblems can be solved inexactly. When one of the two subproblems is easily solved, we propose another novel error criterion which is easier to implement, namely relative error criterion. The relative error criterion only involves one parameter, which is more implementable. We establish the global convergence and sub-linear convergence rate in ergodic sense for the proposed algorithms. The numerical experiments on LASSO regression problems and total variation-based image denoising problem illustrate that our new algorithms outperform the corresponding exact algorithms.

Key words: Inexact criteria, Proximal point algorithm, Alternating direction method of multipliers, Separable convex programming

CLC Number:

Hong-Mei Chen, Xing-Ju Cai, Ling-Ling Xu. Approximate Customized Proximal Point Algorithms for Separable Convex Optimization[J]. Journal of the Operations Research Society of China, 2023, 11(2): 383-408.

TrendMD

References

[1] Tibshirani, R.:Regression shrinkage and selection via the lasso. J. Roy. Statist. Soc. Ser. B 58, 267-288(1996)
[2] Chambolle, A., Lions, P.L.:Image recovery via total variation minimization and related problems. Numer. Math. 76, 167-188(1997)
[3] Rudin, L.I., Osher, S., Fatemi, E.:Nonlinear total variation based noise removal algorithm. Phys. D. 60, 259-268(1992). (Experimental Mathematics:Computational Issues in Nonlinear Science (Los Alamos, NM, 1991))
[4] Cai, J.F., Candès, E.J., Shen, Z.:A singular value thresholding algorithm for matrix completion. SIAM J. Optim. 20, 1956-1982(2010)
[5] Chen, C.H., He, B.S., Yuan, X.M.:Matrix completion via an alternating direction method. IMA J. Numer. Anal. 32, 227-245(2012)
[6] Wang, Y., Yang, J., Yin, W., Zhang, Y.:A new alternating minimization algorithm for total variation image reconstruction. SIAM J. Imaging Sci. 1, 248-272(2008)
[7] Gabay, D., Mercier, B.:A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Comput. Math. Appl. 2, 17-40(1976)
[8] Glowinski, R., Marroco, A.: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. ESAIM Math. Model. Numer. Anal. 9, 41-76(1975)
[9] 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)
[10] He, B., Yuan, X.:On the O(1/n) convergence rate of the Douglas-Rachford alternating direction method. SIAM J. Numer. Anal. 50, 700-709(2012)
[11] Cai, X., Gu, G., He, B., Yuan, X.:A proximal point algorithm revisit on the alternating direction method of multipliers. Sci. China Math. 56, 2179-2186(2013)
[12] Bai, J., Zhang, H., Li, J.:A parameterized proximal point algorithm for separable convex optimization. Optim. Lett. 12, 1589-1608(2018)
[13] Gu, G., He, B., Yuan, X.:Customized proximal point algorithms for linearly constrained convex minimization and saddle-point problems:a unified approach. Comput. Optim. Appl. 59, 135-161(2014)
[14] He, B., Yuan, X., Zhang, W.:A customized proximal point algorithm for convex minimization with linear constraints. Comput. Optim. Appl. 56, 559-572(2013)
[15] Ma, F., Ni, M.:A class of customized proximal point algorithms for linearly constrained convex optimization. Comput. Appl. Math. 37, 896-911(2018)
[16] Rockafellar, R.T.:Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14, 877-898(1976)
[17] Solodov, M.V., Svaiter, B.F.:A hybrid approximate extragradient-proximal point algorithm using the enlargement of a maximal monotone operator. Set-Valued Anal. 7, 323-345(1999)
[18] Solodov, M.V., Svaiter, B.F.:A hybrid projection-proximal point algorithm. J. Convex Anal. 6, 59-70(1999)
[19] Rasch, J., Chambolle, A.:Inexact first-order primal-dual algorithms. Comput. Optim. Appl. 76, 381-430(2020)
[20] Alves, M.M., Eckstein, J., Geremia, M., Melo, J.G.:Relative-error inertial-relaxed inexact versions of Douglas-Rachford and ADMM splitting algorithms. Comput. Optim. Appl. 75, 389-422(2020)
[21] Eckstein, J., Yao, W.:Relative-error approximate versions of Douglas-Rachford splitting and special cases of the ADMM. Math. Program. 170, 417-444(2018)
[22] Lions, P.L., Mercier, B.:Splitting algorithms for the sum of two nonlinear operators. SIAM J. Numer. Anal. 16, 964-979(1979)
[23] Eckstein, J., Yao, W.:Approximate ADMM algorithms derived from Lagrangian splitting. Comput. Optim. Appl. 68, 363-405(2017)
[24] Xie, J.:On inexact ADMMs with relative error criteria. Comput. Optim. Appl. 71, 743-765(2018)
[25] Xie, J., Liao, A., Yang, X.:An inexact alternating direction method of multipliers with relative error criteria. Optim. Lett. 11, 583-596(2017)
[26] Hestenes, M.R.:Multiplier and gradient methods. J. Optim. Theory Appl. 4, 303-320(1969)
[27] Cai, X., Han, D.:O(1/t) complexity analysis of the generalized alternating direction method of multipliers. Sci. China Math. 62, 795-808(2019)
[28] Nocedal, J., Wright, S.J.:Numerical Optimization, Springer Series in Operations Research and Financial Engineering, 2nd edn. Springer, New York (2006)
[29] Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J.:Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn. 3, 1-122(2010)