On the Non-Global Local Minimizers of the Generalized Trust-Region Subproblem and Its Equality-Constrained Version: Number and Computation

Source abstract

In this paper, we study the non-global local minimizers of the generalized trust-region subproblem (GTR), min${x^⊤A_0x + 2b^⊤ _0x|x^⊤A_1x + 2b^⊤_1x + c1 ≤ 0}$, and its equality constrained version (GTRE), which will be candidates of the global minimizers of the nonconvex quadratically multi-constrained quadratic programming when the hard-case happens. Specifically, if there exists $µ_1 ∈ \mathcal{R}$ such that $A_0 + µ_1A_1 ≻ 0$, we prove for GTR and GTRE that, when $A_1 ⪰ 0 (or ⪯ 0)$ there may exist at most one non-global local minimizer, and when A1 is indefinite there may exist at most two non-global local minimizers. Moreover, if there exists $µ_1 ∈ \mathcal{R}$ such that $A_0 +µ_1A_1 ≺ 0$, we prove also that GTR and GTRE may have at most one non-global local minimizer. All the above three upper bounds are tight, i.e., none of them can be improved again. In summary, the famous Maríınez’s result is successfully generalized from $A_1 ≻ 0$ to the case that $µ_0A_0+µ_1A_1 ≻ 0$ for some $µ_0,µ_1 ∈ \mathcal{R}$. Finally, an algorithm is proposed either to find all the non-global local minimizers of GTR and GTRE or to confirm their nonexistence in a tolerance. Preliminary numerical results demonstrate the effectiveness of the algorithm