Holderian Error Bounds and Kurdyka-Lojasiewicz Inequality for the Trust Region Subproblem

• 成果类型: Article; Early Access
• 署名作者: Jiang, Rujun; Li, Xudong
• 署名单位: Fudan University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2021.1243
• 发表日期: 2022
• 关键词: linear-time algorithm; metric regularity; quadratic optimization; convergence analysis; descent methods; tilt stability; GROWTH; exponent; search

摘要

In this paper, we study the local variational geometry of the optimal solution set of the trust region subproblem (TRS), which minimizes a general, possibly nonconvex, quadratic function over the unit ball. Specifically, we demonstrate that a Holderian error bound holds globally for the TRS with modulus 1/4, and the Kurdyka-Lojasiewicz (KL) inequality holds locally for the TRS with a KL exponent 3/4 at any optimal solution. We further prove that, unless in a special case, the Holderian error bound modulus and the KL exponent is 1/2. Finally, as a byproduct, we further apply the obtained KL property to show that projected gradient methods studied elsewhere for solving the TRS achieve a local sublinear or even linear rate of convergence with probability 1 by choosing a proper initial point.