×

Composite optimization by nonconvex majorization-minimization. (English) Zbl 1419.90089

Summary: The minimization of a nonconvex composite function can model a variety of imaging tasks. A popular class of algorithms for solving such problems are majorization-minimization techniques which iteratively approximate the composite nonconvex function by a majorizing function that is easy to minimize. Most techniques, e.g., gradient descent, utilize convex majorizers in order to guarantee that the majorizer is easy to minimize. In our work we consider a natural class of nonconvex majorizers for these functions, and show that these majorizers are still sufficient for a globally convergent optimization scheme. Numerical results illustrate that by applying this scheme, one can often obtain superior local optima compared to previous majorization-minimization methods, when the nonconvex majorizers are solved to global optimality. Finally, we illustrate the behavior of our algorithm for depth superresolution from raw time-of-flight data.

MSC:

90C26 Nonconvex programming, global optimization
90C06 Large-scale problems in mathematical programming
68U10 Computing methodologies for image processing
32B20 Semi-analytic sets, subanalytic sets, and generalizations
65K10 Numerical optimization and variational techniques
47J06 Nonlinear ill-posed problems

Software:

Adam; MCS; INTOPT_90; ASA; iPiano
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] G. Alberti, G. Bouchitté, and G. Dal Maso, {\it The calibration method for the Mumford-Shah functional and free-discontinuity problems}, Calc. Var. Partial Differential Equations, 16 (2003), pp. 299-333, . · Zbl 1015.49008
[2] M. Artina, M. Fornasier, and F. Solombrino, {\it Linearly constrained nonsmooth and nonconvex minimization}, SIAM J. Optim., 23 (2013), pp. 1904-1937, . · Zbl 1277.49039
[3] H. Attouch, J. Bolte, and B. F. Svaiter, {\it Convergence of descent methods for semi-algebraic and tame problems: Proximal algorithms, forward\textendashbackward splitting, and regularized Gauss\textendashSeidel methods}, Math. Program., 137 (2013), pp. 91-129, . · Zbl 1260.49048
[4] C. Audet and J. E. Dennis, Jr., {\it Analysis of generalized pattern searches}, SIAM J. Optim., 13 (2002), pp. 889-903, . · Zbl 1053.90118
[5] C. Bardaro, J. Musielak, and G. Vinti, {\it Nonlinear Integral Operators and Applications}, Walter de Gruyter, Berlin, 2003. · Zbl 1030.47003
[6] H. H. Bauschke, J. Bolte, and M. Teboulle, {\it A descent lemma beyond Lipschitz gradient continuity: First-order methods revisited and applications}, Math. Oper. Res., 42 (2017), pp. 330-348, . · Zbl 1364.90251
[7] H. H. Bauschke and J. J. Borwein, {\it Legendre functions and the method of random Bregman projections}, J. Convex Anal., 4 (1997), pp. 27-67. · Zbl 0894.49019
[8] H. H. Bauschke, J. M. Borwein, and P. L. Combettes, {\it Essential smoothness, essential strict convexity, and Legendre functions in Banach spaces}, Commun. Contemp. Math., 03 (2001), pp. 615-647, . · Zbl 1032.49025
[9] A. Beck and M. Teboulle, {\it A fast iterative shrinkage-thresholding algorithm for linear inverse problems}, SIAM J. Imaging Sci., 2 (2009), pp. 183-202, . · Zbl 1175.94009
[10] M. Benning, M. M. Betcke, M. J. Ehrhardt, and C. Schönlieb, {\it Gradient descent in a generalised Bregman distance framework}, in Joint Conference Geometric Numerical Integration and Its Applications, Vol. 74, Melbourne, 2017, MI Lecture Note Kyushu University, Kyushu University, Fukuoka, Japan, 2017, pp. 40-45.
[11] J. Bolte, A. Daniilidis, and A. Lewis, {\it The Łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems}, SIAM J. Optim., 17 (2007), pp. 1205-1223, . · Zbl 1129.26012
[12] J. Bolte, A. Daniilidis, A. Lewis, and M. Shiota, {\it Clarke subgradients of stratifiable functions}, SIAM J. Optim., 18 (2007), pp. 556-572, . · Zbl 1142.49006
[13] J. Bolte and E. Pauwels, {\it Majorization-minimization procedures and convergence of SQP methods for semi-algebraic and tame programs}, Math. Oper. Res., 41 (2016), pp. 442-465, . · Zbl 1338.65156
[14] J. Bolte, S. Sabach, and M. Teboulle, {\it Proximal alternating linearized minimization for nonconvex and nonsmooth problems}, Math. Program., 146 (2014), pp. 459-494, . · Zbl 1297.90125
[15] J. Bolte, S. Sabach, and M. Teboulle, {\it Nonconvex Lagrangian-based optimization: Monitoring schemes and global convergence}, Math. Oper. Res., to appear. · Zbl 1297.90125
[16] J. Bolte, S. Sabach, M. Teboulle, and Y. Vaisbourd, {\it First order methods beyond convexity and Lipschitz gradient continuity with applications to quadratic inverse problems}, SIAM J. Optim., 28 (2018), pp. 2131-2151, . · Zbl 1402.90118
[17] S. Bonettini, I. Loris, F. Porta, and M. Prato, {\it Variable Metric inexact line-search-based methods for nonsmooth optimization}, SIAM J. Optim., 26 (2016), pp. 891-921, . · Zbl 1338.65157
[18] Y. Boykov, O. Veksler, and R. Zabih, {\it Fast approximate energy minimization via graph cuts}, IEEE Trans. Pattern Anal. Mach. Intell., 23 (2001), pp. 1222-1239, .
[19] M. Burger and S. Osher, {\it A guide to the TV zoo}, in PDE based reconstruction methods in imaging, Lecture Notes in Math. 2090, Springer, Cham, Switzerland, 2013. · Zbl 1342.94014
[20] A. Chambolle, D. Cremers, and T. Pock, {\it A convex approach to minimal partitions}, SIAM J. Imaging Sci., 5 (2012), pp. 1113-1158, . · Zbl 1256.49040
[21] A. Chambolle and T. Pock, {\it A first-order primal-dual algorithm for convex problems with applications to imaging}, J. Math. Imaging Vis., 40 (2011), pp. 120-145, . · Zbl 1255.68217
[22] T. F. Chan, S. Esedoglu, and M. Nikolova, {\it Algorithms for finding global minimizers of image segmentation and denoising models}, SIAM J. Appl. Math., 66 (2006), pp. 1632-1648, . · Zbl 1117.94002
[23] G. H-G. Chen and R. T. Rockafellar, {\it Convergence rates in forward-backward splitting}, SIAM J. Optim., 7 (1997), pp. 421-444, . · Zbl 0876.49009
[24] E. Chouzenoux, J.-C. Pesquet, and A. Repetti, {\it Variable metric forward\textendashbackward algorithm for minimizing the sum of a differentiable function and a convex function}, J. Optim. Theory Appl., 162 (2014), pp. 107-132, . · Zbl 1318.90058
[25] D. Drusvyatskiy, {\it Slope and Geometry in Variational Mathematics}, Ph.D. Thesis, Cornell University, Ithaca, NY, 2013.
[26] D. Drusvyatskiy, A. D. Ioffe, and A. S. Lewis, {\it Nonsmooth Optimization Using Taylor-like Models: Error Bounds, Convergence, and Termination Criteria}, preprint, arXiv:1610.03446 [math], 2016, . · Zbl 1459.65083
[27] D. Drusvyatskiy and C. Paquette, {\it Efficiency of minimizing compositions of convex functions and smooth maps}, Math. Comp., to appear. · Zbl 1398.49012
[28] T. Frerix, T. Möllenhoff, M. Moeller, and D. Cremers, {\it Proximal Backpropagation}, preprint, , 2018.
[29] D. Gabay and B. Mercier, {\it A dual algorithm for the solution of nonlinear variational problems via finite element approximation}, Comput. Math. Appl., 2 (1976), pp. 17-40, . · Zbl 0352.65034
[30] D. E. Goldberg, {\it Genetic Algorithms in Search, Optimization and Machine Learning}, Addison-Wesley, Boston, MA, 1989. · Zbl 0721.68056
[31] E. R. Hansen and G. W. Walster, {\it Global optimization using interval analysis}, Monogr. Textb. Pure Appl. Math. 264, 2nd ed., rev. and expanded, Marcel Dekker, New York, revised and expanded ed., 2004. · Zbl 1103.90092
[32] F. Hanzely, P. Richtarik, and L. Xiao, {\it Accelerated Bregman Proximal Gradient Methods for Relatively Smooth Convex Optimization}, preprint, arXiv:1808.03045 [math], 2018, . · Zbl 1473.90114
[33] D. R. Hunter and K. Lange, {\it A tutorial on MM algorithms}, Amer. Statist., 58 (2004), pp. 30-37, .
[34] W. Huyer and A. Neumaier, {\it Global optimization by multilevel coordinate search}, J. Global Optim., 14 (1999), pp. 331-355, . · Zbl 0956.90045
[35] L. Ingber, {\it Adaptive simulated annealing (ASA): Lessons learned}, Control Cybernet., 25 (1996), pp. 33-54. · Zbl 0860.93035
[36] A. D. Ioffe, {\it An invitation to tame optimization}, SIAM J. Optim., 19 (2009), pp. 1894-1917, . · Zbl 1182.90083
[37] H. Ishikawa and D. Geiger, {\it Segmentation by grouping junctions}, in Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR ’98, IEEE Computer Society, Washington, DC, 1998, pp. 125-131.
[38] R. B. Kearfott, {\it Rigorous Global Search: Continuous Problems}, Kluwer, Dordrecht, Netherlands, 1996. · Zbl 0876.90082
[39] J. Kennedy and R. C. Eberhardt, {\it Particle swarm optimization}, in Proceedings of the 1995 IEEE International Conference on Neural Networks, IEEE, Piscataway, NJ, 1995, pp. 1942-1948.
[40] D. P. Kingma and J. Ba, {\it Adam: A Method for Stochastic Optimization}, preprint, , 2014.
[41] V. Kolmogorov and R. Zabin, {\it What energy functions can be minimized via graph cuts?}, IEEE Trans. Pattern Anal. Mach. Intell., 26 (2004), pp. 147-159, .
[42] G. Kuschk and D. Cremers, {\it Fast and accurate large-scale stereo reconstruction using variational methods}, in 2013 IEEE International Conference on Computer Vision Workshops, IEEE, Piscataway, NJ, 2013, pp. 700-707, .
[43] R. Lange, {\it 3D Time-of-Flight Distance Measurement with Custom Solid-State Image Sensors in CMOS/CCD-Technology}, Ph.D. Thesis, University of Siegen, Siegen, Germany, 2000.
[44] E. Laude, T. Möllenhoff, M. Moeller, J. Lellmann, and D. Cremers, {\it Sublabel-accurate convex relaxation of vectorial multilabel energies}, in Computer Vision \textendash ECCV 2016, Lecture Notes in Comput. Sci. 9905, Springer, Cham, Switzerland, 2016, pp. 614-627, .
[45] A. S. Lewis and S. J. Wright, {\it A proximal method for composite minimization}, Math. Program., 158 (2016), pp. 501-546, . · Zbl 1345.49041
[46] M. Lindner and A. Kolb, {\it Lateral and depth calibration of PMFD-distance sensors}, in International Symposium on Visual Computing, Springer, Berlin, 2006, pp. 524-533.
[47] D. G. Luenberger and Y. Ye, {\it Linear and Nonlinear Programming}, 4th ed., Springer, New York, 2015. · Zbl 1207.90003
[48] J. Mairal, {\it Optimization with first-order surrogate functions}, in Proceedings of the 30th International Conference on Machine Learning - Volume 28, ICML’13, Atlanta, GA, 2013, Curran, Red Hook, NY, pp. III-783-III-791.
[49] T. Möllenhoff and D. Cremers, {\it Sublabel-accurate discretization of nonconvex free-discontinuity problems}, in Proceedings of the IEEE International Conference on Computer Vision, IEEE Computer Society, Los Alamitos, CA, 2017, pp. 1183-1191, .
[50] T. Möllenhoff, E. Laude, M. Moeller, J. Lellmann, and D. Cremers, {\it Sublabel-accurate relaxation of nonconvex energies}, in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, IEEE, Piscataway, NJ, 2016, pp. 3948-3956, .
[51] H. Mühlenbein, M. Schomisch, and J. Born, {\it The parallel genetic algorithm as function optimizer}, Parallel Comput., 17 (1991), pp. 619-632, . · Zbl 0735.65040
[52] Y. Nesterov, {\it Introductory Lectures on Convex Optimization}, Appl. Optim. 87, Springer, Boston, MA, 2004. · Zbl 1086.90045
[53] Y. Nesterov, {\it Gradient methods for minimizing composite functions}, Math. Program., 140 (2013), pp. 125-161, . · Zbl 1287.90067
[54] P. Ochs, {\it Unifying Abstract Inexact Convergence Theorems for Descent Methods and Block Coordinate Variable Metric iPiano}, SIAM J. Optim., to appear. · Zbl 1411.32009
[55] P. Ochs, Y. Chen, T. Brox, and T. Pock, {\it iPiano: Inertial proximal algorithm for nonconvex optimization}, SIAM J. Imaging Sci., 7 (2014), pp. 1388-1419, . · Zbl 1296.90094
[56] P. Ochs, A. Dosovitskiy, T. Brox, and T. Pock, {\it An iterated L1 algorithm for non-smooth non-convex optimization in computer vision}, in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), IEEE, Piscataway, NJ, 2013, pp. 1759-1766, .
[57] P. Ochs, A. Dosovitskiy, T. Brox, and T. Pock, {\it On iteratively reweighted algorithms for nonsmooth nonconvex optimization in computer vision}, SIAM J. Imaging Sci., 8 (2015), pp. 331-372, . · Zbl 1326.65078
[58] P. Ochs, J. Fadili, and T. Brox, {\it Non-smooth Non-convex Bregman Minimization: Unification and New Algorithms}, preprint, arXiv:1707.02278 [cs, math], 2017, . · Zbl 1416.49015
[59] E. Pauwels, {\it The value function approach to convergence analysis in composite optimization}, Oper. Res. Lett., 44 (2016), pp. 790-795, . · Zbl 1408.90283
[60] T. Pock, D. Cremers, H. Bischof, and A. Chambolle, {\it Global solutions of variational models with convex regularization}, SIAM J. Imaging Sci., 3 (2010), pp. 1122-1145, . · Zbl 1202.49031
[61] R. Precup, {\it Methods in Nonlinear Integral Equations}, Springer, Dordrecht, Netherlands, 2002. · Zbl 1060.65136
[62] R. T. Rockafellar, {\it Convex Analysis}, Princeton University Press, Princeton, NJ, 1970. · Zbl 0193.18401
[63] R. T. Rockafellar and R. J.-B. Wets, {\it Variational Analysis}, Grundlehren Math. Wiss. 317, 3rd ed., Springer, Berlin, 2009, .
[64] L. I. Rudin, S. Osher, and E. Fatemi, {\it Nonlinear total variation based noise removal algorithms}, Phys. D, 60 (1992), pp. 259-268, . · Zbl 0780.49028
[65] D. Scharstein, H. Hirschmüller, Y. Kitajima, G. Krathwohl, N. Nešić, X. Wang, and P. Westling, {\it High-resolution stereo datasets with subpixel-accurate ground truth}, in Pattern Recognition, Lecture Notes in Comput. Sci. 8753, Springer, Cham, 2014, pp. 31-42, .
[66] O. Scherzer, M. Grasmair, H. Grossauer, M. Haltmeier, and F. Lenzen, {\it Variational Methods in Imaging}, Appl. Math. Sci. 167, Springer, New York, 2009. · Zbl 1177.68245
[67] E. Strekalovskiy, A. Chambolle, and D. Cremers, {\it Convex relaxation of vectorial problems with coupled regularization}, SIAM J. Imaging Sci., 7 (2014), pp. 294-336, . · Zbl 1298.68288
[68] Y. Sun, P. Babu, and D. P. Palomar, {\it Majorization-minimization algorithms in signal processing, communications, and machine learning}, IEEE Trans. Signal Process., 65 (2017), pp. 794-816, . · Zbl 1414.94595
[69] P. D. Tao and L. T. H. An, {\it Convex analysis approach to DC programming: Theory, algorithms and applications}, Acta Math. Vietnam., 22 (1997), pp. 289-355. · Zbl 0895.90152
[70] Z. Ugray, L. Lasdon, J. Plummer, F. Glover, J. Kelly, and R. Martí, {\it Scatter search and local NLP solvers: A multistart framework for global optimization}, INFORMS J. Comput., 19 (2007), pp. 328-340, . · Zbl 1241.90093
[71] T. Valkonen, {\it A primal\textendashdual hybrid gradient method for nonlinear operators with applications to MRI}, Inverse Problems, 30 (2014), 055012, . · Zbl 1310.47081
[72] C. F. J. Wu, {\it On the Convergence properties of the EM algorithm}, Annals Statist., 11 (1983), pp. 95-103, . · Zbl 0517.62035
[73] L. Xiao, F. Heide, M. O’Toole, A. Kolb, M. B. Hullin, K. Kutulakos, and W. Heidrich, {\it Defocus deblurring and superresolution for time-of-flight depth cameras}, in 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), IEEE, Piscataway, NJ, 2015, pp. 2376-2384, .
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.