# zbMATH — the first resource for mathematics

A linear-time algorithm for the trust region subproblem based on hidden convexity. (English) Zbl 1410.90145
Summary: We present a linear-time approximation scheme for solving the trust region subproblem (TRS). It employs Nesterov’s accelerated gradient descent algorithm to solve a convex programming reformulation of (TRS). The total time complexity is less than that of the recent linear-time algorithm. The algorithm is further extended to the two-sided trust region subproblem.

##### MSC:
 [1] Ben-Tal, A; Teboulle, M, Hidden convexity in some nonconvex quadratically constrained quadratic programming, Math. Program., 72, 51-63, (1996) · Zbl 0851.90087 [2] Conn, A.R., Gould, N.I., Toint, P.L.: Trust Region Methods. Society for Industrial and Applied Mathematics, Philadelphia (2000) · Zbl 0958.65071 [3] Flippo, OE; Jansen, B, Duality and sensitivity in nonconvex quadratic optimization over an ellipsoid, Eur. J. Oper. Res., 94, 167-178, (1996) · Zbl 0930.90076 [4] Golub, G.H., Van Loan, C.F.: Matrix Computations. Johns Hopkins University Press, Baltimore (1989) · Zbl 0733.65016 [5] Gould, NIM; Lucidi, S; Roma, M; Toint, PL, Solving the trust-region subproblem using the Lanczos method, SIAM J. Optim., 9, 504-525, (1999) · Zbl 1047.90510 [6] Hazan, E; Koren, T, A linear-time algorithm for trust region problems, Math. Program., 158, 363-381, (2016) · Zbl 1346.90654 [7] Kuczynski, J; Wozniakowski, H, Estimating the largest eigenvalue by the power and Lanczos algorithms with a random start, SIAM J. Matrix Anal. Appl., 13, 1094-1122, (1992) · Zbl 0759.65016 [8] Moré, JJ; Sorensen, DC, SIAM J. sci. statist. comput., Computing a trust region step, 4, 553-572, (1983) [9] Nesterov, YuE, A method for unconstrained convex minimization problem with the rate of convergence $$O(1/k^2)$$, Soviet Math. Dokl., 27, 372-376, (1983) · Zbl 0535.90071 [10] Pong, TK; Wolkowicz, H, Generalizations of the trust region subproblem, Comput. Optim. Appl., 58, 273-322, (2014) · Zbl 1329.90100 [11] Stern, R; Wolkowicz, H, Indefinite trust region subproblems and nonsymmetric eigenvalue perturbations, SIAM J. Optim., 5, 286-313, (1995) · Zbl 0846.49017 [12] Tseng, P.: On accelerated proximal gradient methods for convex-concave optimization (unpublished manuscript) (2008) · Zbl 1317.65141 [13] Wang, S; Xia, Y, Strong duality for generalized trust region subproblem: S-lemma with interval bounds, Optim. Lett., 9, 1063-1073, (2015) · Zbl 1354.90089 [14] Yuan, Y, Recent advances in trust region algorithms, Math. Program., 151, 249-281, (2015) · Zbl 1317.65141