Local nonglobal minima for solving large-scale extended trust-region subproblems

• Published in: Computational optimization and applications 2017-03, Vol.66 (2), p.223-244
• Main Authors: Salahi, Maziar, Taati, Akram, Wolkowicz, Henry
• Format: Article
• Language: English
• Subjects: Algorithms; Analysis; Applied mathematics; Computer science; Convex and Discrete Geometry; Eigenvalues; Inequalities; Management Science; Mathematics; Mathematics and Statistics; Minima; Norms; Operations Research; Operations Research/Decision Theory; Optimization; Quadratic equations; Statistics; Studies; Surface hardness
• ISSN: 0926-6003; 1573-2894
• DOI: 10.1007/s10589-016-9867-4

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.