Hidden convexity and exact semidefinite descriptions for minimizing the maximum of finitely many quadratic functions

Minimizing the pointwise maximum of finitely many arbitrary (not necessarily convex) quadratic functions over $\mathbb{R}^n$ is the epigraph QCQP $\min\{t:\ q_i(x)\le t,\ i=1,\dots,m\}$, a fundamental nonconvex problem whose tractability hinges on hidden convexity: convexity of the joint image of the quadratic map plus the nonnegative orthant, with the closely related formulations of joint-numerical-range convexity and tightness of the standard Shor semidefinite relaxation. These three senses are distinct targets — hidden convexity of $U$ is strictly weaker than convexity of the image itself — and the settled boundary differs by sense: for two quadratic functions, hidden convexity holds unconditionally (Tuy-Tuan's generalized S-lemma), the joint numerical range is unconditionally convex only for homogeneous pairs (Dines' theorem, Brickman on the sphere), while for nonhomogeneous pairs it is decided by Nguyen-Chu-Sheu's level-set-separation criterion, and the Shor SDP is tight for homogeneous pairs by Yuan's lemma. For three or more quadratic functions hidden convexity fails in general (the published counterexample involves an objective plus two quadratic constraints, i.e., three quadratic functions), and every known affirmative result imposes structural restrictions (positive-definite linear combinations, dimension conditions, simultaneous diagonalizability, eigenvalue multiplicity, polyhedral dual multiplier cones) or merely supplies a-posteriori gap tests. Determine verifiable necessary and sufficient conditions — or, as a fallback, verifiable sufficient conditions weaker than the specific hypotheses currently known — for when minimizing the maximum of finitely many quadratics admits an exact convex reformulation, in one of these distinct senses.

Background

A quadratic function on $\mathbb{R}^n$ is $q(x)=x^{T}Ax+2a^{T}x+c$ with $A$ symmetric; it is a homogeneous quadratic form when $a=0$, $c=0$. Quadratically constrained quadratic programs (QCQPs) minimize a quadratic function subject to finitely many quadratic constraints and are NP-hard in general, but they admit a standard semidefinite relaxation due to Shor: lift $X=xx^{T}$ so that $q(x)=\mathrm{tr}(AX)+2a^{T}x+c$ and replace the rank-one condition by the semidefinite constraint $\begin{pmatrix}1&x^{T}\\x&X\end{pmatrix}\succeq 0$. The relaxation is tight when its optimal value (objective-value exactness), or its projected epigraph (convex-hull exactness), coincides with that of the original problem.

The problem of minimizing the pointwise maximum of finitely many quadratics, $\min_{x}\max_{i\le m}q_{i}(x)$, is the epigraph QCQP $\min\{t:\ q_{i}(x)\le t\ \forall i\}$. Its tractability is governed by the geometry of the image of the quadratic map $q=(q_{1},\dots,q_{m})$. The joint numerical range is $\mathrm{JNR}(q)=\{(q_{1}(x),\dots,q_{m}(x)):\ x\in\mathbb{R}^{n}\}$, and the hidden-convexity set is $U(q_{1},\dots,q_{m})=\mathrm{JNR}(q)+\mathbb{R}^{m}_{+}$, the Minkowski sum with the nonnegative orthant. Because $\min_{x}\max_{i}q_{i}(x)=\min\{t:\ (t,\dots,t)\in U(q_{1},\dots,q_{m})\}$, convexity of $U$ turns the problem into linear optimization over a convex set; under mild feasibility (Slater-type) conditions it is equivalent to zero duality gap of the Lagrangian dual via the generalized S-lemma, the multi-function extension of Yakubovich's classical S-lemma for systems of quadratic inequalities.

