Complexity of a projected Newton-CG method for optimization with bounds

• 成果类型: Article
• 署名作者: Xie, Yue; Wright, Stephen J.
• 署名单位: University of Hong Kong; University of Hong Kong; University of Wisconsin System; University of Wisconsin Madison
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-023-02000-z
• 发表日期: 2024
• 页码: 107-144
• 关键词: nonnegative matrix factorization; Nonconvex Optimization; regularization; algorithm

摘要

This paper describes a method for solving smooth nonconvex minimization problems subject to bound constraints with good worst-case complexity guarantees and practical performance. The method contains elements of two existing methods: the classi-cal gradient projection approach for bound-constrained optimization and a recently proposed Newton-conjugate gradient algorithm for unconstrained nonconvex opti-mization. Using a new definition of approximate second-order optimality parametrized by some tolerance E (which is compared with related definitions from previous works), we derive complexity bounds in terms of E for both the number of iterations required and the total amount of computation. The latter is measured by the number of gradient evaluations or Hessian-vector products. We also describe illustrative computational results on several test problems from low-rank matrix optimization.