A LINEAR-TIME ALGORITHM FOR GENERALIZED TRUST REGION SUBPROBLEMS

作     者：Jiang, Rujun Li, Duan 

作者机构：Fudan Univ Sch Data Sci Shanghai Peoples R China City Univ Hong Kong Sch Data Sci Hong Kong Peoples R China 

出 版 物：《SIAM JOURNAL ON OPTIMIZATION》 (工业与应用数学会最优化杂志)

年 卷 期：2020年第30卷第1期

页      面：915-932页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：Shanghai Sailing Program [18YF1401700] Natural Science Foundation of China (NSFC) Science and Technology Commission of Shanghai Municipality Project Hong Kong Research Grants Council [14213716, 14202017] 

主　　题：generalized trust region subproblem semidefinite programming linear-time complexity approximation algorithms 

摘      要：In this paper, we provide the first provable linear-time (in terms of the number of nonzero entries of the input) algorithm for approximately solving the generalized trust region subproblem (GTRS) of minimizing a quadratic function over a quadratic constraint under some regularity condition. Our algorithm is motivated by and extends a recent linear-time algorithm for the trust region subproblem by Hazan and Koren [Math. Program., 158 (2016), pp. 363-381]. However, due to the nonconvexity and noncompactness of the feasible region, such an extension is nontrivial. Our main contribution is to demonstrate that under some regularity condition, the optimal solution is in a compact and convex set and lower and upper bounds of the optimal value can be computed in linear time. Using these properties, we develop a linear-time algorithm for the GTRS.