×

zbMATH — the first resource for mathematics

An efficient algorithm for solving the generalized trust region subproblem. (English) Zbl 1393.90098
Summary: In this paper, we consider the interval bounded generalized trust region subproblem (GTRS) which is the problem of minimizing a general quadratic function subject to an upper and lower bounded general quadratic constraint. Under the assumption that two matrices from the objective and the constraint functions can be simultaneously diagonalizable via congruence, a diagonalization-based algorithm is introduced to solve it by showing that GTRS is indeed equivalent to a linearly constrained convex univariate problem. Some numerical experiments are given to show the effectiveness of the proposed method and to compare it with the extended Rendl-Wolkowicz algorithm due to Pong and Wolkowicz.

MSC:
90C26 Nonconvex programming, global optimization
90C20 Quadratic programming
PDF BibTeX XML Cite
Full Text: DOI
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] Burer, S; Yang, B, The trust region subproblem with non-intersecting linear constraints, Math Program, 40, 1-12, (2013) · Zbl 1308.90121
[3] Beck, A; Ben-Tal, A; Teboulle, M, Finding a global optimal solution for a quadratically constrained fractional quadratic problem with applications to the regularized total least squares, SIAM J Matrix Anal Appl, 28, 425-445, (2006) · Zbl 1115.65065
[4] Conn AR, Gould NI, Toint PL (2000) Trust region methods. SIAM, Philadelphia · Zbl 0958.65071
[5] Celis, MR; Dennis, JE; Tapia, AR, A trust region strategy for nonlinear equality constrained optimization, Numer Optim, 1984, 71-82, (1985) · Zbl 0566.65048
[6] Fletcher R (1987) Practical methods of optimization. Wiley, New York · Zbl 0905.65002
[7] Fortin, C; Wolkowicz, H, The trust region subproblem and semidefinite programming, Optim Methods Softw, 19, 41-67, (2004) · Zbl 1070.65041
[8] Fu, M; Luo, ZQ; Ye, Y, Approximation algorithms for quadratic programming, J Combin Optim, 2, 29-50, (1998) · Zbl 0896.90154
[9] Golub, GH; 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
[10] Gould, NI; Lucidi, S; Roma, M; Toint, PL, Solving the trust-region subproblem using the Lanczos method, SIAM J Optim, 9, 504-525, (1999) · Zbl 1047.90510
[11] Gould, NI; Robinson, DP; Thorne, HS, On solving trust-region and other regularised subproblems in optimization, Math Program Comput, 2, 21-57, (2010) · Zbl 1193.65098
[12] Golub, GH; Loan, CF, An analysis of the total least squares problem, SIAM J Numer Anal, 17, 883-893, (1980) · Zbl 0468.65011
[13] Hsia, Y; Lin, GX; Sheu, RL, A revisit to quadratic programming with one inequality quadratic constraint via matrix pencil, Pac J Optim, 10, 461-481, (2014) · Zbl 1327.90168
[14] Hansen, PC, Regularization tools, a Matlab package for analysis of discrete regularization problems, Numer Algo, 6, 135, (1994) · Zbl 0789.65029
[15] Jin, Q; Fang, SC; Xing, W, On the global optimality of generalized trust region subproblems, Optimization, 59, 1139-1151, (2010) · Zbl 1203.90119
[16] Lancaster, P; Rodman, L, Canonical forms for Hermitian matrix pairs under strict equivalence and congruence, SIAM Rev, 47, 407-443, (2005) · Zbl 1087.15014
[17] Moré, JJ; Sorensen, DC, Computing a trust region step, SIAM J Sci Stat Comput, 4, 553-572, (1983) · Zbl 0551.65042
[18] Moré, JJ, Generalizations of the trust region problem, Optim Methods Softw, 2, 189-209, (1993)
[19] Pong, TK; Wolkowicz, H, The generalized trust region subproblem, Comput Optim Appl, 58, 273-322, (2014) · Zbl 1329.90100
[20] 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
[21] Stern, RJ; Wolkowicz, H, Indefinite trust region subproblems and nonsymmetric eigenvalue perturbations, SIAM J Optim, 5, 286-313, (1995) · Zbl 0846.49017
[22] Sturm, JF; Zhang, S, On cones of nonnegative quadratic functions, Math Oper Res, 28, 246-267, (2003) · Zbl 1082.90086
[23] Salahi M, Fallahi S, Terlaky T (2016) Minimizing an indefinite quadratic function subject to a single indefinite quadratic constraint, Technical Report, University of Guilan · Zbl 1398.90116
[24] Sima, DM; Huffel, S; Golub, GH, Regularized total least squares based on quadratic eigenvalue problem solvers, BIT Numer Math, 44, 793-812, (2004) · Zbl 1079.65048
[25] Huffel, S; Vandewalle, J, The total least squares problem: computational aspects and analysis, Front Appl Math, 9, 1-87, (1991) · Zbl 0789.62054
[26] Wang S, Xia Y (2015) Strong duality for generalized trust region subproblem: S-lemma with interval bounds. Optim Lett 9:1063-1073 · Zbl 1354.90089
[27] 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.