论文标题
使用Riemannian优化解决信任区域子问题
Solving Trust Region Subproblems Using Riemannian Optimization
论文作者
论文摘要
信任区域子问题是在信任区域方法中扮演关键作用的基本优化问题。但是，它的问题和变体在其他许多应用程序中也会出现。在本文中，我们为信任区域子问题的一种迭代riemannian优化算法介绍了一个家族，该算法将不平等约束取代不平等约束，并收敛到全球最佳限度。我们的方法使用搜索空间的微不足道或非平凡的Riemannian几何形状，并且仅需要有关目标函数的二次组件的最小光谱信息。我们进一步展示了Riemannian优化理论如何促进对信任区域子问题及其困难的更深入的了解，例如，信任区域子问题与寻找仿型特征向量的问题之间存在深厚的联系，以及根据Riiemann Hessian Hessian Operator在全局最佳操作员的条件数量的情况下，对所谓的硬情况进行了新的检查。最后，我们建议通过仔细选择可变的riemannian度量来结合预处理，并以渐近收敛速率建立界限，以预言器近似输入矩阵。
The Trust Region Subproblem is a fundamental optimization problem that takes a pivotal role in Trust Region Methods. However, the problem, and variants of it, also arise in quite a few other applications. In this article, we present a family of iterative Riemannian optimization algorithms for a variant of the Trust Region Subproblem that replaces the inequality constraint with an equality constraint, and converge to a global optimum. Our approach uses either a trivial or a non-trivial Riemannian geometry of the search-space, and requires only minimal spectral information about the quadratic component of the objective function. We further show how the theory of Riemannian optimization promotes a deeper understanding of the Trust Region Subproblem and its difficulties, e.g., a deep connection between the Trust Region Subproblem and the problem of finding affine eigenvectors, and a new examination of the so-called hard case in light of the condition number of the Riemannian Hessian operator at a global optimum. Finally, we propose to incorporate preconditioning via a careful selection of a variable Riemannian metric, and establish bounds on the asymptotic convergence rate in terms of how well the preconditioner approximates the input matrix.