The two-function case is classical and completely settled. Dines (1941) proved that the image of $\mathbb{R}^{n}$ under two homogeneous quadratic forms is always convex, and Brickman (1961) proved the same on the unit sphere for $n\ge 3$. Yuan's lemma (1990) gives the equivalent two-form alternative: $\max\{x^{T}A_{1}x,x^{T}A_{2}x\}\ge 0$ for all $x$ holds if and only if some convex combination of $A_{1},A_{2}$ is positive semidefinite, which is precisely tightness of the semidefinite dual bound for the homogeneous min-max problem with two forms. Polyak (1998) proved convexity of the joint numerical range of three quadratic forms when $n\ge 3$ and the forms admit a positive-definite linear combination, yielding an S-lemma for three forms under that restriction. For nonhomogeneous pairs, Tuy and Tuan (2013) showed that $U(f,g_{1})$ is convex without additional conditions (hidden convexity of one-quadratic-constraint problems goes back to Ben-Tal and Teboulle, 1996), and Nguyen, Chu and Sheu (2022) gave a polynomial-time procedure to decide convexity of the range set of two quadratic functions.

Beyond two functions the picture changes qualitatively. Jeyakumar and Li (2014, Example 2.1) exhibited $f,g_{1},g_{2}$ with $U(f,g_{1},g_{2})$ nonconvex — an objective plus two quadratic constraints, i.e., three quadratic functions in the min-max counting convention used here — and De Lara and Hiriart-Urruty conjectured (counting constraint functions $g_{1},\dots,g_{m}$ alongside a separate objective $f$) that such failures occur for every $m\ge 2$; Ai, Liang and Yuan (2025) recall that Yuan's lemma and the S-lemma 'cannot hold on three real homogeneous quadratic functions in general' and exhibit homogeneous QCQPs with three real quadratic constraints whose standard SDP relaxation has a positive optimality gap. Hence for $m\ge 3$ quadratic functions the SDP for the min-max problem is not tight in general. All known affirmative results impose structure: Polyak's positive-definite-combination condition and its extension by Song and Xia (2023) to families generated by three such forms; Haeser's (2017) extension of Yuan's lemma to matrix sets of rank at most two; Jeyakumar and Li's dimension conditions (one strictly convex quadratic constraint plus affine constraints); the conditions of Huy et al. (2026); the quadratic-eigenvalue-multiplicity and $\Gamma$-geometry (dual multiplier cone) conditions of Wang and Kılınç-Karzan; and the hidden-hyperplane-convexity conditions of Blekherman, Dey and Sun for when aggregations of the defining inequalities describe the convex hull. Ai-Liang-Yuan (2025) and Cheng and Martins (2021) instead provide a-posteriori tests that certify tightness or a gap from an optimal SDP solution pair, for three real (four complex) homogeneous constraints and for two constraints, respectively. No a priori, verifiable characterization for general finite families is known.

Problem Statement

Given finitely many quadratic functions $q_{1},\dots,q_{m}$ on $\mathbb{R}^n$, written $q_{i}(x)=x^{T}A_{i}x+2a_{i}^{T}x+c_{i}$ with each $A_{i}$ symmetric (arbitrary data; the functions need not be convex, and may be homogeneous or nonhomogeneous), consider the problem

$$v^{\ast}=\min_{x\in\mathbb{R}^{n}}\ \max_{1\le i\le m}\ q_{i}(x),$$

together with its standard homogeneous/spherical companion $\min_{\|x\|=1}\max_{i}\ x^{T}A_{i}x$, in which only the quadratic parts $A_{i}$ figure and which is the form in which the problem becomes a homogeneous QCQP with $m$ quadratic inequality constraints.

Determine verifiable necessary and sufficient conditions — or, as a fallback, verifiable sufficient conditions weaker than the hypotheses currently known for the sense it settles (for sense (a): the hypotheses (H1)–(H2) of arXiv:2601.13511, Polyak's positive-definite-combination condition; for sense (b): Polyak's positive-definite-combination condition; for sense (c): Jeyakumar and Li's dimension conditions, Wang and Kılınç-Karzan's quadratic-eigenvalue-multiplicity and polyhedral-$\Gamma$ conditions) — for when this problem admits an exact convex reformulation, in any of the following distinct senses, making explicit which sense is settled:

