A linear-time algorithm for minimizing the ratio of quadratic functions with a quadratic constraint
A linear-time algorithm for minimizing the ratio of quadratic functions with a quadratic constraint
复制标题
DOI：
10.1007/s40314-021-01527-1
复制
发表时间：
2021-05
影响因子：
2.6
通讯作者：
Liping Wang;Tengfei Ma;Yong Xia
中科院分区：
文献类型：
--
作者：
Liping Wang;Tengfei Ma;Yong Xia
We study the problem of minimizing the ratio of quadratic functions with a quadratic constraint (QCRQ), which is a generation of the trust-region subproblem and covers the regularized total least square problem as a special case. In this paper, we carefully employ the bisection search method to solve the scaled Lagrangian dual of (QCRQ) as strong duality holds for the primal and dual problems. We show that our algorithm can globally solve the nonconvex optimization (QCRQ) in linear time. Numerical experiments demonstrate the computational efficiency over other semidefinite programming solvers.
