×

On some steplength approaches for proximal algorithms. (English) Zbl 1338.90464

Summary: We discuss a number of novel steplength selection schemes for proximal-based convex optimization algorithms. In particular, we consider the problem where the Lipschitz constant of the gradient of the smooth part of the objective function is unknown. We generalize two optimization algorithms of Khobotov type and prove convergence. We also take into account possible inaccurate computation of the proximal operator of the non-smooth part of the objective function. Secondly, we show convergence of an iterative algorithm with Armijo-type steplength rule, and discuss its use with an approximate computation of the proximal operator. Numerical experiments show the efficiency of the methods in comparison to some existing schemes.

MSC:

90C56 Derivative-free methods and methods using generalized derivatives
65K10 Numerical optimization and variational techniques

Software:

UNLocBoX; SPIRAL
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Bach, F.; Jenatton, R.; Mairal, J.; Obozinski, G., Optimization with sparsity-inducing penalties, Found. Trends Mach. Learn., 4, 1-106 (2011) · Zbl 06064248
[2] 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-222 (2011)
[3] Combettes, P. L.; Pesquet, J.-C., Proximal splitting methods in signal processing, (Bauschke, H. H.; Burachik, R. S.; Combettes, P. L.; Elser, V.; Luke, D. R.; Wolkowicz, H., Fixed-Point Algorithms for Inverse Problems in Science and Engineering (2011), Springer: Springer Berlin), 185-212 · Zbl 1242.90160
[4] Parikh, N.; Boyd, S., Proximal algorithms, Found. Trends Optim., 1, 123-231 (2014)
[5] Khobotov, E. N., Modification of the extragradient method for solving variational inequalities and certain optimization problems, USSR Comput. Math. Phys., 27, 120-127 (1987) · Zbl 0665.90078
[6] Korpelevich, G., The extragradient method for finding saddle points and other problems, Ekonomika i Matematicheskie Metody, 12, 747-756 (1976) · Zbl 0342.90044
[7] Bertsekas, D. P., Nonlinear Programming (1999), Athena Scientific · Zbl 1015.90077
[8] Bonettini, S.; Ruggiero, V., An alternating extragradient method for total variation based image restoration from Poisson data, Inverse Probl., 27, 095001 (2011) · Zbl 1252.94008
[9] Huang, Y.; Dong, Y., New properties of forward-backward splitting and a practical proximal-descent algorithm, Appl. Math. Comput., 237, 60-68 (2014) · Zbl 1336.65101
[10] Tseng, P.; Yun, S., A coordinate gradient descent method for nonsmooth separable minimization, Math. Program. Ser. B, 117, 387-423 (2009) · Zbl 1166.90016
[12] Figueiredo, M.; Nowak, R., Wavelet-based image estimation: an empirical Bayes’ approach using Jeffreys’ noninformative prior, IEEE Trans. Image Process., 10, 1322-1331 (2001) · Zbl 1037.68775
[13] Rudin, L. I.; Osher, S.; Fatemi, E., Nonlinear total variation based noise removal algorithms, Phys. D, 60, 259-268 (1992) · Zbl 0780.49028
[14] Raginsky, M.; Willett, R.; Harmany, Z.; Marcia, R., Compressed sensing performance bounds under Poisson noise, IEEE Trans. Signal Process., 58, 3990-4002 (2010) · Zbl 1392.94417
[15] Harmany, Z.; Marcia, R.; Willett, R., This is SPIRAL-TAP: sparse poisson intensity reconstruction algorithms—theory and practice, IEEE Trans. Image Process., 21, 1084-1096 (2012) · Zbl 1372.94381
[16] Bertero, M.; Boccacci, P., Introduction to Inverse Problems in Imaging (1998), Institute of Physics Publishing: Institute of Physics Publishing Bristol · Zbl 0914.65060
[18] Geman, S.; German, D., Stochastic relaxation, Gibbs distribution and the Bayesian restoration of images, IEEE Trans. Pattern Anal. Mach. Intell., 6, 721-741 (1984) · Zbl 0573.62030
[19] Combettes, P. L.; Wajs, V. R., Signal recovery by proximal forward-backward splitting multiscale model, Multiscale Model. Simul., 4, 1168-1200 (2005) · Zbl 1179.94031
[20] Moreau, J. J., Proximité et dualité dans un espace hilbertien, Bull. Soc. Math. France, 93, 273-299 (1965) · Zbl 0136.12101
[21] Beck, A.; Teboulle, M., A fast iterative shrinkage-threshold algorithm for linear inverse problems, SIAM J. Imaging Sci., 2, 183-202 (2009) · Zbl 1175.94009
[22] Beck, A.; Teboulle, M., Gradient-based algorithms with applications to signal recovery problems, (Palomar, D.; Eldar, Y., Convex Optimization in Signal Processing and Communications (2010), Cambridge University Press), 42-88 · Zbl 1211.90290
[23] Iusem, A., Augmented Lagrangian methods and proximal point methods for convex optimization, Investigación Operativa, 8, 11-49 (1999)
[24] Lemaire, B., The proximal algorithm, Int. Ser. Numer. Math., 73-87 (1989) · Zbl 0692.90079
[25] Marcotte, P., Application of Khobotov’s algorithm to variational inequalities and network equilibrium problems, INFOR., 29, 258-270 (1991) · Zbl 0781.90086
[27] Barzilai, J.; Borwein, J., Two point step size gradient methods, IMA J. Numer. Anal., 8, 141-148 (1988) · Zbl 0638.65055
[28] Zhou, B.; Gao, L.; Dai, Y. H., Gradient methods with adaptive step-sizes, Comput. Optim. Appl., 35, 69-86 (2006) · Zbl 1121.90099
[29] Osher, S.; Rudin, L.; Fatemi, E., Nonlinear total variation based noise removal algorithms, Phys. D, 60, 259-268 (1992) · Zbl 0780.49028
[30] Alliney, S., An algorithm for the minimization of mixed l1 and l2 norms with application to bayesian estimation, IEEE Signal Processing, 42, 618-627 (1994)
[31] Osher, S.; Solè, A.; Vese, L., Image decomposition and restoration using total variation minimization and the h1 norm, SIAM Multiscale Model. Simul., 1, 349-370 (2003) · Zbl 1051.49026
[32] Chambolle, A., An algorithm for total variation minimization and applications, J. Math. Imaging Vis., 20, 89-97 (2004) · Zbl 1366.94048
[33] Willett, R. M.; Novak, R., Platelets: a multiscale approach for recovering edges and surfaces in photon limited medical imaging, IEEE Trans. Med. Imaging, 22, 332-350 (2003)
[34] Combettes, P. L., Quasi-Fejérian analysis of some optimization algorithms, Parallel Algorithms for Feasibility and Optimization (2001), Elsevier: Elsevier New York · Zbl 0992.65065
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.