A linear-time algorithm for minimizing the ratio of quadratic functions with a quadratic constraint

作     者：Wang, Liping Ma, Tengfei Xia, Yong 

作者机构：Nanjing Univ Aeronaut & Astronaut Dept Math Nanjing 210016 Peoples R China Beihang Univ Sch Math Sci LMIB Minist Educ Beijing 100191 Peoples R China 

出 版 物：《COMPUTATIONAL & APPLIED MATHEMATICS》 (Comput. Appl. Math.)

年 卷 期：2021年第40卷第4期

页      面：1-15页

核心收录：

基　　金：NSFC [11971231, 11771210, 11822103] Beijing Natural Science Foundation [Z180005] 

主　　题：Fractional programming Linear-time complexity Strong duality Bisection Regularized total least squares 

摘      要：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.