×

Strong duality for generalized trust region subproblem: S-lemma with interval bounds. (English) Zbl 1354.90089

Summary: With the help of the newly developed S-lemma with interval bounds, we show that strong duality holds for the interval bounded generalized trust region subproblem (GTRS) under some mild assumptions, which answers an open problem raised by T. K. Pong and H. Wolkowicz [Comput. Optim. Appl. 58, No. 2, 273–322 (2014; Zbl 1329.90100)].

MSC:

90C20 Quadratic programming
90C46 Optimality conditions and duality in mathematical programming

Citations:

Zbl 1329.90100

Software:

GQTPAR
PDFBibTeX XMLCite
Full Text: DOI arXiv

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.M., Toint, Ph.L.: Trust-Region Methods. SIAM, Philadelphia (2000) · Zbl 0958.65071
[3] Derinkuyu, K., Pinar, M.Ç.: On the S-procedure and some variants. Math. Methods Oper. Res. 64, 55-77 (2006) · Zbl 1115.93025 · doi:10.1007/s00186-006-0070-8
[4] Flippo, O.E., Jansen, B.: Duality and sensitivity in nonconvex quadratic optimization over an ellipsoid. Eur. J. Oper. Res. 94(1), 167-178 (1996) · Zbl 0930.90076 · doi:10.1016/0377-2217(95)00199-9
[5] Fortin, C., Wolkowicz, H.: The trust region subproblem and semidefinite programming. Optim. Methods Softw. 19(1), 41-67 (2004) · Zbl 1070.65041 · doi:10.1080/10556780410001647186
[6] Gay, D.M.: Computing optimal locally constrained steps. SIAM J. Sci. Stat. Comput. 2, 186-197 (1981) · Zbl 0467.65027 · doi:10.1137/0902016
[7] Horn, R., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge (1985) · Zbl 0576.15001 · doi:10.1017/CBO9780511810817
[8] Hsia, Y., Lin, G.X., Sheu, R.L.: A revisit to quadratic programming with one inequality quadratic constraint via matrix pencil. Pacific J. Optim. 10(3), 461-481 (2014) · Zbl 1327.90168
[9] Moré, J.J., Sorensen, D.C.: Computing a trust region step. SIAM J. Sci. Stat. Comput. 4, 553-572 (1983) · Zbl 0551.65042 · doi:10.1137/0904038
[10] Moré, J.J.: Generalizations of the trust region problem. Optim. Methods Softw. 2, 189-209 (1993) · doi:10.1080/10556789308805542
[11] Pólik, I.; Terlaky, T., No article title, A Survey of S-lemma. SIAM review., 49, 371-418 (2007) · Zbl 1128.90046 · doi:10.1137/S003614450444614X
[12] Polyak, B.T.: Convexity of quadratic transformations and its use in control and optimization. J. Optim. Theory Appl. 99, 553-583 (1998) · Zbl 0961.90074 · doi:10.1023/A:1021798932766
[13] Pong, T.K., Wolkowicz, H.: Generalizations of the trust region subproblem. Comput. Optim. Appl. 58(2), 273-322 (2014) · Zbl 1329.90100 · doi:10.1007/s10589-013-9635-7
[14] Rendl, F., Wolkowicz, H.: A semidefinite framework for trust region subproblems with applications to large scale minimization. Math. Program. 77(2), 273-299 (1997) · Zbl 0888.90137
[15] Stern, R., Wolkowicz, H.: Indefinite trust region subproblems and nonsymmetric eigenvalue perturbations. SIAM J. Optim. 5(2), 286-313 (1995) · Zbl 0846.49017 · doi:10.1137/0805016
[16] Xia, Y., Wang, S., Sheu, R.L.: S-lemma with Equality and its Applications. (2014). arXiv:1403.2816 · Zbl 1333.90086
[17] Yakubovich, V.A.: S-procedure in nonlinear control theory. Vestn. Leningrad Univ. 1, 62-77 (1971). (in Russian) · Zbl 0232.93010
[18] Yakubovich, V.A.: S-procedure in nonlinear control theory. Vestn. Leningrad Univ. 4, 73-93 (1977). (English translation)
[19] Ye, Y., Zhang, S.: New results on quadratic minimization. SIAM J. Optim. 14, 245-267 (2003) · Zbl 1043.90064 · doi:10.1137/S105262340139001X
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.