SOLVING THE TRUST-REGION SUBPROBLEM BY A GENERALIZED EIGENVALUE PROBLEM
SOLVING THE TRUST-REGION SUBPROBLEM BY A GENERALIZED EIGENVALUE PROBLEM
复制标题
DOI：
10.1137/16m1058200
复制
发表时间：
2017-01-01
影响因子：
3.1
通讯作者：
Takeda, Akiko
中科院分区：
文献类型：
--
作者：
Adachi, Satoru;Iwata, Satoru;Takeda, Akiko
解决信任域子问题（TRS）的最先进算法是基于迭代过程的，涉及许多线性系统的解、特征值问题、子空间优化或线搜索步骤。一个相对被低估的事实，由于甘德，戈卢布，和冯马特[线性代数应用]。， 114 (1989), pp. 815839]，是trs可以通过一个广义特征值问题来求解，不需要外部迭代。本文重新发现了这一事实，发现了它的实用性，在精度和效率上都表现出了良好的性能。此外，我们将该方法推广到各个方向，即允许椭球体约束，处理所谓的硬情况，以及在不需要高精度时有效地获得近似解。我们证明了所得到的算法是一个通用的TRS求解器，对密集和大稀疏问题都有效，包括所谓的硬情况。我们的算法很容易实现：它的本质是几行MATLAB代码。
The state-of-the-art algorithms for solving the trust-region subproblem (TRS) are based on an iterative process, involving solutions of many linear systems, eigenvalue problems, subspace optimization, or line search steps. A relatively underappreciated fact, due to Gander, Golub, and von Matt [Linear Algebra Appl., 114 (1989), pp. 815839], is that TRSs can be solved by one generalized eigenvalue problem, with no outer iterations. In this paper we rediscover this fact and discover its great practicality, which exhibits good performance both in accuracy and efficiency. Moreover, we generalize the approach in various directions, namely by allowing for an ellipsoidal constraint, dealing with the so-called hard case, and obtaining approximate solutions efficiently when high accuracy is unnecessary. We demonstrate that the resulting algorithm is a general-purpose TRS solver, effective both for dense and large-sparse problems, including the so-called hard case. Our algorithm is easy to implement: its essence is a few lines of MATLAB code.