Fast convergence of trust-regions for non-isolated minima via analysis of CG on indefinite matrices

• 成果类型: Article
• 署名作者: Rebjock, Quentin; Boumal, Nicolas
• 署名单位: Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-024-02140-w
• 发表日期: 2025
• 页码: 343-384
• 关键词: cubic regularization; descent methods; lanczos; algorithms; nonconvex; optimization; minimization; subproblem; BEHAVIOR; systems

摘要

Trust-region methods (TR) can converge quadratically to minima where the Hessian is positive definite. However, if the minima are not isolated, then the Hessian there cannot be positive definite. The weaker Polyak-& Lstrok;ojasiewicz (P & Lstrok;) condition is compatible with non-isolated minima, and it is enough for many algorithms to preserve good local behavior. Yet, TR with an exact subproblem solver lacks even basic features such as a capture theorem under P & Lstrok;. In practice, a popular inexact subproblem solver is the truncated conjugate gradient method (tCG). Empirically, TR-tCG exhibits superlinear convergence under P & Lstrok;. We confirm this theoretically. The main mathematical obstacle is that, under P & Lstrok;, at points arbitrarily close to minima, the Hessian has vanishingly small, possibly negative eigenvalues. Thus, tCG is applied to ill-conditioned, indefinite systems. Yet, the core theory underlying tCG is that of CG, which assumes a positive definite operator. Accordingly, we develop new tools to analyze the dynamics of CG in the presence of small eigenvalues of any sign, for the regime of interest to TR-tCG.