The generalized trust region subproblem. (English) Zbl 1329.90100

Summary: The interval bounded generalized trust region subproblem (GTRS) consists in minimizing a general quadratic objective, \(q_{0}(x)\to \min\), subject to an upper and lower bounded general quadratic constraint, \(\ell\leq q_{1}(x)\leq u\). This means that there are no definiteness assumptions on either quadratic function. We first study characterizations of optimality for this implicitly convex problem under a constraint qualification and show that it can be assumed without loss of generality. We next classify the GTRS into easy case and hard case instances, and demonstrate that the upper and lower bounded general problem can be reduced to an equivalent equality constrained problem after identifying suitable generalized eigenvalues and possibly solving a sparse system. We then discuss how the Rendl-Wolkowicz algorithm proposed in [C. Fortin and H. Wolkowicz, Optim. Methods Softw. 19, No. 1, 41–67 (2004; Zbl 1070.65041)] and [F. Rendl and H. Wolkowicz, Math. Program. 77, No. 2 (B), 273–299 (1997; Zbl 0888.90137)] can be extended to solve the resulting equality constrained problem, highlighting the connection between the GTRS and the problem of finding minimum generalized eigenvalues of a parameterized matrix pencil. Finally, we present numerical results to illustrate this algorithm at the end of the paper.


90C20 Quadratic programming
Full Text: DOI Link


