Counting and characterizing local non-global minimizers of the two-constraint homogeneous quadratic program (QQ2)

For the homogeneous quadratic program (QQ2) — minimize $q_0(x)=x^\top A_0 x$ subject to $q_1(x)=x^\top A_1 x=1$ and $q_2(x)=x^\top A_2 x\le 1$ with symmetric data in $\mathbb{R}^{n\times n}$ , $n\ge 3$ — this problem concerns the number and characterization of its local non-global minimizers. Song, Liu and Xia (arXiv:2107.05816; published SIAM J. Optim. 2023) conjectured that (QQ2) has at most four strict local non-global minimizers (a bound attained by an explicit $\mathbb{R}^3$ instance) and proposed a sufficient-condition characterization of non-strict local non-global minimizers via the KKT system, a second-order condition on the tangent subspace, and a null-direction condition. Later work of Ai, Zhang and Yuan (arXiv:2409.01697; J. Comput. Math. 2026) refuted the characterization conjecture with an explicit $\mathbb{R}^4$ counterexample and confirmed a related single-constraint conjecture, but left the at-most-four counting conjecture untouched. The surviving open core is: prove or disprove the at-most-four bound, and find correct necessary-and-sufficient conditions for non-strict local non-global minimizers of (QQ2).

Background

A quadratically constrained quadratic program (QCQP) minimizes a quadratic objective subject to quadratic constraints; here all functions are homogeneous (no linear terms). The trust-region subproblem (TRS) — minimizing a quadratic over a Euclidean ball — is the classical special case: Martínez showed in 1994 that TRS has at most one local non-global minimizer, where a local non-global minimizer is a point that minimizes the objective in some neighborhood yet has strictly smaller objective values elsewhere on the feasible set. The generalized trust-region subproblem (GTR or GT) replaces the ball by a general quadratic constraint, and its equality-constrained variant (GTRE) uses a single equality constraint; the generalized CDT problem (GCDT) is the two-constrained extension studied here as (QQ2), which also contains the ellipsoidal regularized total least squares problem as a special case. For such problems a global minimizer admits a complete characterization: the KKT conditions (stationarity of the Lagrangian, feasibility, and complementarity with nonnegative multipliers on the inequality) together with positive semidefiniteness of $A_0+\alpha A_1+\beta A_2$ . Local non-global minimizers are harder: they satisfy the KKT conditions with multipliers $\alpha\in\mathbb{R}$ , $\beta\ge 0$ and second-order necessary conditions — the Hessian of the Lagrangian $A_0+\alpha A_1+\beta A_2$ must be nonnegative on the tangent subspace $\{v : v^\top A_1 x^*=0,\ v^\top A_2 x^*=0\}$ — but the second-order sufficient condition (SOSC, i.e. positive definiteness on that subspace) can fail, giving rise to non-strict local minimizers, of which (QQ2) may have infinitely many, unlike TRS. Song–Liu–Xia proved that at any local non-global minimizer of (QQ2) both the linear independence constraint qualification and strict complementarity hold, and asked two questions: a counting question — is four an upper bound on the number of strict local non-global minimizers? — and a characterization question — is the natural list of necessary conditions (KKT plus tangent-subspace second-order nonnegativity plus existence of a null direction $\bar v$ with $\bar v^\top(A_2-A_1)\bar v=0$ ) already sufficient for a non-strict candidate to be a local non-global minimizer?

Problem Statement

Consider (QQ2): minimize $q_0(x)=x^\top A_0 x$ over $x\in\mathbb{R}^n$ ( $n\ge 3$ ) subject to $q_1(x)=x^\top A_1 x=1$ and $q_2(x)=x^\top A_2 x\le 1$ , where $A_0,A_1,A_2$ are arbitrary real symmetric matrices. (a) Prove or disprove that (QQ2) has at most four strict local non-global minimizers; the bound is known to be attained in $\mathbb{R}^3$ , so a proof would be sharp and a disproof requires an instance with five or more pairwise distinct strict local non-global minimizers. (b) Since the conjectured sufficient-condition characterization of non-strict local non-global minimizers (KKT with multipliers $\alpha\in\mathbb{R}$ , $\beta>0$ , second-order nonnegativity on the tangent subspace, and existence of a null direction $\bar v$ with $\bar v^\top(A_2-A_1)\bar v=0$ ) has been refuted by an explicit counterexample, establish correct necessary-and-sufficient conditions under which a KKT point of (QQ2) is a non-strict local non-global minimizer.

References

Mengmeng Song, Hongying Liu, Yong Xia, 'On local minimizers of quadratically constrained nonconvex homogeneous quadratic optimization with at most two constraints', arXiv:2107.05816 (2021), https://arxiv.org/abs/2107.05816
Mengmeng Song, Hongying Liu, Jiulin Wang, Yong Xia, 'On local minimizers of nonconvex homogeneous quadratically constrained quadratic optimization with at most two constraints', SIAM Journal on Optimization 33(1):267-293 (2023), DOI:10.1137/21M1416746, https://doi.org/10.1137/21M1416746
Wenbao Ai, Mengxiao Zhang, Jianhua Yuan, 'New results on the local-nonglobal minimizers of the generalized trust-region subproblem', arXiv:2409.01697 (2024), https://arxiv.org/abs/2409.01697
Wenbao Ai, Mengxiao Zhang, Jianhua Yuan, 'On the non-global local minimizers of the generalized trust-region subproblem and its equality-constrained version: number and computation', Journal of Computational Mathematics (2026), DOI:10.4208/jcm.2512-m2025-0164, https://doi.org/10.4208/jcm.2512-m2025-0164
Jiulin Wang, Mengmeng Song, Yong Xia, 'On local minimizers of generalized trust-region subproblem', arXiv:2108.13729 (2021), https://arxiv.org/abs/2108.13729