(a) hidden convexity: the set $U(q_{1},\dots,q_{m})=\{(q_{1}(x),\dots,q_{m}(x)):x\in\mathbb{R}^{n}\}+\mathbb{R}^{m}_{+}$ is convex, so that $v^{\ast}$ is computed by minimizing a linear function over a convex set and the generalized S-lemma (zero Lagrangian duality gap) holds under Slater-type feasibility conditions;

(b) convexity of the joint numerical range of $(q_{1},\dots,q_{m})$, i.e., of the image of the quadratic map itself;

(c) tightness of the standard Shor semidefinite relaxation of the epigraph QCQP $\min\{t:\ q_{i}(x)\le t,\ i=1,\dots,m\}$, in the sense of objective-value exactness and/or convex-hull exactness of its epigraph.

The three senses are distinct targets — hidden convexity of $U$ is strictly weaker than convexity of the image itself — so an answer settles the sense it addresses rather than any one sense settling all of them. The desired generality is arbitrary finite families beyond the currently structured cases (no dimension, convexity, or simultaneous-diagonalizability restrictions); this describes the full scope of the open question, while a resolving answer must, at minimum, handle the families of the cited negative instances (such as Ai-Liang-Yuan's three-real-form instances). The known settled boundary provides context, sense by sense: for two functions, sense (a) holds unconditionally (Tuy-Tuan; complete proof in arXiv:2601.13511); sense (b) holds unconditionally only for homogeneous pairs (Dines; Brickman on the sphere), while for nonhomogeneous pairs it is decided by Nguyen-Chu-Sheu's iff level-set-separation criterion; sense (c) for homogeneous pairs follows from Yuan's lemma. The known negative instances (Jeyakumar-Li's nonconvex $U(f,g_{1},g_{2})$ example; Ai-Liang-Yuan's three-real-form failures and positive-gap instances) involve three quadratic functions, so in this counting convention the open regime is $m\ge 3$.

References

1. Lloyd L. Dines: On the mapping of quadratic forms. Bulletin of the American Mathematical Society 47 (1941) 494-498. DOI 10.1090/S0002-9904-1941-07494-X. https://doi.org/10.1090/S0002-9904-1941-07494-X
2. Louis Brickman: On the field of values of a matrix. Proceedings of the American Mathematical Society 12 (1961) 61-66. DOI 10.1090/S0002-9939-1961-0122827-1. https://doi.org/10.1090/S0002-9939-1961-0122827-1
3. B. T. Polyak: Convexity of quadratic transformations and its use in control and optimization. Journal of Optimization Theory and Applications 99 (1998) 553-583. DOI 10.1023/A:1021798932766. https://doi.org/10.1023/A:1021798932766
4. Y. Yuan: On a subproblem of trust region algorithms for constrained optimization. Mathematical Programming 47 (1990) 53-63. DOI 10.1007/BF01580852. https://doi.org/10.1007/BF01580852
5. Imre Pólik, Tamás Terlaky: A survey of the S-lemma. SIAM Review 49 (2007) 371-418. DOI 10.1137/S003614450444614X. https://doi.org/10.1137/S003614450444614X
6. Aharon Ben-Tal, Marc Teboulle: Hidden convexity in some nonconvex quadratically constrained quadratic programming. Mathematical Programming 72 (1996) 51-63. DOI 10.1007/BF02592331. https://doi.org/10.1007/BF02592331
7. H. Tuy, H. D. Tuan: Generalized S-lemma and strong duality in nonconvex quadratic programming. Journal of Global Optimization 56 (2013) 1045-1072. DOI 10.1007/s10898-012-9917-0. https://doi.org/10.1007/s10898-012-9917-0
8. V. Jeyakumar, G. Y. Li: Trust-region problems with linear inequality constraints: exact SDP relaxation, global optimality and robust optimization. Mathematical Programming 147 (2014) 171-206. DOI 10.1007/s10107-013-0716-2. https://doi.org/10.1007/s10107-013-0716-2
9. Immanuel M. Bomze, Vaithilingam Jeyakumar, Guoyin Li: Extended trust-region problems with one or two balls: exact copositive and Lagrangian relaxations. Journal of Global Optimization 71 (2018) 551-569. DOI 10.1007/s10898-018-0607-4. https://doi.org/10.1007/s10898-018-0607-4
10. Gabriel Haeser: An extension of Yuan's lemma and its applications in optimization. arXiv:1704.01109 (2017). https://arxiv.org/abs/1704.01109
11. Michel De Lara, Jean-Baptiste Hiriart-Urruty: A fresh geometrical look at the general S-procedure. Optimization Letters 16 (2022) 1129-1135. DOI 10.1007/s11590-021-01789-y. https://doi.org/10.1007/s11590-021-01789-y
12. 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). https://arxiv.org/abs/2012.10327
13. Mengmeng Song, Yong Xia: Polyak's convexity theorem, Yuan's lemma and S-lemma: extensions and applications. arXiv:2108.08517 (2021); published as 'Calabi-Polyak convexity theorem, Yuan's lemma and S-lemma: extensions and applications', Journal of Global Optimization 85 (2023) 743-756 (online first 2022), DOI 10.1007/s10898-022-01225-0. https://arxiv.org/abs/2108.08517
14. Alex L. Wang, Fatma Kılınç-Karzan: On convex hulls of epigraphs of QCQPs. arXiv:2002.01566 (2020); IPCO 2020, Lecture Notes in Computer Science, DOI 10.1007/978-3-030-45771-6_32. https://arxiv.org/abs/2002.01566
15. Alex L. Wang, Fatma Kılınç-Karzan: On the tightness of SDP relaxations of QCQPs. Mathematical Programming 193 (2022) 33-73 (online first 2021; arXiv:1911.09195). DOI 10.1007/s10107-020-01589-9. https://arxiv.org/abs/1911.09195
16. Alex L. Wang, Fatma Kılınç-Karzan: On semidefinite descriptions for convex hulls of quadratic programs. Operations Research Letters 54 (2024) 107108 (arXiv:2403.04752). DOI 10.1016/j.orl.2024.107108. https://arxiv.org/abs/2403.04752
17. Wenbao Ai, Wei Liang, Jianhua Yuan: On the tightness of an SDP relaxation for homogeneous QCQP with three real or four complex homogeneous constraints. Mathematical Programming 211 (2025) 5-48 (online first 2024; arXiv:2304.04174). DOI 10.1007/s10107-024-02105-z. https://arxiv.org/abs/2304.04174
18. Sheng Cheng, Nuno C. Martins: An optimality gap test for a semidefinite relaxation of a quadratic program with two quadratic constraints. SIAM Journal on Optimization 31 (2021) 866-886. DOI 10.1137/19M1273761. https://doi.org/10.1137/19M1273761
19. Grigoriy Blekherman, Santanu S. Dey, Shengding Sun: Aggregations of quadratic inequalities and hidden hyperplane convexity. SIAM Journal on Optimization 34 (2024) 98-126 (arXiv:2210.01722). DOI 10.1137/22M1528215. https://arxiv.org/abs/2210.01722
20. Nguyen Quang Huy, Nguyen Huy Hung, Tran Van Nghi, Hoang Ngoc Tuan, Nguyen Van Tuyen: Hidden convexity of quadratic systems and its application to quadratic programming. arXiv:2601.13511 (2026). https://arxiv.org/abs/2601.13511
21. Huu-Quang Nguyen, Ya-Chi Chu, Ruey-Lin Sheu: On the convexity for the range set of two quadratic functions. Journal of Industrial and Management Optimization 18 (2022) 575-592. DOI 10.3934/jimo.2020169. https://doi.org/10.3934/jimo.2020169
22. Huu-Quang Nguyen: The joint range of quadratic mapping on Hilbert space. arXiv:2512.06437 (2025). https://arxiv.org/abs/2512.06437