Solving Generalized CDT Problems via Two-Parameter Eigenvalues
提出一种求解广义CDT问题的算法，通过求解双参数线性特征值问题计算所有拉格朗日乘子，找到全局最优解，在精确算术下保证全局收敛，数值实验表明有限精度下表现良好。
We consider solving a nonconvex quadratic minimization problem with two quadratic constraints, one of which being convex. This problem is a generalization of the Celis--Denis--Tapia (CDT) problem and thus we refer to it as GCDT (Generalized CDT). The CDT problem has been widely studied, but no polynomial-time algorithm was known until Bienstock's recent work. His algorithm solves the CDT problem in polynomial time with respect to the number of bits in data and $\log\epsilon^{-1}$ by admitting an $\epsilon$ error in the constraints. The algorithm, however, appears to be difficult to implement. In this paper, we present another algorithm for GCDT, which is guaranteed to find a global solution for almost all GCDT instances (and slightly perturbed ones in some exceptionally rare cases), in exact arithmetic (including eigenvalue computation). Our algorithm is based on the approach proposed by Iwata, Nakatsukasa, and Takeda (2015) for computing the signed distance between overlapping ellipsoids. Our algorithm computes all the Lagrange multipliers of GCDT by solving a two-parameter linear eigenvalue problem, obtains the corresponding KKT points, and finds a global solution as the KKT point with the smallest objective value. In practice, in finite precision arithmetic, our algorithm requires $O(n^6\log\log u^{-1})$ computational time, where $n$ is the number of variables and $u$ is the unit roundoff. Although we derive our algorithm under the unrealistic assumption that exact eigenvalues can be computed, numerical experiments illustrate that our algorithm performs well in finite precision arithmetic.