{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,5]],"date-time":"2026-10-05T22:03:19Z","timestamp":1791237799156,"version":"4.1.0"},"reference-count":20,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2003,1]]},"abstract":"<jats:p>In this paper we present several new results on minimizing an indefinite quadratic function under quadratic\/linear constraints. The emphasis is placed on the case in which the constraints are two quadratic inequalities. This formulation is termed the extended trust region subproblem in this paper, to distinguish it from the ordinary trust region subproblem, in which the constraint is a single ellipsoid. The computational complexity of the extended trust region subproblem in general is still unknown. In this paper we consider several interesting cases related to this problem and show that for those cases the corresponding semidefinite programming relaxation admits no gap with the true optimal value, and consequently we obtain polynomial-time procedures for solving those special cases of quadratic optimization. For the extended trust region subproblem itself, we introduce a parameterized problem and prove the existence of a trajectory that will lead to an optimal solution. Combining this with a result obtained in the first part of the paper, we propose a polynomial-time solution procedure for the extended trust region subproblem arising from solving nonlinear programs with a single equality constraint.<\/jats:p>","DOI":"10.1137\/s105262340139001x","type":"journal-article","created":{"date-parts":[[2003,7,25]],"date-time":"2003-07-25T21:13:10Z","timestamp":1059167590000},"page":"245-267","source":"Crossref","is-referenced-by-count":195,"title":["New Results on Quadratic Minimization"],"prefix":"10.1137","volume":"14","author":[{"given":"Yinyu","family":"Ye","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shuzhong","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1016\/0025-5610(94)00071-Z"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970777"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"M.Celis, J.Dennis, R.Tapia, A trust region strategy for nonlinear equality constrained optimization, SIAM, Philadelphia, PA, 1985, 71\u20138287c:90175","DOI":"10.21236\/ADA454933"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009739827008"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/BF01292610"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02796-7"},{"key":"R8","unstructured":"S. Kim, M. Kojima, and Y. Ye,\n                      On Quadratic Minimization with Quadratic Constraints\n                      , discussion note, Department of Management Sciences, The University of Iowa, Iowa City, IA, 2001."},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511983658"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1007\/s101070050100"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1080\/10556789808805690"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"YuriNesterov, HenryWolkowicz, YinyuYe, Semidefinite programming relaxations of nonconvex quadratic optimization, Internat. Ser. Oper. Res. Management Sci., Vol. 27, Kluwer Acad. Publ., Boston, MA, 2000, 361\u20134191778235","DOI":"10.1007\/978-1-4615-4381-7_13"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"Y. Nesterov and A. Nemirovskii,\n                      Interior\u2010Point Polynomial Algorithms in Convex Programming\n                      , SIAM Stud. Appl. Math. 13, Philadelphia, 1994.","DOI":"10.1137\/1.9781611970791"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1023\/A:1021798932766"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008203903341"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1137\/0805016"},{"key":"R17","unstructured":"JosSturm, Theory and algorithms of semidefinite programming, Appl. Optim., Vol. 33, Kluwer Acad. Publ., Dordrecht, 2000, 1\u20131942001e:90001"},{"key":"R18","unstructured":"J. F. Sturm and S. Zhang,\n                      On cones of nonnegative quadratic functions\n                      , Math. Oper. Res., to appear."},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1007\/s10107980012a"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580852"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S105262340139001X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:23:09Z","timestamp":1787332989000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S105262340139001X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,1]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2003,1]]}},"alternative-id":["10.1137\/S105262340139001X"],"URL":"https:\/\/doi.org\/10.1137\/s105262340139001x","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003,1]]}}}