[1] Barvinok, A., Problems of distance geometry and convex properties of quadratic maps, Discrete Comput. Geom., 13, 189-202, (1995) · Zbl 0829.05025
[2] Barvinok, A., A remark on the rank of positive semidefinite matrices subject to affine constraints, Discrete Comput. Geom., 25, 23-31, (2001) · Zbl 0969.90096
[3] Beck, A., Quadratic matrix programming, SIAM J. Optim., 17, 1224-1238, (2006) · Zbl 1136.90025
[4] Beck, A.; Eldar, Y.C., Strong duality in nonconvex quadratic optimization with two quadratic constraints, SIAM J. Optim., 17, 844-860, (2006) · Zbl 1128.90044
[5] Bonnans, J.F., Shapiro, A.: Perturbation Analysis of Optimization Problems. Springer Series in Operations Research. Springer, New York (2000) · Zbl 0966.49001
[6] Burer, S.; Anstreicher, K.M., Second-order-cone constraints for extended trust-region subproblems, SIAM J. Optim., 23, 432-451, (2013) · Zbl 1298.90062
[7] Conn, A.R., Gould, N.I.M., Toint, Ph.L.: Trust-Region Methods. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (2000) · Zbl 0958.65071
[8] Ding, Y.; Ge, D.; Wolkowicz, H., On equivalence of semidefinite relaxations for quadratic matrix programming, Math. Oper. Res., 36, 88-104, (2011) · Zbl 1218.90149
[9] Finsler, P.: Über das Vorkommen definiter und semidefiniter Formen in Scharen quadratischer Formen. Comment. Math. Helv. 9, 188-192 (1937) · Zbl 0016.19901
[10] Flippo, O.E.; Jansen, B., Duality and sensitivity in nonconvex quadratic optimization over an ellipsoid, Eur. J. Oper. Res., 94, 167-178, (1996) · Zbl 0930.90076
[11] Fortin, C.; Wolkowicz, H., The trust region subproblem and semidefinite programming, Optim. Methods Softw., 19, 41-67, (2004) · Zbl 1070.65041
[12] Gay, D.M., Computing optimal locally constrained steps, SIAM J. Sci. Stat. Comput., 2, 186-197, (1981) · Zbl 0467.65027
[13] Gohberg, I., Lancaster, P., Rodman, L.: Matrices and Indefinite Scalar Products. Birkhauser, Basel (1983) · Zbl 0513.15006
[14] Golub, G.H.; Ye, Q., An inverse free preconditioned Krylov subspace method for symmetric generalized eigenvalue problems, SIAM J. Sci. Comput., 24, 312-334, (2002) · Zbl 1016.65017
[15] Gould, N.I.M.; Lucidi, S.; Roma, M.; Toint, Ph.L., Solving the trust-region subproblem using the Lanczos method, SIAM J. Optim., 9, 504-525, (1999) · Zbl 1047.90510
[16] Gould, N.I.M.; Robinson, D.P.; Sue Thorne, H., On solving trust-region and other regularised subproblems in optimization, Math. Program. Comput., 2, 21-57, (2010) · Zbl 1193.65098
[17] Gould, N.I.M., Toint, Ph.L.: A quadratic programming bibliography. Technical report, Rutherford Appleton Laboratory, England (2001). www.optimization-online.org/DB_HTML/2001/02/285.html · Zbl 1058.90045
[18] Hager, W.W., Minimizing a quadratic over a sphere, SIAM J. Optim., 12, 188-208, (2001) · Zbl 1058.90045
[19] Hestenes, M.R.; McShane, E.J., A theorem on quadratic forms and its application in the calculus of variations, Trans. Am. Math. Soc., 47, 501-512, (1940) · JFM 66.0047.03
[20] Jin, Q.; Fang, S.C.; Xing, W., On the global optimality of generalized trust region subproblems, Optimization, 59, 1139-1151, (2010) · Zbl 1203.90119
[21] Lampe, J.; Rojas, M.; Sorensen, D.C.; Voss, H., Accelerating the LSTRS algorithm, SIAM J. Sci. Comput., 33, 175-194, (2011) · Zbl 1368.65096
[22] Lancaster, P.; Rodman, L., Canonical forms for Hermitian matrix pairs under strict equivalence and congruence, SIAM Rev., 47, 407-443, (2005) · Zbl 1087.15014
[23] Luo, Z.-Q.; Zhang, S., On extensions of the Frank-Wolfe theorems, Comput. Optim. Appl., 13, 87-110, (1999) · Zbl 1040.90536
[24] Moré, J.J., Generalizations of the trust region problem, Optim. Methods Softw., 2, 189-209, (1993)
[25] Moré, J.J.; Sorensen, D.C., Computing a trust region step, SIAM J. Sci. Stat. Comput., 4, 553-572, (1983) · Zbl 0551.65042
[26] Parlett, B.N.: The Symmetric Eigenvalue Problem. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (1998). Corrected reprint of the 1980 original · Zbl 0885.65039
[27] Pataki, G., On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues, Math. Oper. Res., 23, 339-358, (1998) · Zbl 0977.90051
[28] Pólik, I.; Terlaky, T., A survey of the S-lemma, SIAM Rev., 49, 371-418, (2007) · Zbl 1128.90046
[29] 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
[30] Rockafellar, R.T.: Convex Analysis. Princeton Landmarks in Mathematics. Princeton University Press, Princeton (1997). Reprint of the 1970 original, Princeton Paperbacks
[31] Rojas, M.; Santos, S.A.; Sorensen, D.C., A new matrix-free algorithm for the large-scale trust-region subproblem, SIAM J. Optim., 11, 611-646, (2000) · Zbl 0994.65067
[32] Rojas, M.; Santos, S.A.; Sorensen, D.C., Algorithm 873: LSTRS: MATLAB software for large-scale trust-region subproblems and regularization, ACM Trans. Math. Softw., 34, (2008) · Zbl 1291.65177
[33] Sorensen, D.C., Minimization of a large-scale quadratic function subject to a spherical constraint, SIAM J. Optim., 7, 141-161, (1997) · Zbl 0878.65044
[34] Stern, R.; Wolkowicz, H., Indefinite trust region subproblems and nonsymmetric eigenvalue perturbations, SIAM J. Optim., 5, 286-313, (1995) · Zbl 0846.49017
[35] Tao, P.D.; An, L.T.H., Difference of convex functions optimization algorithms (DCA) for globally minimizing nonconvex quadratic forms on Euclidean balls and spheres, Oper. Res. Lett., 19, 207-216, (1996) · Zbl 0876.90071
[36] Yakubovich, V.A., The S-procedure in nonlinear control theory, Vestn. Leningr. Univ., 4, 73-93, (1977)
[37] Ye, Y.; Zhang, S., New results on quadratic minimization, SIAM J. Optim., 14, 245-267, (2003) · Zbl 1043.90064
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.