Convexity of joint numerical ranges of three or more quadratic functions

Nguyen, Sheu and Xia (2020) showed that minimizing a convex quadratic $F(z)$ of $z=(f(x),g(x))$, where $f,g$ are $n$-variate quadratic functions, subject to linear inequalities in $z$ and the implicit constraint that $z$ belongs to the joint numerical range of $(f,g)$, is exactly solvable by semidefinite programming whenever that joint numerical range is convex; they identified the convexity of the joint numerical range of $k\ge3$ quadratic functions as the central open structural question blocking extension of their framework to $k$ functions. The problem is to characterize the convexity of the joint numerical range $\{(f_1(x),\dots,f_k(x)):x\in\mathbb{R}^n\}$ of $k\ge3$ inhomogeneous quadratic functions by necessary-and-sufficient, efficiently checkable conditions — or to prove that no such characterization exists; the $k=2$ analogue has been settled by a level-set non-separation criterion with a polynomial-time test. For $k\ge3$ only sufficient conditions and special-case results are known, so the core remains open.

Background

Minimizing a quadratic objective subject to quadratic constraints — a quadratically constrained quadratic program (QCQP) — is NP-hard in general, yet several important subclasses are 'hidden convex': a nonconvex-looking statement admits an exact convex reformulation. The classical instance is the trust region subproblem, minimizing a quadratic over a single ball constraint, which is exactly solvable by semidefinite programming (SDP, optimization of a linear objective over the cone of symmetric positive semidefinite matrices). The engine behind most such results is the S-procedure, also called the S-lemma: a theorem giving conditions under which nonnegativity of one quadratic function on the set where finitely many other quadratics are nonnegative can be certified by a single nonnegative Lagrange-type combination, which turns the original problem into a dual SDP. For two homogeneous quadratic functions the S-lemma works essentially because of a convexity theorem of Dines (1941): the joint range $\{(x^{T}Ax,\,x^{T}Bx):x\in\mathbb{R}^n\}$ of two homogeneous quadratic forms is always convex. The joint numerical range (JNR) of $k$ inhomogeneous quadratic functions $f_i(x)=x^{T}A_ix+2a_i^{T}x+\alpha_i$ is the set $\{(f_1(x),\dots,f_k(x)):x\in\mathbb{R}^n\}$ of simultaneously attainable value tuples, i.e., the image of $\mathbb{R}^n$ under a quadratic map; it is a semialgebraic set (a set defined by polynomial equalities and inequalities), and for $k\ge3$ it is in general nonconvex, with convexity a delicate structural property. Nguyen, Sheu and Xia (2020) proposed minimizing $F(f(x),g(x))$, where $F$ is a quadratic function of two variables and $f,g$ are $n$-variate quadratics, subject to linear inequalities in $z=(f(x),g(x))$ plus the implicit constraint $z\in\mathbf C$, the JNR of $(f,g)$. Their Theorem 1 is a new S-procedure: under the assumptions $\Theta\succeq0$ (the matrix of the outer quadratic $F$, making $F$ convex) and convexity of $\mathbf C$, the problem is exactly solvable by a single SDP; they applied this to solve the quadratic hypersurfaces intersection problem of Pólik and Terlaky and the problem (AQP) of minimizing the absolute value of a quadratic over one quadratic constraint. Both assumptions are genuinely needed: counterexamples due to Polyak (1998) show the S-procedure fails when the JNR is nonconvex. For two quadratic functions the convexity question is now settled: Dines's theorem covers the homogeneous case; Flores-Bazán and Opazo extended the analysis to inhomogeneous pairs and to mappings with one or two quadratic components plus linear ones; and Nguyen, Chu and Sheu (2022) proved that the range of two inhomogeneous quadratics is convex if and only if no two level sets of $f$ and $g$ separate each other, together with a polynomial-time procedure deciding convexity. The 2020 paper's conclusion states that Theorem 1 extends from $\{f,g\}$ to $k$ quadratic functions $\{f_1,\dots,f_k\}$ whenever the JNR of $\{f_1,\dots,f_k\}$ is convex and $\Theta_{k\times k}\succeq0$, and calls the convexity of the JNR 'the central feature for many optimization problems' that 'should be studied carefully in the future'. For $k\ge3$ only sufficient conditions are known: Polyak's theorem that the joint numerical range of three homogeneous quadratic forms whose matrices admit a positive definite linear combination is convex, along with his local convexity results for quadratic transformations; Song and Xia's extension of that theorem to any number of quadratic forms that can be generated by three forms having a positive definite linear combination; Dymarsky's small-ball convexity bound and hyperplane-splitting sufficient conditions for images of multidimensional quadratic maps; and the fact that when the symmetric matrices are simultaneously diagonalizable via congruence (SDC, the existence of one invertible matrix $R$ with $R^{T}A_iR$ diagonal for all $i$) the joint range is a closed convex polyhedral cone.

Problem Statement

