Hölderian Error Bounds and Kurdyka-Łojasiewicz Inequality for the Trust Region Subproblem

References

• [1] Artacho FA, Geoffroy MH (2008) Characterization of metric regularity of subdifferentials. J. Convex Anal. 15(2):365.Google Scholar
• [2] 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
• [3] Beck A (2014) Introduction to Nonlinear Optimization: Theory, Algorithms, and Applications with MATLAB (SIAM, Philadelphia).Crossref, Google Scholar
• [4] Beck A, Vaisbourd Y (2018) Globally solving the trust region subproblem using simple first-order methods. SIAM J. Optim. 28(3):1951–1967.Crossref, Google Scholar
• [5] Ben-Tal A, El Ghaoui L, Nemirovski A (2009) Robust Optimization (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• [6] Bertsekas DP (1999) Nonlinear Programming (Athena Scientific).Google Scholar
• [7] Bolte J, Daniilidis A, Ley O, Mazet L (2010) Characterizations of Łojasiewicz inequalities: subgradient flows, talweg, convexity. Trans. Amer. Math. Soc. 362(6):3319–3363.Crossref, Google Scholar
• [8] Bolte J, Nguyen TP, Peypouquet J, Suter BW (2017) From error bounds to the complexity of first-order descent methods for convex functions. Math. Programming 165(2):471–507.Crossref, Google Scholar
• [9] Burke JV, Ferris MC (1993) Weak sharp minima in mathematical programming. SIAM J. Control Optim. 31(5):1340–1359.Crossref, Google Scholar
• [10] Carmon Y, Duchi JC (2018) Analysis of Krylov subspace solutions of regularized nonconvex quadratic problems. Adv. Neural Inform. Processing Systems 31:10705–10715.Google Scholar
• [11] Conn AR, Gould NI, Toint PL (2000) Trust Region Methods (SIAM, Philadelphia).Crossref, Google Scholar
• [12] Cui Y, Ding C, Zhao X (2017) Quadratic growth conditions for convex matrix optimization problems associated with spectral functions. SIAM J. Optim. 27(4):2332–2355.Crossref, Google Scholar
• [13] Cui Y, Sun D, Toh KC (2019) On the R-superlinear convergence of the KKT residuals generated by the augmented Lagrangian method for convex composite conic programming. Math. Programming 178(1):381–415.Crossref, Google Scholar
• [14] Dontchev AL, Rockafellar RT (2009) Implicit Functions and Solution Mappings, vol. 543 (Springer, Berlin).Crossref, Google Scholar
• [15] Drusvyatskiy D, Lewis AS (2013) Tilt stability, uniform quadratic growth, and strong metric regularity of the subdifferential. SIAM J. Optim. 23(1):256–267.Crossref, Google Scholar
• [16] Drusvyatskiy D, Lewis AS (2018) Error bounds, quadratic growth, and linear convergence of proximal methods. Math. Oper. Res. 43(3):919–948.Link, Google Scholar
• [17] Drusvyatskiy D, Ioffe AD, Lewis AS (2021) Nonsmooth optimization using Taylor-like models: error bounds, convergence, and termination criteria. Math. Programming 185(1):357–383.Crossref, Google Scholar
• [18] Drusvyatskiy D, Mordukhovich BS, Nghia TT (2014) Second-order growth, tilt stability, and metric regularity of the subdifferential. J. Convex Anal. 21:1165–1192.Google Scholar
• [19] Fabian MJ, Henrion R, Kruger AY, Outrata JV (2010) Error bounds: Necessary and sufficient conditions. Set-Valued Variance Anal. 18(2):121–149.Crossref, Google Scholar
• [20] Flippo OE, Jansen B (1996) Duality and sensitivity in nonconvex quadratic optimization over an ellipsoid. Eur. J. Oper. Res. 94(1):167–178.Crossref, Google Scholar
• [21] Fortin C, Wolkowicz H (2004) The trust region subproblem and semidefinite programming. Optim. Methods Software 19(1):41–67.Crossref, Google Scholar
• [22] Frankel P, Garrigos G, Peypouquet J (2015) Splitting methods with variable metric for Kurdyka–Łojasiewicz functions and general convergence rates. J. Optim. Theory Appl. 165(3):874–900.Crossref, Google Scholar
• [23] Gao B, Liu X, Chen X, Yuan YX (2016) On the Łojasiewicz exponent of the quadratic sphere constrained optimization problem. Preprint, submitted November 27, updated on November 29, 2016 and February 23, 2021. https://arxiv.org/abs/1611.08781.Google Scholar
• [24] Ghadimi S, Lan G, Zhang H (2016) Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization. Math. Programming 155(1-2):267–305.Crossref, Google Scholar
• [25] Gould NI, Lucidi S, Roma M, Toint PL (1999) Solving the trust-region subproblem using the Lanczos method. SIAM J. Optim. 9(2):504–525.Crossref, Google Scholar
• [26] Han D, Sun D, Zhang L (2018) Linear rate convergence of the alternating direction method of multipliers for convex composite programming. Math. Oper. Res. 43(2):622–637.Link, Google Scholar
• [27] Hazan E, Koren T (2016) A linear-time algorithm for trust region problems. Math. Programming 158(1):363–381.Crossref, Google Scholar
• [28] Ho-Nguyen N, Kilinc-Karzan F (2017) A second-order cone based approach for solving the trust-region subproblem and its variants. SIAM J. Optim. 27(3):1485–1512.Crossref, Google Scholar
• [29] Hou K, Zhou Z, So AMC, Luo ZQ (2013) On the linear convergence of the proximal gradient method for trace norm regularization. Adv. Neural Inform. Processing Systems (NIPS), 26:710–718.Google Scholar
• [30] Ioffe A (2016) Metric regularity-a survey part 1. theory. J. Australian Math. Soc. 101(2):188–243.Crossref, Google Scholar
• [31] Jiang R, Li D (2019) Novel reformulations and efficient algorithms for the generalized trust region subproblem. SIAM J. Optim. 29(2):1603–1633.Crossref, Google Scholar
• [32] Jiang R, Li D (2020) A linear-time algorithm for generalized trust region subproblems. SIAM J. Optim. 30(1):915–932.Crossref, Google Scholar
• [33] Jiang R, Li D, Wu B (2018) SOCP reformulation for the generalized trust region subproblem via a canonical form of two symmetric matrices. Math. Programming 169(2):531–563.Crossref, Google Scholar
• [34] Li W (1995) Error bounds for piecewise convex quadratic programs and applications. SIAM J. Control Optim. 33(5):1510–1529.Crossref, Google Scholar
• [35] Li G, Pong TK (2016) Douglas–Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems. Math. Programming 159(1):371–401.Crossref, Google Scholar
• [36] Li G, Pong TK (2018) Calculus of the exponent of Kurdyka–Łojasiewicz inequality and its applications to linear convergence of first-order methods. Foundations Comput. Math. 18(5):1199–1232.Crossref, Google Scholar
• [37] Li M, Meng K, Yang X (2018) On error bound moduli for locally Lipschitz and regular functions. Math. Programming 171(1):463–487.Crossref, Google Scholar
• [38] Li G, Mordukhovich BS, Pham T (2015) New fractional error bounds for polynomial systems with applications to Hölderian stability in optimization and spectral theory of tensors. Math. Programming 153(2):333–362.Crossref, Google Scholar
• [39] Liu H, So AMC, Wu W (2019) Quadratic optimization with orthogonality constraint: Explicit Łojasiewicz exponent and linear convergence of retraction-based line-search and stochastic variance-reduced gradient methods. Math. Programming 178(1):215–262.Crossref, Google Scholar
• [40] Liu H, Wu W, So AMC (2016) Quadratic optimization with orthogonality constraints: Explicit Łojasiewicz exponent and linear convergence of line-search methods. Balcan MF, Weinberger KQ, eds. Proc. Internat. Conf. on Machine Learn., vol. 48 (PMLR, New York),1158–1167.Google Scholar
• [41] Lojasiewicz S (1963) Une propriété topologique des sous-ensembles analytiques réels. Équations Dérivées Partielles 117:87–89.Google Scholar
• [42] Łojasiewicz S (1993) Sur la géométrie semi-et sous-analytique. Ann. Inst. Fourier (Grenoble) 43:1575–1595.Crossref, Google Scholar
• [43] Luo ZQ, Sturm JF (2000) Error bounds for quadratic systems. High Performance Optimization (Springer, Berlin), 383–404.Crossref, Google Scholar
• [44] Luo ZQ, Tseng P (1992a) Error bound and convergence analysis of matrix splitting algorithms for the affine variational inequality problem. SIAM J. Optim. 2(1):43–54.Crossref, Google Scholar
• [45] Luo ZQ, Tseng P (1992b) On the linear convergence of descent methods for convex essentially smooth minimization. SIAM J. Control Optim. 30(2):408–425.Crossref, Google Scholar
• [46] Luo ZQ, Tseng P (1993) Error bounds and convergence analysis of feasible descent methods: a general approach. Ann. Oper. Res. 46(1):157–178.Crossref, Google Scholar
• [47] Luo ZQ, Pang JS, Ralph D (1996) Mathematical Programs with Equilibrium Constraints (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [48] Martínez JM (1994) Local minimizers of quadratic functions on Euclidean balls and spheres. SIAM J. Optim. 4(1):159–176.Crossref, Google Scholar
• [49] Moré JJ (1993) Generalizations of the trust region problem. Optim. Methods Software 2(3-4):189–209.Crossref, Google Scholar
• [50] Moré JJ, Sorensen DC (1983) Computing a trust region step. SIAM J. Sci. Statist. Comput. 4(3):553–572.Crossref, Google Scholar
• [51] Nesterov Y (2003) Introductory Lectures on Convex Optimization: A Basic Course, vol. 87 (Springer Science & Business Media, New York).Google Scholar
• [52] Pang JS (1997) Error bounds in mathematical programming. Math. Programming 79(1):299–332.Crossref, Google Scholar
• [53] Poliquin R, Rockafellar R (1996) Prox-regular functions in variational analysis. Trans. Amer. Math. Soc. 348(5):1805–1838.Crossref, Google Scholar
• [54] Pong TK, Wolkowicz H (2014) The generalized trust region subproblem. Comput. Optim. Appl. 58(2):273–322.Crossref, Google Scholar
• [55] Rendl F, Wolkowicz H (1997) A semidefinite framework for trust region subproblems with applications to large scale minimization. Math. Programming 77(1):273–299.Crossref, Google Scholar
• [56] So AMC, Zhou Z (2017) Non-asymptotic convergence analysis of inexact gradient methods for machine learning without strong convexity. Optim. Methods Software 32(4):963–992.Crossref, Google Scholar
• [57] Wang T, Pang JS (1994) Global error bounds for convex quadratic inequality systems. Optimization 31(1):1–12.Crossref, Google Scholar
• [58] Wang J, Xia Y (2017) A linear-time algorithm for the trust region subproblem based on hidden convexity. Optim. Lett. 11(8):1639–1646.Crossref, Google Scholar
• [59] Wang J, Xia Y (2020) Closing the gap between necessary and sufficient conditions for local nonglobal minimizer of trust region subproblem. SIAM J. Optim. 30(3):1980–1995.Crossref, Google Scholar
• [60] Yakubovich V (1997) S-procedure in nonlinear control theory. Vestnick Leningrad Univ. Math. 4:73–93.Google Scholar
• [61] Yuan Yx (2015) Recent advances in trust region algorithms. Math. Programming 151(1):249–281.Crossref, Google Scholar
• [62] Zhang LH, Shen C (2018) A nested Lanczos method for the trust-region subproblem. SIAM J. Sci. Comput. 40(4):2005–2032.Crossref, Google Scholar
• [63] Zhang H, Conn AR, Scheinberg K (2010) A derivative-free algorithm for least-squares minimization. SIAM J. Optim. 20(6):3555–3576.Crossref, Google Scholar
• [64] Zhang LH, Shen C, Li RC (2017) On the generalized Lanczos trust-region method. SIAM J. Optim. 27(3):2110–2142.Crossref, Google Scholar
• [65] Zhang H, Milzarek A, Wen Z, Yin W (2021) On the geometric analysis of a quartic–quadratic optimization problem under a spherical constraint. Math. Programming 1–53.Google Scholar
• [66] Zhou Z, So AMC (2017) A unified approach to error bounds for structured convex optimization problems. Math. Programming 165(2):689–728.Crossref, Google Scholar
• [67] Zhou Z, Zhang Q, So AMC (2015) ℓ1,p-norm regularization: Error bounds and convergence rate analysis of first-order methods. Bach F, Blei D, eds. Proc. Internat. Conf. on Machine Learn., vol. 37 (PMLR, Lille, France), 1501–1510.Google Scholar