Majorization-Minimization Procedures and Convergence of SQP Methods for Semi-Algebraic and Tame Programs

References

• Absil PA, Mahony R, Andrews B (2005) Convergence of the iterates of descent methods for analytic cost functions. SIAM J. Optim. 16(2):531–547.Crossref, Google Scholar
• Attouch H, Bolte J (2009) On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Math. Programming 116(1–2):5–16.Crossref, Google Scholar
• Attouch H, Bolte J, Redont P, Soubeyran A (2010) Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the Kurdyka-Łojasiewicz inequality. Math. Oper. Res. 35(2):438–457.Link, Google Scholar
• Attouch H, Bolte J, Svaiter BF (2013) Convergence of descent methods for semi-algebraic and tame problems: Proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methods. Math. Programming 137(1–2):91–129.Crossref, Google Scholar
• Auslender A (2013) An extended sequential quadratically constrained quadratic programming algorithm for nonlinear, semidefinite, and second-order cone programming. J. Optim. Theory Appl. 156(2):183–212.Crossref, Google Scholar
• Auslender A, Shefi R, Teboulle M (2010) A moving balls approximation method for a class of smooth constrained minimization problems. SIAM J. Optim. 20(6):3232–3259.Crossref, Google Scholar
• Beck A, Teboulle M (2010) Gradient-based algorithms with applications to signal recovery problems. Palomar D, Eldar Y, eds. Convex Optimization in Signal Processing and Communications (Cambribge University Press, Cambridge, UK), 42–88.Google Scholar
• Bertsekas D (1995) Nonlinear Programming (Athena Scientific, Belmont, MA).Google Scholar
• Bochnak J, Coste M, M-F R (1998) Real Algebraic Geometry (Springer, Berlin).Crossref, Google Scholar
• Bolte J, Daniilidis A, Lewis AS (2007a) The łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAM J. Optim. 17(4):1205–1223.Crossref, Google Scholar
• Bolte J, Sabach S, Teboulle M (2013) Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Math. Programming 146(1–2):459–494.Crossref, Google Scholar
• Bolte J, Daniilidis A, Lewis AS, Shiota M (2007b) Clarke subgradients of stratifiable functions. SIAM J. Optim. 18(2):556–572.Crossref, Google Scholar
• Bonnans JF, Gilbert JC, Lemaréchal C, Sagastizábal C (2003) Numerical Optimization: Theoretical and Practical Aspects (Springer, Berlin).Crossref, Google Scholar
• Burke JV, Han SP (1989) A robust sequential quadratic programming method. Math. Programming 43(1–3):277–303.Crossref, Google Scholar
• Byrd RH, Gould N, Nocedal J, Waltz R (2005) On the convergence of successive linear-quadratic programming algorithms. SIAM J. Optim. 16(2):471–489.Crossref, Google Scholar
• Cartis C, Gould N, Toint P (2014) On the complexity of finding first-order critical points in constrained nonlinear optimization. Math. Programming A 144(1):93–106.Crossref, Google Scholar
• Chouzenoux E, Jezierska A, Pesquet J, Talbot H (2013) A majorize-minimize subspace approach for ℓ2 − ℓ0 image regularization. SIAM J. Imaging Sci. 6(1):563–591.Crossref, Google Scholar
• Combettes PL, Pesquet J-C (2011) Proximal splitting methods in signal processing. Bauschke H, Burachik RS, Combettes PL, Elser V, Luke R, Wolkowicz H, eds. Fixed-Point Algorithms for Inverse Problems in Science and Engineering, Springer Optimization and Its Applications (Springer, New York), 185–212.Crossref, Google Scholar
• Cox B, Juditsky A, Nemirovski A (2013) Dual subgradient algorithms for large-scale nonsmooth learning problems. Math. Programming 148(1–2):1–38.Google Scholar
• Dempster AP, Laird NM, Rubin DB (1977) Maximum likelihood from incomplete data via the EM algorithm. J. Royal Statist. Soc., Ser. B 39(1):1–38.Google Scholar
• Dontchev A, Rockafellar RT (2009) Implicit Functions and Solution Mappings (Springer Monograph Series, New York).Crossref, Google Scholar
• Fletcher R (1985) An ℓ1 penalty method for nonlinear constraints. Boggs PT, Byrd RH, B SR, eds. Numerical Optimization (SIAM, Philadelphia), 26–40.Google Scholar
• Fletcher R (2000) Practical Methods of Optimization, 2nd ed. (John Wiley & Sons, New York).Crossref, Google Scholar
• Fletcher R, Gould N, Leyffer S, Toint P, Wächter A (2002) Global convergence of a trust-region SQP-filter algorithm for general nonlinear programming. SIAM J. Optim. 13(3):635–659.Crossref, Google Scholar
• Fukushima M, Luo Z, Tseng P (2003) A sequential quadratically constrained quadratic programming method for differentiable convex minimization. SIAM J. Optim. 13(4):1098–1119.Crossref, Google Scholar
• Gill PE, Wong E (2012) Sequential quadratic programming methods. Lee J, Leyffer S, eds. Mixed Integer Nonlinear Programming, The IMA Volumes in Mathematics and Its Applications, Vol. 154 (Springer, New York), 147–224.Crossref, Google Scholar
• Gill PE, Murray W, Saunders M (2005) SNOPT: An SQP algorithm for large-scale constrained optimization. SIAM Rev. 47(1):99–131.Crossref, Google Scholar
• Han S (1977) A globally convergent method for nonlinear programming. J. Optim. Theory Appl. 22(3):297–309.Crossref, Google Scholar
• Hare WL, Lewis AS (2004) Identifying active constraints via partial smoothness and prox-regularity. J. Convex Anal. 11(2):251–266.Google Scholar
• Ioffe A (2009) An invitation to tame optimization. SIAM J. Optim. 19(4):1894–1917.Crossref, Google Scholar
• Kurdyka K (1998) On gradients of functions definable in o-minimal structures. Annales de l’institut Fourier 48(3):769–783.Crossref, Google Scholar
• Levenberg K (1944) A method for the solution of certain problems in least squares. Quart. Appl. Math. 2:164–168.Crossref, Google Scholar
• Lewis AS (2002) Active sets, nonsmoothness, and sensitivity. SIAM J. Optim. 13(3):702–725.Crossref, Google Scholar
• Łojasiewicz S (1963) Une propriété topologique des sous-ensembles analytiques réels. Les Équations aux Dérivées Partielles, Vol. 117 (Éditions du Centre National de la Recherche Scientifique, Paris), 87–89.Google Scholar
• Mairal J (2013) Optimization with first-order surrogate functions. Dasgupta S, McAllester D, eds., Proc. Internat. Conf. Machine Learn. (ICML) (Microtome Publishing, Brookline, MA), 28:783–791.Google Scholar
• Maratos N (1978) Exact penalty function algorithms for finite dimensional and control optimization problems. Ph.D. thesis, Imperial College, University of London, London.Google Scholar
• Marquardt D (1963) An algorithm for least-square estimation of nonlinear parameters. SIAM J. Appl. Math. 11:431–441.Crossref, Google Scholar
• Nesterov Y (2004) Introductory Lectures on Convex Optimization: A Basic Course, Vol. 87 (Springer, New York).Crossref, Google Scholar
• Nocedal J, Wright SJ (2006) Numerical Optimization, Springer Series in Operations Research and Financial Engineering (Springer, New York).Google Scholar
• Noll D (2014) Convergence of non-smooth descent methods using the Kurdyka-Łojasiewicz inequality. J. Optim. Theory Appl. 160(2):553–572.Crossref, Google Scholar
• Ortega JM, Rheinboldt WC (1970) Iterative Solution of Nonlinear Equations in Several Variables, Vol. 30 (SIAM, Philadelphia).Google Scholar
• Powell MJD (1973) On search directions for minimization algorithms. Math. Programming 4(1):193–201.Crossref, Google Scholar
• Rockafellar RT, Wets R (1998) Variational Analysis, Vol. 317 (Springer, Berlin).Crossref, Google Scholar
• Shuzhong S (1985) Ekeland’s variational principle and the mountain pass lemma. Acta Mathematica Sinica 1(4):348–355.Crossref, Google Scholar
• Solodov MV (2004) On the sequential quadratically constrained quadratic programming methods. Math. Oper. Res. 29(1):64–79.Link, Google Scholar
• Solodov MV (2009) Global convergence of an SQP method without boundedness assumptions on any of the iterative sequences. Math. Programming 118(1):1–12.Crossref, Google Scholar
• Svanberg K (2002) A class of globally convergent optimization methods based on conservative convex separable approximations. SIAM J. Optim. 12(2):555–573.Crossref, Google Scholar
• van den Dries L, Miller C (1996) Geometric categories and o-minimal structures. Duke Math. J. 84(2):497–540.Crossref, Google Scholar
• Wilson A (1963) Simplicial method for convex programming. Ph.D. thesis, Harvard University, Cambridge, MA.Google Scholar
• Wright S (2003) Constraint identification and algorithm stabilization for degenerate nonlinear programs. Math. Programming 95(1):137–160.Crossref, Google Scholar