2018/07/19 by Rujun Jiang, Duan Li, Jiang, Rujun +1
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #Complexity and Algorithms in Graphs #FOS: Mathematics #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.1807.07563
openalex publication_date 2018/07/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we provide the first provable linear-time (in the number of non-zero 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 regular conditions. Our algorithm is motivated by and extends a recent linear-time algorithm for the trust region subproblem by Hazan and Koren [Math. Program., 2016, 158(1-2): 363-381]. However, due to the non-convexity and non-compactness of the feasible region, such an extension is nontrivial. Our main contribution is to demonstrate that under some regular 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.