×

zbMATH — the first resource for mathematics

Globally solving the trust region subproblem using simple first-order methods. (English) Zbl 1455.90104
The authors introduce a family of first-order conic methods (FOCM) for solving the trust region subproblem \[ \left\{ \begin{array}{l} \mathrm{ minimize }\; q(x) := x^T A x - 2b^Tx \\ \mathrm{ s.t.}\\ x \in B := \{v \in \mathbb{R}^n \mid \|v\|^2 \leq 1\}, \end{array} \right.\tag{TRS} \] where \(q\) is a quadratic (not necessarily convex) function given by a symmetric matrix \(A \in \mathbb{R}^{n \times n}\) and \(b \in \mathbb{R}\), while \(B\) is the Euclidean closed unit ball. It is shown that any method within the family FOCM (in particular, the projected and conditional gradient methods) produces a sequence that converges to a stationary point of the problem TRS. The convergence to an optimal solution is proven in both the “easy case” and the “hard case” under suitable assumptions.

MSC:
90C06 Large-scale problems in mathematical programming
90C26 Nonconvex programming, global optimization
90C46 Optimality conditions and duality in mathematical programming
Software:
GQTPAR; HSL-VF05
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] S. Adachi, S. Iwata, Y. Nakatsukasa, and A. Takeda, Solving the trust-region subproblem by a generalized eigenvalue problem, SIAM J. Optim., 27 (2017), pp. 269–291. · Zbl 1359.49009
[2] H. Attouch, J. Bolte, and B. F. Svaiter, Convergence of descent methods for semi-algebraic and tame problems: Proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methods, Math. Program., 137 (2013), pp. 91–129. · Zbl 1260.49048
[3] A. Beck, Introduction to Nonlinear Optimization: Theory, Algorithms, and Applications with MATLAB, MOS-SIAM Ser. Optim. 19, SIAM, Philadelphia, PA, 2014. · Zbl 1320.90001
[4] A. Beck, First-Order Methods in Optimization, MOS-SIAM Ser. Optim. 25, SIAM, Philadelphia, PA, 2017.
[5] A. Ben-Tal and M. Teboulle, Hidden convexity in some nonconvex quadratically constrained quadratic programming, Math. Program., 72 (1996), pp. 51–63. · Zbl 0851.90087
[6] D. P. Bertsekas, Nonlinear Programming, 2nd ed., Athena Scientific, Nashua, NH, 1999.
[7] J. Bolte, S. Sabach, and M. Teboulle, Proximal alternating linearized minimization for nonconvex and nonsmooth problems, Math. Program., 146 (2014), pp. 459–494. · Zbl 1297.90125
[8] A. R. Conn, N. I. Gould, and P. L. Toint, Trust Region Methods, MOS-SIAM Ser. Optim. 1, SIAM, Philadelphia, PA, 2000. · Zbl 0958.65071
[9] J. B. Erway, P. E. Gill, and J. D. Griffin, Iterative methods for finding a trust-region step, SIAM J. Optim., 20 (2009), pp. 1110–1131. · Zbl 1189.49049
[10] M. Frank and P. Wolfe, An algorithm for quadratic programming, Naval Res. Logist., 3 (1956), pp. 95–110.
[11] W. Gander, G. H. Golub, and U. von Matt, A constrained eigenvalue problem, Linear Algebra Appl., 114 (1989), pp. 815–839. · Zbl 0666.15006
[12] D. M. Gay, Computing optimal locally constrained steps, SIAM J. Sci. and Stat. Comput., 2 (1981), pp. 186–197. · Zbl 0467.65027
[13] G. H. Golub and C. F. Van Loan, Matrix Computations, 4th ed., John Hopkins University Press, Baltimore, MD, 2012. · Zbl 0559.65011
[14] N. I. M. Gould, S. Lucidi, M. Roma, and P. L. Toint, Solving the trust-region subproblem using the Lanczos method, SIAM J. Optim., 9 (1999), pp. 504–525. · Zbl 1047.90510
[15] W. W. Hager, Minimizing a quadratic over a sphere, SIAM J. Optim., 12 (2001), pp. 188–208. · Zbl 1058.90045
[16] E. Hazan and T. Koren, A linear-time algorithm for trust region problems, Math. Program., 158 (2016), pp. 363–381. · Zbl 1346.90654
[17] N. Ho-Nguyen and F. Kilinc-Karzan, A second-order cone based approach for solving the trust-region subproblem and its variants, SIAM J. Optim., 27 (2017), pp. 1485–1512. · Zbl 1370.90170
[18] J. Lampe, M. Rojas, D. C. Sorensen, and H. Voss, Accelerating the LSTRS algorithm, SIAM J. Sci. Comput., 33 (2011), pp. 175–194. · Zbl 1368.65096
[19] E. S. Levitin and B. T. Polyak, Constrained minimization methods, Comput. Math. Math. Phys., 6 (1966), pp. 787–823. · Zbl 0184.38902
[20] R. Luss and M. Teboulle, Conditional gradient algorithms for rank-one matrix approximations with a sparsity constraint, SIAM Rev., 55 (2013), pp. 65–98. · Zbl 1263.90094
[21] J. J. Moré and D. C. Sorensen, Computing a trust region step, SIAM J. Sci. and Stat. Comput., 4 (1983), pp. 553–572. · Zbl 0551.65042
[22] F. Rendl and H. Wolkowicz, A semidefinite framework for trust region subproblems with applications to large scale minimization, Math. Program., 77 (1997), pp. 273–299. · Zbl 0888.90137
[23] M. Rojas, S. A. Santos, and D. C. Sorensen, A new matrix-free algorithm for the large-scale trust-region subproblem, SIAM J. Optim., 11 (2000), pp. 611–646. · Zbl 0994.65067
[24] D. C. Sorensen, Newton’s method with a model trust region modification, SIAM J. Numer. Anal., 19 (1982), pp. 409–426. · Zbl 0483.65039
[25] D. C. Sorensen, Minimization of a large-scale quadratic function subject to a spherical constraint, SIAM J. Optim., 7 (1997), pp. 141–161. · Zbl 0878.65044
[26] T. Steihaug, The conjugate gradient method and trust regions in large scale optimization, SIAM J. Numer. Anal., 20 (1983), pp. 626–637. · Zbl 0518.65042
[27] P. D. Tao and L. T. H. An, A d.c. optimization algorithm for solving the trust-region subproblem, SIAM J. Optim., 8 (1998), pp. 476–505. · Zbl 0913.65054
[28] P. L. Toint, Towards an efficient sparsity exploiting Newton method for minimization, in Sparse Matrices and Their Uses, Academic Press, New York, 1981, pp. 57–88. · Zbl 0463.65045
[29] J. Wang and Y. Xia, A linear-time algorithm for the trust region subproblem based on hidden convexity, Optim. Lett., 11 (2017), pp. 1639–1646. · Zbl 1410.90145
[30] J. H. Wilkinson, The Algebraic Eigenvalue Problem, Numer. Math. Sci. Comput. 87, Oxford University Press, Oxford, 1965. · Zbl 0258.65037
[31] Y. Ye, A new complexity result on minimization of a quadratic function with a sphere constraint, in Recent Advances in Global Optimization, Princeton University Press, Princeton, NJ, 1992, pp. 19–31.
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.