Let $k\ge3$ and let $f_1,\dots,f_k:\mathbb{R}^n\to\mathbb{R}$ be inhomogeneous quadratic functions, with joint numerical range $\mathbf C_k=\{(f_1(x),\dots,f_k(x))\,:\,x\in\mathbb{R}^n\}.$ The problem — the structural question identified as central by Nguyen, Sheu and Xia (2020) for extending their SDP-exact, S-procedure-based framework from two to $k$ quadratic functions (their Theorem 1 extends to $\{f_1,\dots,f_k\}$ whenever $\mathbf C_k$ is convex and the outer quadratic's matrix satisfies $\Theta_{k\times k}\succeq0$) — is to characterize convexity of $\mathbf C_k$ by necessary and sufficient conditions that are efficiently checkable; or to prove that no such efficiently checkable characterization exists. Known class-specific results — linearly dependent quadratic matrices, simultaneous diagonalizability via congruence, families generated by three quadratic forms with a positive-definite linear combination, and the smallest-enclosing-ball class — remain special cases of the general $k\ge3$ question. The source's separate hopes — robust implementation of the minimizer-reconstruction step, exact treatment of a nonconvex outer quadratic $F$ (which leads toward general quartic optimization), and extension to general quartic polynomials — are not part of this problem; likewise, constructing tractable certificates or exact convex reformulations for optimization over nonconvex joint ranges is related motivation and background rather than a separate deliverable of this problem.

References

1. Huu-Quang Nguyen, Ruey-Lin Sheu, Yong Xia. Solving a new type of quadratic optimization problem having a joint numerical range constraint. arXiv:2012.10327 (2020), DOI 10.48550/arXiv.2012.10327. https://arxiv.org/abs/2012.10327
2. Lloyd L. Dines. On the mapping of quadratic forms. Bulletin of the American Mathematical Society 47(6) (1941), 494–498, DOI 10.1090/s0002-9904-1941-07494-x. https://doi.org/10.1090/s0002-9904-1941-07494-x
3. B. T. Polyak. Convexity of Quadratic Transformations and Its Use in Control and Optimization. Journal of Optimization Theory and Applications 99(3) (1998), 553–583, DOI 10.1023/a:1021798932766. https://doi.org/10.1023/A:1021798932766
4. Fabián Flores-Bazán, Felipe Opazo. Joint-range convexity for a pair of inhomogeneous quadratic functions and applications to QP. arXiv:1508.01612 (2015). https://arxiv.org/abs/1508.01612
5. Fabián Flores-Bazán, Felipe Opazo. Characterizing Convexity of Images for Quadratic-Linear Mappings with Applications in Nonconvex Quadratic Optimization. SIAM Journal on Optimization 31(3) (2021), 1774–1796, DOI 10.1137/19M1240484. https://doi.org/10.1137/19M1240484
6. Anatoly Dymarsky. Convexity of a Small Ball Under Quadratic Map. arXiv:1410.1553 (2014). https://arxiv.org/abs/1410.1553
7. Anatoly Dymarsky. On the Convexity of Image of a Multidimensional Quadratic Map. arXiv:1410.2254 (2014). https://arxiv.org/abs/1410.2254
8. Thi-Ngan Nguyen, Van-Bong Nguyen, Thanh-Hieu Le, Ruey-Lin Sheu. Simultaneous diagonalization via congruence of m real symmetric matrices and its implications in optimization. arXiv:2004.06360 (2020). https://arxiv.org/abs/2004.06360
9. Huu-Quang Nguyen, Ya-Chi Chu, Ruey-Lin Sheu. On the convexity for the range set of two quadratic functions. Journal of Industrial & Management Optimization 18(1) (2022), 575; DOI 10.3934/jimo.2020169; arXiv:2503.01225 (2025). https://arxiv.org/abs/2503.01225
10. Van-Bong Nguyen, Huu-Quang Nguyen. A new separable property of the joint numerical range of quadratic functions and its applications to the Smallest Enclosing Ball Problem. arXiv:2501.15399 (2025). https://arxiv.org/abs/2501.15399
11. Huu-Quang Nguyen. The Joint Range of Quadratic Mapping on Hilbert Space. arXiv:2512.06437 (2025). https://arxiv.org/abs/2512.06437
12. Huu-Quang Nguyen, Ruey-Lin Sheu. Quadratic optimization problems with non-crossover and non-separable constraint boundaries. Journal of Global Optimization (2025), DOI 10.1007/s10898-025-01497-2. https://doi.org/10.1007/s10898-025-01497-2
13. Mengmeng Song, Yong Xia. Calabi-Polyak convexity theorem, Yuan's lemma and S-lemma: extensions and applications. Journal of Global Optimization 85 (2022), 743–756, DOI 10.1007/s10898-022-01225-0; arXiv:2108.08517 (2021). https://arxiv.org/abs/2108.08517
14. Liding Xu, Sebastian Pokutta. Joint-Range Inequalities for Nonconvex QCQPs. arXiv:2608.03318 (2026). https://arxiv.org/abs/2608.03318