×

zbMATH — the first resource for mathematics

Local nonglobal minima for solving large-scale extended trust-region subproblems. (English) Zbl 1391.90496
Summary: We study large-scale extended trust-region subproblems (eTRS) i.e., the minimization of a general quadratic function subject to a norm constraint, known as the trust-region subproblem (TRS) but with an additional linear inequality constraint. It is well known that strong duality holds for the TRS and that there are efficient algorithms for solving large-scale TRS problems. It is also known that there can exist at most one local non-global minimizer (LNGM) for TRS. We combine this with known characterizations for strong duality for eTRS and, in particular, connect this with the so-called hard case for TRS. We begin with a recent characterization of the minimum for the TRS via a generalized eigenvalue problem and extend this result to the LNGM. We then use this to derive an efficient algorithm that finds the global minimum for eTRS by solving at most three generalized eigenvalue problems.

MSC:
90C26 Nonconvex programming, global optimization
90C30 Nonlinear programming
90C46 Optimality conditions and duality in mathematical programming
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
Software:
SeDuMi; GQTPAR
PDF BibTeX Cite
Full Text: DOI arXiv
References:
[1] Adachi, S., Iwata, S., Nakatsukasa, Y., Takeda, A.: Solving the trust region subproblem by a generalized eigenvalue problem. Technical report, Mathematical Engineering, The University of Tokyo, (2015) · Zbl 1359.49009
[2] Ai, W; Zhang, S, Strong duality for the CDT subproblem: a necessary and sufficient condition, SIAM J. Optim., 19, 1735-1756, (2008) · Zbl 1187.90290
[3] Boggs, PT; Tolle, JW, Sequential quadratic programming, Acta Numerica., 4, 1-51, (1995) · Zbl 0828.65060
[4] Burer, S; Anstreicher, KM, Second-order-cone constraints for extended trust-region subproblems, SIAM J. Optim., 23, 432-451, (2013) · Zbl 1298.90062
[5] Conn, A.R., Gould, N.I.M., Toint, PhL: Trust-Region Methods. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (2000) · Zbl 0958.65071
[6] Fiacco, A.V.: Introduction to Sensitivity and Stability Analysis in Nonlinear Programming. Mathematics in Science and Engineering, vol. 165. Academic Press, Orlando (1983) · Zbl 0543.90075
[7] Fortin, C; Wolkowicz, H, The trust region subproblem and semidefinite programming, Optim. Methods Softw., 19, 41-67, (2004) · Zbl 1070.65041
[8] Gay, DM, Computing optimal locally constrained steps, SIAM J. Sci. Stat. Comput., 2, 186-197, (1981) · Zbl 0467.65027
[9] Gould, NIM; Daniel, P; Robinson, P; Sue Thorne, H, On solving trust-region and other regularised subproblems in optimization, Math. Progr. Comput., 2, 21-57, (2010) · Zbl 1193.65098
[10] Hager, WW; Park, S, Global convergence of SSM for minimizing a quadratic over a sphere, Math. Comp., 74, 1413-1423, (2005) · Zbl 1059.90112
[11] Hsia, Y., Sheu, R.-L.: Trust region subproblem with a fixed number of additional linear inequality constraints has polynomial complexity. Report, Beihang University, Beijing, China (2013)
[12] Jeyakumar, V; Li, GY, Trust-region problems with linear inequality constraints: exact SDP relaxation, global optimality and robust optimization, Math. Progr., 147, 171-206, (2014) · Zbl 1297.90105
[13] Lampe, J; Rojas, M; Sorensen, DC; Voss, H, Accelerating the LSTRS algorithm, SIAM J. Sci. Comput., 33, 175-194, (2011) · Zbl 1368.65096
[14] Lucidi, S; Palagi, L; Roma, M, On some properties of quadratic programs with a convex quadratic constraint, SIAM J. Optim., 8, 105-122, (1998) · Zbl 0910.90227
[15] Martínez, JM, Local minimizers of quadratic functions on Euclidean balls and spheres, SIAM J. Optim., 4, 159-176, (1994) · Zbl 0801.65057
[16] Moré, JJ; Sorensen, DC, Computing a trust region step, SIAM J. Sci. Stat. Comput., 4, 553-572, (1983) · Zbl 0551.65042
[17] Rendl, F; Wolkowicz, H, A semidefinite framework for trust region subproblems with applications to large scale minimization, Math. Program., 77, 273-299, (1997) · Zbl 0888.90137
[18] Rojas, M., Santos, S.A., and Sorensen, D.C.: A new matrix-free algorithm for the large-scale trust-region subproblem. SIAM J. Optim. 11(3):611-646 (2001) (Electronic) · Zbl 0994.65067
[19] Salahi, M; Fallahi, S, Trust region subproblem with an additional linear inequality constraint, Optim. Lett., 10, 821-832, (2016) · Zbl 1367.90077
[20] Salahi, M., Taati, A.: A fast eigenvalue approach for solving the trust region subproblem with an additional linear inequality. Comput. Appl. Math. (2016). doi:10.1007/s40314-016-0347-3 · Zbl 1393.90097
[21] Sturm, J.F.: Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Softw. 11/12(1-4), 625-653 (1999). http://sedumi.ie.lehigh.edu · Zbl 0973.90526
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.