On the complexity of solving feasibility problems with regularized models

References

• R. Andreani, E.G. Birgin, J.M. Martínez, and M.L. Schuverdt, On augmented Lagrangian methods with general lower-level constraints, SIAM J. Optim. 18 (2008), pp. 1286–1309. doi: 10.1137/060654797
   Web of Science ®Google Scholar
• F.J. Aragón Artacho, J.M. Borwein, and M.K. Tam, Douglas-Rachford feasibility methods for matrix completion problems, ANZIAM J. 55 (2014), pp. 299–326.
   Web of Science ®Google Scholar
• J. Barzilai and J.M. Borwein, Two point step size gradient methods, IMA J. Numer. Anal. 8 (1988), pp. 141–148. doi: 10.1093/imanum/8.1.141
   Web of Science ®Google Scholar
• A. Beck and M. Teboulle, A linearly convergent algorithm for solving a class of nonconvex/affine feasibility problems, in Fixed-Point Algorithms for Inverse Problems in Science and Engineering, H. Bauschke, R. Burachik, P. Combettes, V. Elser, D. Luke, and H. Wolkowicz, eds., Vol. 49, Springer Optimization and Its Applications, Springer, New York, NY, 2011, pp. 33–48.
   Google Scholar
• E.G. Birgin and J.M. Martínez, Practical Augmented Lagrangian Methods for Constrained Optimization, Vol. 10 of Fundamentals of Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2014, doi:10.1137/1.9781611973365.
   Google Scholar
• E.G. Birgin and J.M. Martínez, Complexity and performance of an Augmented Lagrangian algorithm, Optim. Methods Softw., to appear. doi:10.1080/10556788.2020.1746962.
   Google Scholar
• E.G. Birgin, J.M. Martínez, and M. Raydan, Nonmonotone spectral projected gradient methods on convex sets, SIAM J. Optim. 10 (2000), pp. 1196–1211. doi: 10.1137/S1052623497330963
   Web of Science ®Google Scholar
• E.G. Birgin, J.L. Gardenghi, J.M. Martínez, S.A. Santos, and P.L. Toint, Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models, Math. Program. 163 (2017), pp. 359–368. doi: 10.1007/s10107-016-1065-8
   Web of Science ®Google Scholar
• C. Cartis, N.I.M. Gould, and P.L. Toint, Adaptive cubic regularization methods for unconstrained optimization. Part I: Motivation, convergence and numerical results, Math. Program. 127 (2011), pp. 245–295. doi: 10.1007/s10107-009-0286-5
   Web of Science ®Google Scholar
• C. Cartis, N.I.M. Gould, and P.L. Toint, Adaptive cubic regularization methods for unconstrained optimization. Part II: Worst-case function and derivative complexity, Math. Program. 130 (2011), pp. 295–319. doi: 10.1007/s10107-009-0337-y
   Web of Science ®Google Scholar
• C. Cartis, N.I.M. Gould, and P.L. Toint, On the evaluation complexity of cubic regularization methods for potentially rank-deficient nonlinear least-squares problems and its relevance to constrained nonlinear optimization, SIAM J. Optim. 23 (2013), pp. 1553–1574. doi: 10.1137/120869687
   Web of Science ®Google Scholar
• C. Cartis, N.I.M. Gould, and P.L. Toint, Improved worst-case evaluation complexity for potentially rank-deficient nonlinear least-Euclidean-norm problems using higher-order regularized models, Tech. Rep. NA 15-17, Numerical Analysis Group, University of Oxford, 2015.
   Google Scholar
• C. Cartis, N.I.M. Gould, and P.L. Toint, Universal regularization methods: Varying the power, the smoothness and the accuracy, SIAM J. Optim. 29 (2019), pp. 595–615. doi: 10.1137/16M1106316
   Web of Science ®Google Scholar
• J.E. Dennis and R.S. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Prentice Hall, Englewood Cliff, NJ, 1983.
   Google Scholar
• N.I.M. Gould, D. Orban, and P.L. Toint, CUTEst: A constrained and unconstrained testing environment with safe threads for mathematical optimization, Comput. Optim. Appl. 60 (2014), pp. 545–557. doi: 10.1007/s10589-014-9687-3
   Web of Science ®Google Scholar
• G.N. Grapiglia and Y. Nesterov, Regularized Newton methods for minimizing functions with Hölder continuous Hessians, SIAM J. Optim. 27 (2017), pp. 478–506. doi: 10.1137/16M1087801
   Web of Science ®Google Scholar
• G.N. Grapiglia and Y. Nesterov, Accelerated regularized Newton methods for minimizing composite convex functions, SIAM J. Optim. 29 (2019), pp. 77–99. doi: 10.1137/17M1142077
   Web of Science ®Google Scholar
• A.O. Herrera, H.D. Scolnik, G. Chichilnisky, G.C. Gallopin, and J.E. Hardoy, Catastrophe Or New Society? A Latin America World Model, IDRC, Ottawa, ON, 1976.
   Google Scholar
• C.R. Johnson, Matrix completion problems: A survey, Proc. Sympos. Appl. Math. 40 (1990), pp. 171–198. doi: 10.1090/psapm/040/1059486
   Google Scholar
• M. Laurent, Matrix completion problems, in Encyclopedia of Optimization, C.A. Floudas and P. Pardalos, eds., Springer, Boston, MA, 2008, pp. 1967–1975.
   Google Scholar
• J.M. Martínez, On high-order model regularization for constrained optimization, SIAM J. Optim. 27 (2017), pp. 2447–2458. doi: 10.1137/17M1115472
   Web of Science ®Google Scholar
• L. Martínez, R. Andrade, E.G. Birgin, and J.M. Martínez, PACKMOL: A package for building initial configurations for molecular dynamics simulations, J. Comput. Chem. 30 (2009), pp. 2157–2164. doi: 10.1002/jcc.21224
   PubMed Web of Science ®Google Scholar
• Y. Nesterov and B.T. Polyak, Cubic regularization of Newton method and its global performance, Math. Program. 108 (2006), pp. 177–205. doi: 10.1007/s10107-006-0706-8
   Web of Science ®Google Scholar
• M. Raydan, The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem, SIAM J. Optim. 7 (1997), pp. 26–33. doi: 10.1137/S1052623494266365
   Web of Science ®Google Scholar
• M. Yashtini, On the global convergence rate of the gradient descent method for functions with Hölder continuous gradients, Optim. Lett. 10 (2016), pp. 1361–1370. doi: 10.1007/s11590-015-0936-x
   Web of Science ®Google Scholar