Relaxing the three-generator hypothesis of Song-Xia's second-order optimality theorem and nonhomogeneous extensions of the extended quadratic alternative theorems

Song and Xia (arXiv:2108.08517; J. Glob. Optim. 85:743-756, 2023) extended the Calabi-Polyak convexity theorem by proving that the joint numerical range of any number of homogeneous quadratic forms is a convex cone whenever the forms are generated by three forms having a positive definite linear combination, and derived from it an extended Yuan's lemma and an extended S-lemma. Two applications anchor the paper: a sufficient condition -- the Hessians of the Lagrangian at the vertices of the multiplier set are generated by three matrices with a positive definite linear combination -- under which the standard second-order necessary optimality condition holds at a local minimizer satisfying the Mangasarian-Fromovitz constraint qualification, and strong duality for homogeneous quadratic optimization with two bilateral quadratic constraints. The authors state that it is unknown whether the second-order hypothesis can be relaxed, and that nonhomogeneous analogues of their alternative theorems remain to be developed.

Background

Consider a nonlinear programming problem (NLP): minimize a twice continuously differentiable objective $f(x)$ subject to inequality constraints $g_i(x)\le 0$ and equality constraints $h_j(x)=0$. At a feasible point $\bar x$, the Lagrangian $L(x,\lambda,\mu)=f(x)+\sum_i\lambda_i g_i(x)+\sum_j\mu_j h_j(x)$ combines objective and constraints with multiplier vectors; the Lagrange multiplier set $\Lambda(\bar x)$ collects the nonnegative multipliers that reproduce the gradient of $f$ from the active constraint gradients (the KKT multipliers); and the critical cone $C(\bar x)$ consists of the directions $v$ that stay feasible to first order (non-increasing on the active inequalities, annihilating the equality gradients) and do not increase the objective to first order. The standard second-order necessary optimality condition (SONC) at a local minimizer $\bar x$ requires a single multiplier $(\lambda,\mu)\in\Lambda(\bar x)$ whose Lagrangian Hessian satisfies $v^\top\nabla^2 L(\bar x,\lambda,\mu)v\ge 0$ for every $v\in C(\bar x)$. Under the linear independence constraint qualification (LICQ) the multiplier set is a single point and SONC follows from the Fritz John conditions; under the weaker Mangasarian-Fromovitz constraint qualification (MFCQ: the equality gradients are linearly independent and some direction strictly decreases all active inequalities while annihilating the equality gradients), $\Lambda(\bar x)$ is only a nonempty bounded polytope (Gauvin's theorem), and Anitescu constructed a degenerate program where MFCQ holds yet SONC fails -- so additional structure is needed between MFCQ and LICQ.

The relevant structure is convexity of joint numerical ranges of quadratic forms. For symmetric matrices $A_1,\dots,A_m$ the joint numerical range is $\{(x^\top A_1 x,\dots,x^\top A_m x):x\in\mathbb{R}^n\}$. Dines (1941) proved it is a convex cone for $m=2$. Polyak (1998), crediting an argument of Calabi, proved that for $n\ge 3$ and $m=3$ it is a convex cone whenever the three forms admit a positive definite linear combination; for $m>3$ this fails in general even with such a combination (Polyak's counterexample). Song and Xia (2021; journal version 2023) proved that for $n\ge 3$ the joint numerical range of any number $m\ge 1$ of quadratic forms is a convex cone whenever the Hessian matrices can be generated by three matrices $A_1,A_2,A_3$ (each Hessian is a real linear combination of them) that admit a positive definite linear combination -- the extended Calabi-Polyak theorem, which also covers Dines' theorem.

This convexity powers quadratic alternative theorems, which certify that a system of quadratic inequalities cannot hold by exhibiting a nonnegative multiplier combination. Yuan's lemma (1990) states that $\max\{x^\top A_1 x,x^\top A_2 x\}\ge 0$ for all $x\in\mathbb{R}^n$ if and only if some convex combination $t_1 A_1+t_2 A_2$ is positive semidefinite. The S-lemma (Yakubovich; see the survey of Polik and Terlaky) is the analogous equivalence for an implication between two quadratic inequalities and is a workhorse of robust optimization and control theory. Song and Xia extended Yuan's lemma to $m$ forms generated by three forms with a positive definite linear combination, valid on regular cones of dimension at least three (cones $K$ with $K\cup(-K)$ a subspace, a class containing all first-order cones $K=S+\mathbb{R}_+d$). Applied at a local minimizer $x^*$ satisfying MFCQ, with $(\lambda^i,\mu^i)$ the vertices of $\Lambda(x^*)$, this yields their second-order result: if the vertex Hessians $\{\nabla^2 L(x^*,\lambda^i,\mu^i)\}$ are generated by three matrices with a positive definite linear combination, then SONC holds at $x^*$ whenever the critical cone is a regular cone of dimension at least three (Theorem 7 in the arXiv version's numbering, stated for every regular subcone $K\subseteq C(x^*)$ with $\dim K\ge 3$, the multiplier a priori depending on $K$). This strictly generalizes Baccari and Trad's assumption that $\Lambda(x^*)$ is a bounded line segment and Haeser's assumption that the vertex Hessians span a space of rank at most two. The same convexity extends the homogeneous S-lemma and implies strong duality for homogeneous quadratic optimization with two bilateral quadratic constraints, covering the generalized trust region subproblem with interval bounds and the two-sided regularized total least squares problem.

All of these extended results concern homogeneous quadratic forms $x^\top A x$. For nonhomogeneous quadratic functions $f_i(x)=x^\top A_i x+2a_i^\top x+b_i$, the picture is only partially understood. The classical S-lemma handles a single nonhomogeneous quadratic constraint; for a pair of nonhomogeneous quadratics the convexity of the range $\{(f_1(x),f_2(x)):x\in\mathbb{R}^n\}$ has been characterized -- Flores-Bazan and Opazo gave joint-range convexity extensions and S-lemma validity conditions for inhomogeneous pairs, and Nguyen, Chu and Sheu proved the range is convex exactly when no two level sets separate each other, a condition checkable in polynomial time. No analogue is known for three or more nonhomogeneous forms, nor for bilateral nonhomogeneous constraint pairs beyond the single-constraint interval-bound case.

Problem Statement

The problem has two linked parts, Part A and Part B (i)-(iii), both extending the Song-Xia hidden-convexity machinery (the extended Calabi-Polyak convexity theorem for joint numerical ranges and the alternative theorems derived from it).

Part A (relaxing the second-order hypothesis). Let $x^*$ be a local minimizer of a nonlinear program at which MFCQ holds, let $(\lambda^1,\mu^1),\dots,(\lambda^m,\mu^m)$ be the vertices of the Lagrange multiplier set $\Lambda(x^*)$, and let $C(x^*)$ be the critical cone. Song and Xia proved (Theorem 7 of arXiv:2108.08517) that the standard second-order necessary optimality condition -- existence of a single $(\lambda,\mu)\in\Lambda(x^*)$ with $v^\top\nabla^2 L(x^*,\lambda,\mu)v\ge 0$ for all $v\in C(x^*)$ -- holds whenever there exist symmetric matrices $A_1,A_2,A_3$ such that every vertex Hessian $\nabla^2 L(x^*,\lambda^i,\mu^i)$ is a real linear combination of $A_1,A_2,A_3$ and some linear combination $s_1A_1+s_2A_2+s_3A_3$ is positive definite, provided the critical cone $C(x^*)$ is a regular cone of dimension at least three. Determine whether and how far this hypothesis can be weakened while the conclusion still holds for every MFCQ local minimizer. Part A is resolved either by a strictly weaker structural condition that provably guarantees the conclusion for every MFCQ local minimizer or by a proof that the three-generator hypothesis is already sharp.

Part B (nonhomogeneous alternative theorems). The Song-Xia convexity theorem and its derived alternative theorems concern homogeneous quadratic forms $x^\top A x$. For nonhomogeneous quadratic functions $f_i(x)=x^\top A_i x+2a_i^\top x+b_i$, establish or rule out: (i) convexity of the joint range $\{(f_1(x),\dots,f_m(x)):x\in\mathbb{R}^n\}$ for $m\ge 3$ under a generator condition of the Song-Xia type, restricted to the nondegenerate regime in which every pair $\{f_i,f_j\}$ has convex joint range (the case $m=2$ being already characterized); (ii) a nonhomogeneous analogue of the extended Yuan's lemma, characterizing when $\max_i f_i(x)\ge 0$ on a regular cone by existence of a suitable nonnegative matrix combination; and (iii) an extended S-lemma yielding strong duality for quadratic optimization subject to two bilateral nonhomogeneous quadratic constraints, extending the known single-constraint interval-bound case.

References

1. Song, Mengmeng; Xia, Yong. Polyak's convexity theorem, Yuan's lemma and S-lemma: extensions and applications. arXiv:2108.08517 (2021). https://arxiv.org/abs/2108.08517
2. Song, Mengmeng; Xia, Yong. Calabi-Polyak convexity theorem, Yuan's lemma and S-lemma: extensions and applications. Journal of Global Optimization 85(3):743-756 (2023; online 2022). DOI 10.1007/s10898-022-01225-0. https://doi.org/10.1007/s10898-022-01225-0
3. Haeser, Gabriel. An Extension of Yuan's Lemma and Its Applications in Optimization. Journal of Optimization Theory and Applications 174(3):641-649 (2017). DOI 10.1007/s10957-017-1123-2. https://doi.org/10.1007/s10957-017-1123-2
4. Baccari, Abdeljelil; Trad, Abdelhamid. On the Classical Necessary Second-Order Optimality Conditions in the Presence of Equality and Inequality Constraints. SIAM Journal on Optimization 15:394-408 (2004). DOI 10.1137/S105262340342122X. https://doi.org/10.1137/S105262340342122X
5. Anitescu, Mihai. Degenerate Nonlinear Programming with a Quadratic Growth Condition. SIAM Journal on Optimization 10:1116-1135 (2000). DOI 10.1137/S1052623499359178. https://doi.org/10.1137/S1052623499359178
6. Polyak, B. T. Convexity of Quadratic Transformations and Its Use in Control and Optimization. Journal of Optimization Theory and Applications 99:553-583 (1998). DOI 10.1023/A:1021798932766. https://doi.org/10.1023/A:1021798932766
7. Yuan, Y. On a subproblem of trust region algorithms for constrained optimization. Mathematical Programming 47:53-63 (1990). DOI 10.1007/BF01580852. https://doi.org/10.1007/BF01580852
8. Dines, Lloyd L. On the mapping of quadratic forms. Bulletin of the American Mathematical Society 47:494-498 (1941). DOI 10.1090/S0002-9904-1941-07494-X. https://doi.org/10.1090/S0002-9904-1941-07494-X
9. Pólik, Imre; Terlaky, Tamás. A Survey of the S-Lemma. SIAM Review 49:371-418 (2007). DOI 10.1137/S003614450444614X. https://doi.org/10.1137/S003614450444614X
10. Wang, Shu; Xia, Yong. Strong duality for generalized trust region subproblem: S-lemma with interval bounds. Optimization Letters 9:1063-1073 (2015). DOI 10.1007/s11590-014-0812-0. https://doi.org/10.1007/s11590-014-0812-0
11. Fischer, Andreas; Haeser, Gabriel; Silveira, Thiago P. On achieving strong necessary second-order properties in nonlinear programming. Pacific Journal of Optimization 20(4):683-697 (2024). DOI 10.61208/pjo-2024-002. https://doi.org/10.61208/pjo-2024-002
12. Behling, Roger; Haeser, Gabriel; Ramos, Alberto; Viana, Daiana S. On a Conjecture in Second-Order Optimality Conditions. Journal of Optimization Theory and Applications 176:625-633 (2018). DOI 10.1007/s10957-018-1229-1. https://doi.org/10.1007/s10957-018-1229-1
13. Flores-Bazán, Fabián; Opazo, Felipe. Joint-range convexity for a pair of inhomogeneous quadratic functions and applications to QP. arXiv:1508.01612 (2015). https://arxiv.org/abs/1508.01612
14. Flores-Bazán, Fabián; Opazo, Felipe. Characterizing Convexity of Images for Quadratic-Linear Mappings with Applications in Nonconvex Quadratic Optimization. SIAM Journal on Optimization 31(3):1774-1796 (2021). DOI 10.1137/19M1240484. https://doi.org/10.1137/19M1240484
15. Nguyen, Huu-Quang; Chu, Ya-Chi; Sheu, Ruey-Lin. On the convexity for the range set of two quadratic functions. Journal of Industrial and Management Optimization 18(1):575 (2022), DOI 10.3934/jimo.2020169; extended version arXiv:2503.01225 (2025). https://arxiv.org/abs/2503.01225
16. Yang, Meijia; Wang, Shu; Xia, Yong. Non-quadratic extension of homogeneous S-lemma and its applications in optimization. Journal of Industrial and Management Optimization 19(9):6826-6834 (2023). DOI 10.3934/jimo.2022241. https://doi.org/10.3934/jimo.2022241
17. Bednarczuk, Ewa M.; Bruccola, Giovanni. On global solvability of a class of possibly nonconvex QCQP problems in Hilbert spaces. Optimization 73:3537-3556 (online 2023). DOI 10.1080/02331934.2023.2281640. https://doi.org/10.1080/02331934.2023.2281640
18. Ai, Wenbao; Liang, Wei; Yuan, Jianhua. On the tightness of an SDP relaxation for homogeneous QCQP with three real or four complex homogeneous constraints. arXiv:2304.04174 (2023). https://arxiv.org/abs/2304.04174
19. Yang, Meijia; Xia, Yong. Global optimization of quadratic root-difference minimization under elliptic annulus constraints. arXiv:2605.29294 (2026). https://arxiv.org/abs/2605.29294