Complexity of a projected Newton-CG method for optimization with bounds
Complexity of a projected Newton-CG method for optimization with bounds
复制标题
DOI：
10.1007/s10107-023-02000-z
复制
发表时间：
2021-03
影响因子：
2.7
通讯作者：
Yue Xie;Stephen J. Wright
中科院分区：
文献类型：
--
作者：
Yue Xie;Stephen J. Wright
本文描述了一种求解有界约束的光滑非凸极小化问题的方法，该方法具有良好的最坏情况复杂性保证和实用性能。该方法包含两个现有的方法的元素：经典的梯度投影方法的有界约束优化和最近提出的牛顿共轭梯度算法的无约束非凸优化。使用一个新的定义的近似二阶最优参数化的一些公差（这是与以前的作品相关的定义相比），我们得出的复杂性界方面的迭代次数和总计算量。后者通过梯度评估或Hessian-vector乘积的数量来衡量。我们还描述了说明性的计算结果，从低秩矩阵优化的几个测试问题。
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 classical gradient projection approach for bound-constrained optimization and a recently proposed Newton-conjugate gradient algorithm for unconstrained nonconvex optimization. Using a new definition of approximate second-order optimality parametrized by some tolerance(which is compared with related definitions from previous works), we derive complexity bounds in terms offor 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.