Nguyen, Sheu and Xia (2020) showed that minimizing a convex quadratic F(z)F(z) of z=(f(x),g(x))z=(f(x),g(x)), where f,gf,g are nn-variate quadratic functions, subject to linear inequalities in zz and the implicit constraint that zz belongs to the joint numerical range of (f,g)(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≥3k\ge3 quadratic functions as the central open structural question blocking extension of their framework to kk functions. The problem is to characterize the convexity of the joint numerical range {(f1(x),…,fk(x)):x∈Rn}\{(f_1(x),\dots,f_k(x)):x\in\mathbb{R}^n\} of k≥3k\ge3 inhomogeneous quadratic functions by necessary-and-sufficient, efficiently checkable conditions — or to prove that no such characterization exists; the k=2k=2 analogue has been settled by a level-set non-separation criterion with a polynomial-time test. For k≥3k\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 {(xTAx, xTBx):x∈Rn}\{(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 kk inhomogeneous quadratic functions fi(x)=xTAix+2aiTx+αif_i(x)=x^{T}A_ix+2a_i^{T}x+\alpha_i is the set {(f1(x),…,fk(x)):x∈Rn}\{(f_1(x),\dots,f_k(x)):x\in\mathbb{R}^n\} of simultaneously attainable value tuples, i.e., the image of Rn\mathbb{R}^n under a quadratic map; it is a semialgebraic set (a set defined by polynomial equalities and inequalities), and for k≥3k\ge3 it is in general nonconvex, with convexity a delicate structural property. Nguyen, Sheu and Xia (2020) proposed minimizing F(f(x),g(x))F(f(x),g(x)), where FF is a quadratic function of two variables and f,gf,g are nn-variate quadratics, subject to linear inequalities in z=(f(x),g(x))z=(f(x),g(x)) plus the implicit constraint z∈Cz\in\mathbf C, the JNR of (f,g)(f,g). Their Theorem 1 is a new S-procedure: under the assumptions Θ⪰0\Theta\succeq0 (the matrix of the outer quadratic FF, making FF convex) and convexity of C\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 ff and gg separate each other, together with a polynomial-time procedure deciding convexity. The 2020 paper's conclusion states that Theorem 1 extends from {f,g}\{f,g\} to kk quadratic functions {f1,…,fk}\{f_1,\dots,f_k\} whenever the JNR of {f1,…,fk}\{f_1,\dots,f_k\} is convex and Θk×k⪰0\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≥3k\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 RR with RTAiRR^{T}A_iR diagonal for all ii) the joint range is a closed convex polyhedral cone.

Problem Statement

Let k≥3k\ge3 and let f1,…,fk:Rn→Rf_1,\dots,f_k:\mathbb{R}^n\to\mathbb{R} be inhomogeneous quadratic functions, with joint numerical range Ck={(f1(x),…,fk(x)) : x∈Rn}.\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 kk quadratic functions (their Theorem 1 extends to {f1,…,fk}\{f_1,\dots,f_k\} whenever Ck\mathbf C_k is convex and the outer quadratic's matrix satisfies Θk×k⪰0\Theta_{k\times k}\succeq0) — is to characterize convexity of Ck\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≥3k\ge3 question. The source's separate hopes — robust implementation of the minimizer-reconstruction step, exact treatment of a nonconvex outer quadratic FF (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