×

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:
90C20 Quadratic programming
Software:
GQTPAR; HSL-VF05
PDF BibTeX XML Cite
Full Text: DOI
References:
[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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.