On local minimizers of generalized trust-region subproblem

Abstract

Generalized trust-region subproblem (GT) is a nonconvex quadratic optimization with a single quadratic constraint. It reduces to the classical trust-region subproblem (T) if the constraint set is a Euclidean ball. (GT) is polynomially solvable based on its inherent hidden convexity. In this paper, we study local minimizers of (GT). Unlike (T) with at most one local nonglobal minimizer, we can prove that two-dimensional (GT) has at most two local nonglobal minimizers, which are shown by example to be attainable. The main contribution of this paper is to prove that, at any local nonglobal minimizer of (GT), not only the strict complementarity condition holds, but also the standard second-order sufficient optimality condition remains necessary. As a corollary, finding all local nonglobal minimizers of (GT) or proving the nonexistence can be done in polynomial time. Finally, for (GT) in complex domain, we prove that there is no local nonglobal minimizer, which demonstrates that real-valued optimization problem may be more difficult to solve than its complex version.

arXiv comment20 pages, 1 figure

References in corpus (7)

• Alternating Minimization Algorithms for Hybrid Precoding in Millimeter Wave MIMO Systems
• Consensus-ADMM for General Quadratically Constrained Quadratic Programming
• A Second-Order Cone Based Approach for Solving the Trust Region Subproblem and Its Variants
• Simultaneous Diagonalization of Matrices and its Applications in Quadratically Constrained Quadratic Programming
• Trust Region Subproblem with a Fixed Number of Additional Linear Inequality Constraints has Polynomial Complexity
• On Local Minimizers of Quadratically Constrained Nonconvex Homogeneous Quadratic Optimization with at Most Two Constraints
• Trust-region and $p$-regularized subproblems: local nonglobal minimum is the second smallest objective function value among all first-order stationary points