The generalized trust region subproblem
The generalized trust region subproblem
复制标题
DOI：
10.1007/s10589-013-9635-7
复制
发表时间：
2014-01
影响因子：
2.2
通讯作者：
Ting Kei Pong;Henry Wolkowicz
中科院分区：
文献类型：
--
作者：
Ting Kei Pong;Henry Wolkowicz
区间有界广义信赖域子问题（GTRS）是在一般二次型约束条件下，极小化一般二次型目标q 0（x）→min，且约束条件为上、下界q ≤q1（x）≤u.这意味着对任何一个二次函数都没有确定性假设。我们首先研究了在约束条件下这个简单凸问题的最优性特征，并表明可以在不失一般性的情况下假设它。接下来，我们将GTRS分为简单情况和困难情况下的实例，并证明，上，下有界的一般问题可以减少到一个等价的等式约束问题后，确定合适的广义特征值和可能解决稀疏系统。然后，我们讨论了如何Rendl-Wolkowicz算法提出的Fortin和Wolkowicz（Optim.方法软件。19（1）：41-67，2004）和Rendl和Wolkowicz（Math. Program. 77（2，Ser. B）：273-299，1997）可以被扩展以解决所得到的等式约束问题，突出了GTRS与找到参数化矩阵束的最小广义特征值的问题之间的联系。最后，我们提出的数值结果来说明这个算法在本文的最后。
Theinterval bounded generalized trust region subproblem(GTRS) consists in minimizing a general quadratic objective,q0(x)→min, subject to an upper and lower bounded general quadratic constraint,ℓ≤q1(x)≤u. This means that there are no definiteness assumptions on either quadratic function. We first study characterizations of optimality for thisimplicitlyconvex problem under a constraint qualification and show that it can be assumed without loss of generality. We next classify the GTRS into easy case and hard case instances, and demonstrate that the upper and lower bounded general problem can be reduced to an equivalent equality constrained problem after identifying suitable generalized eigenvalues and possibly solving a sparse system. We then discuss how the Rendl-Wolkowicz algorithm proposed in Fortin and Wolkowicz (Optim. Methods Softw. 19(1):41–67, 2004) and Rendl and Wolkowicz (Math. Program. 77(2, Ser. B):273–299, 1997) can be extended to solve the resulting equality constrained problem, highlighting the connection between the GTRS and the problem of finding minimum generalized eigenvalues of a parameterized matrix pencil. Finally, we present numerical results to illustrate this algorithm at the end of the paper.