#  Arrangement of level sets of quadratic constraints and its relation to
nonconvex quadratic optimization problems

Huu-Quang Nguyen111Department of Mathematics, Vinh University, Nghe An,
Vietnam, email<EMAIL_ADDRESS>and Ruey-Lin Sheu222Department of
Mathematics, National Cheng Kung University, Tainan, Taiwan email:
<EMAIL_ADDRESS>
> Abstract We study a special class of non-convex quadratic programs subject
> to two (possibly indefinite) quadratic constraints when the level sets of
> the constraint functions are not arranged alternatively. It is shown in the
> paper that this class of problems admit strong duality following a tight SDP
> relaxation, without assuming primal or dual Slater conditions. Our results
> cover Ye and Zhang’s development in 2003 and the generalized trust region
> subproblems (GTRS) as special cases. Through the novel geometric view and
> some simple examples, we can explain why the problem becomes very hard when
> the level sets of the constraints are indeed arranged alternatively.
>
> Key words Non-convex quadratic programming, arrangement of constraint level
> sets, $\mathcal{S}$-procedure, Strong duality, SDP relaxation, GTRS, CDT
> problem.
>
> Mathematics Subject Classification (2010). 90C20, 90C22, 90C26.

##  1 Introduction

Consider the following quadratic program

$\begin{array}[]{ c l
}{\rm(P)}&\underset{x\in\mathbb{R}^{n}}{\min}\,\,f(x)=x^{T}Ax+2a^{T}x+a_{0},\\\
&\text{ s.t. }g(x)=x^{T}Bx+2b^{T}x+b_{0}\leq 0\\\ &\hskip
24.18501pth(x)=x^{T}Cx+2c^{T}x+c_{0}\leq 0\end{array}$ (1.1)

where $A,B,C$ are symmetric matrices in $\mathbb{R}^{n\times n};$
$a,b,c\in\mathbb{R}^{n},$ and $a_{0},b_{0},c_{0}\in\mathbb{R}.$ For
convenience, let the feasible domain be denoted by

$\mathcal{D}=\\{g\leq 0\\}\cap\\{h\leq 0\\}$

where, given an arbitrary function $\phi:\mathbb{R}^{n}\rightarrow\mathbb{R},$

$\\{\phi\star\gamma\\}=\\{x\in\mathbb{R}^{n}:\phi(x)\star\gamma\\},~{}~{}\mbox{
for }\star\in\\{<,\leq,=,\geq,>\\}.$

It is known that there are no general results for (P) but a few special cases
do have been studied in literature. They can be classified into several
categories based on the setup of the problem data.

  * •

[CDT] (The Celis-Dennis-Tapia subproblem)[4, 1984]: $B\succ 0$, $C\succeq 0.$

  * •

[HQPD] ((P) in Homogeneous Quadratic forms with a Positive Definite linear
combination) [12, 1998]: $a=b=c=0$ and $(\exists\lambda,\beta\in\mathbb{R})$
$\lambda B+\beta C\succ 0.$

  * •

[YZ] ((P) under conditions assumed in Ye and Zhang [19, 2003]): (i) the SDP
relaxation of (P), denoted by (SP), and its conic dual (SD) both satisfy the
Slater condition (see below for details); (ii) $g(x)$ and $h(x)$ do not have
any common root; (iii) $\\{h\geq 0\\}\subset\\{g\leq 0\\}.$

  * •

[GTRS] (The Generalized Trust Region Subproblem)[7, 1993][15, 1995][11, 2014]:
$B=-C,b=-c$ with the constraint set $\\{l\leq g(x)\leq u\\}.$

  * •

[QP1EQC] ((P) with a single quadratic equality constraint)[7, 1993][18, 2016]:
$h(x)=-g(x).$ (P) becomes $\min\\{f(x)|~{}g(x)=0\\}.$ Note that [QP1EQC]
$\subset$ [GTRS].

  * •

[QP1QC] ((P) with a single quadratic inequality constraint)[7, 1993][10,
2007][6, 2014]: $h(x)=-1.$ That is, (P) becomes $\min\\{f(x)|~{}g(x)\leq
0\\}.$

We will use those abbreviations in this paper.

All problems above can be solved in polynomial time. For [CDT], please refer
to Bienstock [2, 2016]; Sakaue et al. [14, 2016]; and Consolini and Locatelli
[5, 2017]. For [HQPD] and [YZ], please see Polyak [12, 1998] and Ye and Zhang
[19, 2003], respectively. For [GTRS] and [QP1EQC], they can be resolved by
$\mathcal{S}$-lemma with equality. See Wang and Xia [17, 2015] and Xia et al.
[18, 2016]. For [QP1QC], it can be solved with the classical
$\mathcal{S}$-lemma by P$\acute{{\rm o}}$lik and Terlaky [10, 2007] or using a
matrix pencil by Hsia et al. [6, 2014].

As far as strong duality is concerned, [HQPD], [YZ], [QP1QC] admit a tight SDP
reformulation under Slater’s condition [16, 2020]; [GTRS], [QP1EQC] requires
additionally that $\\{g=0\\}$ does not separate $\\{f<0\\}$ [18, 2016][9,
2018]; while [CDT] can do that when and only when the problem data setting
does not satisfy property $\mathcal{I}.$ See Ai and Zhang [1, 2009].

Our main results in this paper add to the above list a new polynomial-solvable
subclass in (P), named [Non-Alter], with strong duality.

  * •

[Non-Alter] ((P) under Assumptions 1 and 2 below):

Assumption 1: $\mathcal{D}\subset\\{g=0\\}\Rightarrow\mathcal{D}=\\{g=0\\}$
and $\mathcal{D}\subset\\{h=0\\}\Rightarrow\mathcal{D}=\\{h=0\\}$.

Assumption 2: Either $\\{g=0\\}\subset\\{h\leq 0\\}$ or
$\\{g=0\\}\subset\\{h\geq 0\\};$ and either $\\{h=0\\}\subset\\{g\leq 0\\}$ or
$\\{h=0\\}\subset\\{g\geq 0\\}.$ Immediately in Section 2, we will show that

$\Big{(}{\rm[YZ]}\cup{\rm[GTRS]}\cup{\rm[QP1EQC]}\cup{\rm[QP1QC]}\Big{)}\subset\hbox{[Non-
Alter]},$

but [CDT], [HQPD] may not. We choose particularly the abbreviation [Non-Alter]
to stand for “Non Alternative,” the geometric meaning of which will be clear
in Section 2. The whole idea comes from an earlier paper of us [9, 2018],
where we proved that, when a quadratic level set $\\{g=0\\}$ separates
disconnected components of another quadratic hypersurface $\\{h<0\\}$, the
S-lemma with equality [18, 2016] fails to hold.

Our major technique to establish strong duality for [Non-Alter] is to develop
a new $\mathcal{S}$-procedure involving three general quadratic functions
$(f,g,h).$ In Section 3, we first show that if $g,~{}h$ satisfy Assumptions 1
and 2 along with some constraint qualifications (which can be dealt separately
if fail), neither of the following two quadratic systems has a solution.

$\begin{cases}\begin{array}[]{l}g(x)>0,\\\ h(x)\geq
0;\end{array}\end{cases}\hbox{ and }\ \ \
\begin{cases}\begin{array}[]{l}g(x)\geq 0,\\\ h(x)>0.\end{array}\end{cases}$
(1.2)

Then, in Section 4, we show that, under Assumptions 1, 2 and the same
constraint qualifications for $(g,h)$, the following two statements are
equivalent for any quadratic function $f$ and any given $\gamma\in\mathbb{R}:$

  * (${\rm S_{1}}$) ($\forall x\in\mathbb{R}^{n}$) $~{}\big{(}g(x)\leq 0,~{}h(x)\leq 0\big{)}~{}\Longrightarrow~{}f(x)\geq\gamma.$

  * (${\rm S_{2}}$) $(\exists\lambda_{1}\geq 0,\lambda_{2}\geq 0)$ such that $f(x)-\gamma+\lambda_{1}g(x)+\lambda_{2}h(x)\geq 0,~{}\forall x\in\mathbb{R}^{n}.$

The new $\mathcal{S}$-procedure allows us to compute the optimal value of (P)
in the class [Non-Alter] through an SDP. We also provide a method to find an
optimal solution if (P) is attained.

##  2 What are contained in [Non-Alter] and what are not?

The class [Non-Alter] consists of (P) satisfying Assumptions 1 and 2.
Assumption 1 relaxes the Slater condition, which we discuss below.

$-$ Discussions about Assumption 1:

Unlike the Slater condition, Assumption 1 allows the feasible domain
$\mathcal{D}$ to have an empty interior. When it happens so, either
$\mathcal{D}\subset\\{g=0\\}$ or $\mathcal{D}\subset\\{h=0\\}$ or both,
$\mathcal{D}$ must be the entire $\\{g=0\\}$ and/or $\\{h=0\\},$ but cannot be
only part of the boundary.

Trivially, [QP1QC] satisfies Assumption 1 due to $\mathcal{D}=\\{g\leq 0\\}.$
In addition, [QP1EQC] also satisfies Assumption 1 since
$\mathcal{D}=\\{g=0\\}=\\{h=0\\}.$

On the other hand, [QP1QC] satisfies Assumption 2 since we express
particularly [QP1QC] with $h(x)=-1.$ Then, $\\{g=0\\}\subset\\{h\leq
0\\}=\mathbb{R}^{n}$ and $\\{h=0\\}=\emptyset\subset\\{g\leq 0\\}.$ [QP1EQC]
always satisfies Assumption 2 due to $h=-g.$

Therefore,

$\Big{(}{\rm[QP1QC]}\cup{\rm[QP1EQC]}\Big{)}\subset\hbox{[Non-Alter]}.$

The following example fails Assumption 1. Let $g(x,y,z)=x^{2}+y^{2}-1$ and
$h(x,y,z)=-x+1$ be defined on $\mathbb{R}^{3}.$ Then,
$\mathcal{D}=\\{(1,0,t):t\in\mathbb{R}\\}=\\{h=0\\}\subset\\{g=0\\}$ but
$\mathcal{D}\not=\\{g=0\\}.$ The example, however, can be solved easily. $-$
Discussions about Assumption 2:

Assumption 2 requires that the level set $\\{g=0\\}$ must lie, either entirely
in the sublevel set $\\{h\leq 0\\},$ or entirely in the superlevel set
$\\{h\geq 0\\}.$ Due to symmetry, it also assumes that either
$\\{h=0\\}\subset\\{g\leq 0\\}$ or $\\{h=0\\}\subset\\{g\geq 0\\}.$ Assumption
2 is closely related to a concept for separation between quadratic
hypersurfaces, introduced in [9, 2018] by the following definition:

######  Definition 2.1 ([9]).

The level set $\\{g=0\\}$ is said to separate the (sub-, super-) level set
$\\{h\star\,0\\}$ for $\star\in\\{<,\leq,=,\geq,>\\}$ if there are non-empty
subsets $L^{-}$ and $L^{+}$ of $\\{h\star\,0\\}$ such that
$\\{h\star\,0\\}=L^{-}\cup L^{+}$ and

$g(a^{-})g(a^{+})<0,~{}\forall~{}a^{-}\in L^{-};~{}\forall~{}a^{+}\in L^{+}.$

Let us choose $\star$ to be $=$ for Assumption 2. When
$\\{h=0\\}\subset\\{g\leq 0\\}$ or $\\{h=0\\}\subset\\{g\geq 0\\}$ happens,
$\\{g=0\\}$ cannot separate $\\{h=0\\}.$ Similarly, $\\{g=0\\}\subset\\{h\leq
0\\}$ or $\\{g=0\\}\subset\\{h\geq 0\\}$ implies that $\\{h=0\\}$ cannot
separate $\\{g=0\\}.$ Assumption 2 assumes a symmetry that $\\{g=0\\}$ and
$\\{h=0\\}$ cannot mutually separate each other.

What types of domain $\mathcal{D}$ satisfy Assumption 2? and what types not?

First, [GTRS] $\subset$ [Non-Alter]. By $l\leq g(x)\leq u,~{}u\geq l,$ we can
write

$g_{+}(x)=g(x)-u,~{}~{}g_{-}(x)=l-g(x).$

Then,

$g_{+}(x)=0~{}\Rightarrow~{}g(x)=u~{}\Rightarrow~{}g(x)\geq
l~{}\Rightarrow~{}g_{-}(x)\leq 0.$

Similarly, $g_{-}(x)=0~{}\Rightarrow~{}g_{+}(x)\leq 0.$ So, [GTRS] satisfies
Assumption 2. As for Assumption 1, if $l\not=u,$ it is automatically satisfied
since $\mathcal{D}=\\{l\leq g(x)\leq u\\}$ consists of an interior point. When
$l=u,$ [GTRS] is reduced to [QP1EQC] $\subset$ [Non-Alter].

On the other hand, [CDT] stands in the negative. Take $x\in\mathbb{R}^{2}$ as
an example. With $g(x)=\|x\|^{2}-1$ and $~{}h(x)=\|x-0.5\|^{2}-1,$ the circle
$\\{h=0\\}$ is divided into two parts. One part falls inside $\\{g\leq 0\\},$
while the other falling outside $\\{g>0\\}.$ Then,
$\\{h=0\\}\not\subset\\{g\leq 0\\},~{}\\{h=0\\}\not\subset\\{g\geq 0\\}.$
Assumption 2 does not hold.

Let us image the arrangement of the level sets for $\\{g=0\\}$ and $\\{h=0\\}$
in this case. It appears to be, from left to right in sequence, one piece of
$\\{g=0\\}$, one piece of $\\{h=0\\}$, one piece of $\\{g=0\\}$, and finally
one piece of $\\{h=0\\}$. We shall call, informally333We use the notion of
alternative arrangement of level sets in an informal way because it is
complicated to give a formal definition if at all possible. We only intend to
capture the important feature of geometry shared by many problems in [Non-
Alter] using 2D examples, though the true geometry of a general case could be
more sophisticated than that., the level sets of $\\{g=0\\}$ and $\\{h=0\\}$
are arranged alternatively. The class [Non-Alter] earns its name by that
reason. It excludes (P) having such an alternatively arranged level sets of
$\\{g=0\\}$ and $\\{h=0\\}.$ It now suggests that Problems (P) having its
feasible domain formed by alternatively arranged $\\{g=0\\}$ and $\\{h=0\\}$
is hard, in the sense of practical computation.

As we have mentioned in Introduction, [CDT] has been proved to be polynomially
solvable in computational complexity theory. However, unless the problem data
does not satisfy Property $\mathcal{I}$ [1, 2009] which implies a convex
reformulation for [CDT], there are still no algorithms reported that be able
to solve efficiently the type of [CDT] having a positive duality gap against
its Lagrange.

There is another reason explaining why (P) outside [Non-Alter] is hard. By the
following examples, one observes that, when the level sets of $(g,h)$ are
arranged alternatively, we are faced with finding a local non-global minimum
for [QP1EQC]. In general, identifying a feasible solution (or even a KKT
point) to be a local minimum could already be very difficult. See Murty and
Kabadi [8, 1987].

######  Example 2.2.

Let $g(x,y)=-x^{2}+y^{2}+9,h(x,y)=1-x.$ Then, the level set

$\\{g=0\\}=\\{g=0\\}^{-}\cup\\{g=0\\}^{+}$

consists of two branches of a hyperbola, $\\{g=0\\}^{-}$ and $\\{g=0\\}^{+}$,
as depicted below in blue. The level set $\\{h=0\\}$ is a vertical line in red
and it separate the two branches of $\\{g=0\\}$ as
$h(\\{g=0\\}^{-})h(\\{g=0\\}^{+})<0.$ Assumption 2 fails for this example.

We also observe the level sets $\\{g=0\\}$ and $\\{h=0\\}$ are arranged
alternatively: in blue-red-blue sequence (one $g$, one $h$, and $g$ again). We
consider it as a difficult case to solve if, upon the domain

$\mathcal{D}=\\{x\in\mathbb{R}^{2}|~{}-x^{2}+y^{2}+9\leq 0,~{}x\geq 1\\},$

the radius $r$ of a ball $f(x,y)=(x+2)^{2}+(y-8)^{2}\leq r^{2}$ is to be
minimized. The solution of (P): $\min\\{f(x):x\in\mathcal{D}\\}$ attains at
point $F$, which is a local non-global solution of (QP1EQC):
$\min\\{f(x):g(x)=0\\},$ whose global minimum point $E$ is infeasible to
$\mathcal{D}.$

$E$$F$$\\{g=0\\}^{+}$$\\{h=0\\}$$\\{g=0\\}^{-}$$\\{f=8.6\\}$$\\{f=19.5\\}$
Figure 1: Graphic representation for Example 2.2

######  Example 2.3.

Let $g(x,y)=-x^{2}+3y^{2}+1$ (blue) and $h(x,y)=x^{2}-3y^{2}-2x-y-1$ (red).
Both $\\{g=0\\}$ and $\\{h=0\\}$ have two branches:

$\\{g=0\\}=\\{g=0\\}^{-}\cup\\{g=0\\}^{+};~{}~{}\\{h=0\\}=\\{h=0\\}^{-}\cup\\{h=0\\}^{+}.$

We can see that they mutually separate each other:

$g(\\{h=0\\}^{-})g(\\{h=0\\}^{+})<0;~{}~{}h(\\{g=0\\}^{-})h(\\{g=0\\}^{+})<0.$

Thus, $\\{h=0\\}\not\subset\\{g\leq 0\\}$ and $\\{h=0\\}\not\subset\\{g\geq
0\\}.$ The example does not belong to [Non-Alter]. We observe that the level
sets of $\\{g=0\\}$ and $\\{h=0\\}$ (4 pieces in total) are arranged
alternatively: blue-red-blue-red.

$\\{g=0\\}^{+}$$\\{h=0\\}^{+}$$\\{h=0\\}^{-}$$\\{g=0\\}^{-}$ Figure 2: Graphic
representation for Example 2.3

######  Example 2.4.

Let $g(x,y)=-x^{2}+y^{2}+9$ (blue) and $h(x,y)=-(-x^{2}+y^{2}+49)$ (red).
Since $\\{g=0\\}\subset\\{h\leq 0\\}$ and $\\{h=0\\}\subset\\{g\leq 0\\},$
Assumption 2 holds. The level sets $\\{g=0\\},~{}\\{h=0\\}$ are arranged in
the manner: red-blue-blue-red, which is not alternative.

Consider $f_{1}(x,y)=(x+2)^{2}+(y-8)^{2}$, $f_{2}(x,y)=(x-14)^{2}+(y-4)^{2}$
as objective functions. The solution to $\min\\{f_{1}(x):x\in\mathcal{D}\\}$
is at $G$, whereas the solution to $\min\\{f_{2}(x):x\in\mathcal{D}\\}$ is at
$H$. The point $G$ is also the global minimum for $\min\\{f_{1}(x):g=0\\}$ and
the point $H$ is the global minimum for $\min\\{f_{1}(x):h=0\\}.$ This example
shows that [Non-Alter] can be solved in polynomial time as it reduces to
[QP1EQC].

$G$$H$$-7$$7$$-3$$3$$\\{g=0\\}^{+}$$\\{h=0\\}^{+}$$\\{g=0\\}^{-}$$\\{h=0\\}^{-}$$\\{f_{1}=23.04\\}$$\\{f_{2}=25.5\\}$
Figure 3: Graphic representation for Example 2.4

######  Example 2.5.

The following two problems belong to [Non-Alter]. Both Assumptions 1 and 2 are
satisfied and the level sets are not arranged alternatively. They can be
solved in polynomial time for any given quadratic objective function.

\- $g(x,y)=x^{2}+3y^{2}-16,~{}h(x,y)=-2x^{2}-y^{2}+4.$ (the left picture in
Figure 4)

\- $g(x,y)=-x^{2}+3y^{2}+4,~{}h(x,y)=y^{2}-x-2$ (the right picture in Figure
4)

$\\{g=0\\}$$\\{h=0\\}$

$\\{g=0\\}^{+}$$\\{h=0\\}$$\\{g=0\\}^{-}$

Figure 4: Graphic representation for Example 2.5

Finally in this section, we show that ${\rm[YZ]}\subset\hbox{[Non-Alter]}.$

For (P) to be in [YZ], it is required that (i) the SDP relaxation (SP) and its
conic dual (SD) both have a Slater point; (ii)
$\\{g=0\\}\cap\\{h=0\\}=\emptyset;$ and (iii) $\\{h\geq 0\\}\subset\\{g\leq
0\\}.$ We point out that (iii) implies parenthetically that

$\\{h\geq 0\\}\subset\\{g\leq
0\\}~{}\Rightarrow~{}\\{g>0\\}\subset\\{h<0\\}~{}\Rightarrow~{}\\{g\geq
0\\}\subset\\{h\leq 0\\}.$ (2.1)

By requiring (iii), it assumes both $\\{h\geq 0\\}\subset\\{g\leq 0\\}$ and
$\\{g\geq 0\\}\subset\\{h\leq 0\\},$ which shows that Assumption 2:
$\\{h=0\\}\subset\\{g\leq 0\\}$ and $\\{g=0\\}\subset\\{h\leq 0\\}$ is a
stronger version of (iii). Since [Non-Alter] does not assume the Slater
condition; does not restrict from a common root of $g$ and $h,$ it follows
that ${\rm[YZ]}\subset\hbox{[Non-Alter]}.$

The SDP relaxation (SP) and its conic dual (SD) in [YZ] have the following
formulations.

$\begin{array}[]{ c l }(\rm SP)\,\,\,\,\,\min&{M(f)\bullet X}\\\ {\text{
subject to }}&{M(g)\bullet X\leq 0,}\\\ {}\hfil&{M(h)\bullet X\leq 0,}\\\
{}\hfil&{X_{00}=1,X\succeq 0};\end{array}$ $\begin{array}[]{ c l }(\rm
SD)\,\,\,\,\,\max&{\gamma}\\\ {\text{ subject to
}}&{Z=M(f)-\gamma\begin{bmatrix}1&\bar{0}^{T}\\\
\bar{0}&[0]\end{bmatrix}+\alpha M(g)+\beta M(h),}\\\ {}\hfil&{Z\succeq
0,\alpha\geq 0,\beta\geq 0},\end{array}$

where $\bar{0}$ is zero vector in $\mathbb{R}^{n},$ $[0]$ is the zero matrix
in $\mathbb{R}^{n\times n}$, and

$M(f)=\begin{bmatrix}a_{0}&a^{T}\\\
a&A\end{bmatrix};\,M(g)=\begin{bmatrix}b_{0}&b^{T}\\\
b&B\end{bmatrix};\,M(h)=\begin{bmatrix}c_{0}&c^{T}\\\ c&C\end{bmatrix}$ (2.2)

For the rest of the paper, we prove that (SP) is tight for a larger subclass
[Non-Alter] of (P). In particular, the deletion of the dual Slater condition

$(\exists\tilde{\alpha}\geq 0,\tilde{\beta}\geq
0)~{}M(f)-\gamma\begin{bmatrix}1&\bar{0}^{T}\\\
\bar{0}&[0]\end{bmatrix}+\tilde{\alpha}M(g)+\tilde{\beta}M(h)\succ 0$ (2.3)

creates a notable technical gap to conquer. Without (2.3), we do not have a
“full-dimensional” dual to work with, and there is no easy way to returning
back to a full-dimensional case, either. As such, strong duality for the
nonconvex (P) becomes very tricky to establish. On the other hand, checking
(2.3) is another subtle issue. Although the strict feasibility of (2.3) with
two variables $\tilde{\alpha},~{}\tilde{\beta}$ can be determined in
polynomial time by computational complexity theory [13, 1997], practical
checkable algorithms seem to be unavailable so far.

The analysis in the following section is fundamental in its own right. It
concerns with the unsolvability of a system of two quadratic inequalities.

##  3 Unsolvability of (1.2)

This section gives a detail account of the conditions under which (1.2) has no
solution, which will be shown to be a hinge for strong duality of (P) in next
section.

The unsolvability of a single quadratic inequality, for example $f(x)<0$, has
a well-known result:

$f(x)<0$ has no solution if and only if $\begin{pmatrix}A&a\\\
a^{T}&a_{0}\end{pmatrix}\succeq 0.$

For two quadratic inequalities, the situation is very different. The type of
problem has not been studied much in literature. We first note that,

$\displaystyle\eqref{Unsolvable-system}\hbox{ is unsolvable }$
$\displaystyle\Longleftrightarrow$ $\displaystyle\Big{(}\\{h\geq
0\\}\subset\\{g\leq 0\\}\Big{)}\wedge\Big{(}\\{g\geq 0\\}\subset\\{h\leq
0\\})\Big{)}$ $\displaystyle\Longrightarrow$ $\displaystyle\hbox{ Assumption 2
}~{}~{}(\hbox{ see }\eqref{YZ3})$ (3.2)

The main result in this section, Theorem 3.1 below, concerns the reverse from
(3.2) to (3) under additional hypotheses.

######  Theorem 3.1.

Under Assumptions $1,~{}2,~{}3,~{}4$ and $5$, neither of the following two
quadratic systems has a solution $($the unsolvability of (1.2)$).$

$\begin{cases}\begin{array}[]{l}g(x)>0,\\\ h(x)\geq
0;\end{array}\end{cases}\hbox{ and }\ \ \
\begin{cases}\begin{array}[]{l}g(x)\geq 0,\\\ h(x)>0.\end{array}\end{cases}$

In other words, $\big{(}\\{g>0\\}\cap\\{h\geq 0\\}\big{)}\cup\big{(}\\{g\geq
0\\}\cap\\{h>0\\}\big{)}=\emptyset.$

Assumption 3: $f(x),g(x),h(x)$ are non-constant functions and

$\mathcal{D}=\\{x|g(x)\leq 0,h(x)\leq
0\\}\neq\emptyset;~{}\mathcal{D}\neq\\{g\leq 0\\};~{}\mathcal{D}\neq\\{h\leq
0\\}.$

Assumption 4: All the functions $g,h,-g,-h$ satisfy Slater’s condition.

Assumption 5: Suppose, after coordinate transformation, $g,~{}h$ degenerates
to single variable functions (in $x_{1}\in\mathbb{R}$) of the form
$-x_{1}^{2}+1$ and ${\bar{c}_{1}}x_{1}+{\bar{c}_{0}},~{}\bar{c}_{1}>0$ one for
each. Then, $\bar{c}_{0}\not=\pm\bar{c}_{1}.$

Assumption 3 is a prior condition to avoid triviality. Assumption 4 is a
regularity condition for the constraint functions $g,~{}h$ not to have a
degenerate gradient at the boundary. Assumption 5 excludes one peculiar
example: $g(x)=-x^{2}+1$ and $h(x)=x-1.$ It implies that
$\\{g=0\\}\subset\\{h\leq 0\\},$ $\\{h=0\\}\subset\\{g\leq 0\\}$ but
$\\{h=0\\}$ separates $\\{g<0\\}.$ Such a pathological case, satisfying
Assumption 2 as well as the two-sided Slater condition Assumption 4, fails
surprisingly the $\mathcal{S}$-lemma with equality [18, 2016][9, 2018].

The main tools to prove the un-solvability result, Theorem 3.1, are “the
separation theorem” and “the $\mathcal{S}$-lemma with equality” of Quang and
Sheu [9, 2018], which we take, respectively, as Lemma 3.2 and Lemma 3.3 below.
While the well-known separation theorem asserts the existence of a hyperplane
to separate two disjoint convex sets, our theorem in [9, 2018] may be thought
of as a nonlinear version of the classical separation theorem. It describes
when and how a hyper-surface $\\{h=0\\}$ can separate two convex connected
branches of $\\{g<0\\}.$ Moreover, when the separation happens, the
$\mathcal{S}$-lemma with equality fails.

######  Lemma 3.2.

(Quang and Sheu [9, 2018]) The hypersurface $\\{h=0\\}$ separates $\\{g<0\\}$
if and only if there exists a basis of $\mathbb{R}^{n}$ such that

  * $\rm(i)$

$g(x)$ is of the form
$-x_{1}^{2}+\delta(x_{2}^{2}+\cdots+x_{m}^{2})+\theta,~{}\delta,\theta\in\\{0,1\\};$

  * $\rm(ii)$

With the same basis and $\delta$ as in $\rm(i)$, $h(x)$ has the form

$\bar{c}_{1}x_{1}+\delta(\bar{c}_{2}x_{2}+\cdots+\bar{c}_{m}x_{m})+\bar{c}_{0},~{}\bar{c}_{1}\neq
0;$

  * $\rm(iii)$

$g|_{\\{h=0\\}}(x)=-(\delta\dfrac{\bar{c}_{2}}{\bar{c}_{1}}x_{2}+\cdots+\delta\dfrac{\bar{c}_{m}}{\bar{c}_{1}}x_{m}+\dfrac{\bar{c}_{0}}{\bar{c}_{1}})^{2}+\delta(x_{2}^{2}+\cdots+x_{m}^{2})+\theta\geq
0,~{}\forall(x_{2},\cdots,x_{n})^{T}\in\mathbb{R}^{n-1}.$

######  Lemma 3.3.

(Quang and Sheu [9, 2018]) If $h(x)$ takes both positive and negative values,
then $\\{h=0\\}$ fails to separate $\\{g<0\\}$ if and only if

$\big{(}h(x)=0~{}\Longrightarrow~{}g(x)\geq
0\big{)}\Longrightarrow(\exists\lambda\in\mathbb{R})(\forall
x\in\mathbb{R}^{n})~{}g(x)+\lambda h(x)\geq 0.$

Before proceeding to prove Theorem 3.1, two technical lemmas, Lemma 3.4 and
Lemma 3.5 will be shown in sequence to help.

######  Lemma 3.4.

Under Assumptions 4 and 5, if either $\\{g=0\\}\subset\\{h\leq 0\\}$ or
$\\{g=0\\}\subset\\{h\geq 0\\}$ holds true, $\\{h=0\\}$ separates neither
$\\{g<0\\}$ nor $\\{g>0\\}.$ Similarly, if either $\\{h=0\\}\subset\\{g\leq
0\\}$ or $\\{h=0\\}\subset\\{g\geq 0\\}$ holds true, $\\{g=0\\}$ separates
neither $\\{h<0\\}$ nor $\\{h>0\\}.$

###### Proof.

Suppose contrarily that $\\{h=0\\}$ separates $\\{g<0\\}$. We will show that
both $\\{g=0\\}\subset\\{h\leq 0\\}$ and $\\{g=0\\}\subset\\{h\geq 0\\}$ are
violated.

From Lemma 3.2, $g(x)$ is of the form

$-x_{1}^{2}+\delta(x_{2}^{2}+\cdots+x_{m}^{2})+\theta,~{}\delta,\theta\in\\{0,1\\}.$

We first consider the case when rank$(B)=1,$ and then when rank$(B)>1.$

When rank$(B)=1,$ there must be $\delta=0$ so that
$g(x)=-x_{1}^{2}+\theta,~{}\theta\in\\{0,1\\};~{}~{}h(x)=\bar{c}_{1}x_{1}+\bar{c}_{0},~{}{\bar{c}_{1}}>0.$
If $\theta=0,$ $g(x)\leq 0,~{}\forall x,$ which fails the Slater condition
Assumption 4. So, $g(x)=-x_{1}^{2}+1$ and

$\\{g=0\\}=\\{-1,1\\};~{}\\{g<0\\}=(-\infty,-1)\cup(1,\infty);~{}\\{g>0\\}=(-1,1);$
$\\{h=0\\}=-\frac{\bar{c}_{0}}{\bar{c}_{1}};~{}\\{h<0\\}=(-\infty,-\frac{\bar{c}_{0}}{\bar{c}_{1}});~{}~{}\\{h>0\\}=(-\frac{\bar{c}_{0}}{\bar{c}_{1}},\infty).$

Under Assumption 5, $-\frac{\bar{c}_{0}}{\bar{c}_{1}}\not=\pm 1.$

\- If $-\frac{\bar{c}_{0}}{\bar{c}_{1}}\in(-1,1),$ which contradicts to both
$\\{g=0\\}\subset\\{h\leq 0\\}$ and $\\{g=0\\}\subset\\{h\geq 0\\}.$

\- If $-\frac{\bar{c}_{0}}{\bar{c}_{1}}\in(-\infty,-1)\cup(1,\infty),$ then
$\\{h=0\\}$ cannot separate $\\{g<0\\}.$

In other words, rank$(B)=1$ is impossible under current circumstance.

Now, suppose rank$(B)>1.$ Consider, for any $t\in\mathbb{R},$

$x(t)=(\sqrt{t^{2}+\theta},-t,0,\cdots,0)\in\\{g=0\\};~{}y(t)=(-\sqrt{t^{2}+\theta},t,0,\cdots,0)\in\\{g=0\\}.$

Then, for any properly chosen $t_{0}$ such that
${\bar{c}_{1}}\sqrt{t_{0}^{2}+\theta}-\bar{c}_{2}t_{0}\neq 0,$ there is

$h(x(t_{0}))h(y(t_{0}))=-(\bar{c}_{1}\sqrt{t_{0}^{2}+\theta}-\bar{c}_{2}t_{0})^{2}<0,$

which fails both $\\{g=0\\}\subset\\{h\leq 0\\}$ and $\\{g=0\\}\subset\\{h\geq
0\\}$.

In summary, we have shown that $\\{h=0\\}$ cannot separate $\\{g<0\\}$ if
either $\\{g=0\\}\subset\\{h\leq 0\\}$ or $\\{g=0\\}\subset\\{h\geq 0\\}$
holds true. The other parts of the lemma can be similarly argued. $\Box$

In the next lemma, we use a variable transformation to make $g(x)$ adopt one
of the following five canonical forms (see Quang and Sheu [9, 2018]):

$\displaystyle-x_{1}^{2}-\cdots-
x_{k}^{2}+\delta(x_{k+1}^{2}+\cdots+x_{m}^{2})+\theta;$ (3.3) $\displaystyle-
x_{1}^{2}-\cdots-x_{k}^{2}+\delta(x_{k+1}^{2}+\cdots+x_{m}^{2})-1;$ (3.4)
$\displaystyle-x_{1}^{2}-\cdots-
x_{k}^{2}+\delta(x_{k+1}^{2}+\cdots+x_{m}^{2})+x_{m+1};$ (3.5)
$\displaystyle\hskip 8.0ptx_{1}^{2}+\cdots+x_{m}^{2}+\eta x_{m+1}+c^{\prime};$
(3.6) $\displaystyle\hskip 8.0pt\eta x_{1}+c^{\prime},$ (3.7)

where $\delta,\eta,\theta\in\\{0,1\\}.$

######  Lemma 3.5.

Assume that $\\{g=0\\}=\\{h=0\\}$ and Assumptions 3 and 4 hold true. Let
$g(\bar{x})>0,h(\bar{x})>0$ for some $\bar{x}\in\mathbb{R}^{n}.$ Then, there
exists a largest open ball
$\mathcal{B}(\bar{x},\bar{r})=\\{x:\|x-\bar{x}\|<\bar{r}\\}$ centered at
$\bar{x}$ with the radius $\bar{r}$ such that

$\mathcal{B}(\bar{x},\bar{r})\subset\\{g>0\\}\cap\\{h>0\\}\text{ and
}\overline{\mathcal{B}(\bar{x},\bar{r})}\cap\\{g=0\\}\neq\emptyset.$ (3.8)

Moreover, $\forall
x^{*}\in\overline{\mathcal{B}(\bar{x},\bar{r})}\cap\\{g=0\\},$

$\nabla g(x^{*})=t^{*}\overrightarrow{x^{*}\bar{x}}\neq 0\hbox{ and }~{}\nabla
h(x^{*})=s^{*}\overrightarrow{x^{*}\bar{x}}\neq 0,~{}~{}t^{*}>0,~{}s^{*}>0.$

###### Proof.

Since $g(\bar{x})>0$ and $h(\bar{x})>0$, it follows that
$\\{g>0\\}\cap\\{h>0\\}$ is a non-empty open set. Hence the set
$\mathcal{R}=\\{r\in\mathbb{R}_{+}:\mathcal{B}(\bar{x},{r})\subset\\{g>0\\}\cap\\{h>0\\}\\}$
is non-empty. Let $\bar{r}=\sup\\{r:r\in\mathcal{R}\\}.$ Then,
$\bar{r}<\infty$. Otherwise, $\bar{r}=\infty$ would imply that
$\mathcal{B}(\bar{x},{r})=\mathbb{R}^{n}$ and $\mathcal{D}=\emptyset,$ which
is a contradiction to Assumption 3. We therefore have shown that there exists
a largest open ball
$\mathcal{B}(\bar{x},\bar{r})=\\{x:\|x-\bar{x}\|<\bar{r}\\}$ centered at
$\bar{x}$ with the radius $\bar{r}$ such that
$\mathcal{B}(\bar{x},\bar{r})\subset\\{g>0\\}\cap\\{h>0\\}$.

It is clear that, if $x\in\left(\\{g>0\\}\cap\\{h>0\\}\right)^{c},$
$\|x-\bar{x}\|\geq\bar{r}.$ Therefore,

$\inf_{x\in\left(\\{g>0\\}\cap\\{h>0\\}\right)^{c}}\|x-\bar{x}\|\geq\bar{r}.$
(3.9)

On the other hand, since $\bar{r}$ is the largest radius such that
$\mathcal{B}(\bar{x},\bar{r})\subset\\{g>0\\}\cap\\{h>0\\}$,
$\forall\varepsilon>0,$ there is some
$x\in\left(\\{g>0\\}\cap\\{h>0\\}\right)^{c}$ such that
$\|x-\bar{x}\|<\bar{r}+\varepsilon.$ Then,

$\inf_{x\in\left(\\{g>0\\}\cap\\{h>0\\}\right)^{c}}\|x-\bar{x}\|\leq\bar{r}.$
(3.10)

Combining (3.9) and (3.10), one has

$\bar{r}^{2}=\inf_{x\in\left(\\{g>0\\}\cap\\{h>0\\}\right)^{c}}\|x-\bar{x}\|^{2}=\min\left\\{\inf_{\\{g\leq
0\\}}\|x-\bar{x}\|^{2},\inf_{\\{h\leq 0\\}}\|x-\bar{x}\|^{2}\right\\}.$ (3.11)

Suppose, without loss of generality, in (3.11) there is
$\bar{r}^{2}=\inf_{\\{g\leq 0\\}}\|x-\bar{x}\|^{2}.$ Since the distance from a
point to a closed set is always attainable, there is an $\hat{x}\in\\{g\leq
0\\}$ such that

$\|\hat{x}-\bar{x}\|^{2}=\bar{r}^{2},~{}i.e.,~{}\hat{x}\in\overline{\mathcal{B}(\bar{x},\bar{r})}.$

Moreover, $\hat{x}$ cannot be an interior point of $\\{g\leq 0\\},$ for
otherwise the distance from $\bar{x}$ to $\\{g\leq 0\\}$ would have been
shorter than $\bar{r}$ (since $\mathcal{B}(\bar{x},\bar{r})\subset\\{g>0\\}$).
This implies that $g(\bar{x})=0$ and thus

$\hat{x}\in\overline{\mathcal{B}(\bar{x},\bar{r})}\cap\\{g=0\\}\neq\emptyset.$

Now, $\forall x^{*}\in\overline{\mathcal{B}(\bar{x},\bar{r})}\cap\\{g=0\\}$,
since $x^{*}\not\in\\{g>0\\}\cap\\{h>0\\},$ $\|x^{*}-\bar{x}\|\geq\bar{r}$. By
$x^{*}\in\overline{\mathcal{B}(\bar{x},\bar{r})}$,
$\|x^{*}-\bar{x}\|\leq\bar{r}$. Hence,

$\|x^{*}-\bar{x}\|^{2}=\bar{r}^{2}=\inf_{\\{g=0\\}}\|x-\bar{x}\|^{2}.$ (3.12)

Due to the assumption $\\{g=0\\}=\\{h=0\\}$, (3.12) applies likewise to
$\\{h=0\\}.$

Next, we claim that $\nabla g(x^{*})\neq 0$ and $\nabla h(x^{*})\neq 0.$

Suppose contrarily that there is some
$x^{*}\in\overline{\mathcal{B}(\bar{x},\bar{r})}\cap\\{g=0\\}$ such that
$\nabla g(x^{*})=0.$ Then, with a suitable change of variables, $g(x)$ can
only be of the canonical form (3.3); or (3.4); or (3.6) with $\eta=0$. That
is,

$g(x)=\bar{\delta}(-x_{1}^{2}-\cdots-
x_{k}^{2})+\delta(x_{k+1}^{2}+\cdots+x_{m}^{2})+\theta,$

where $\bar{\delta},{\delta}\in\\{0,1\\},\theta\in\mathbb{R}.$ Moreover, since
$\nabla g(x^{*})=0$, one has

$x^{*}=(x^{*}_{1},\cdots,x^{*}_{k},x^{*}_{k+1},\cdots,x^{*}_{m},\cdots,x^{*}_{n})^{T}\mbox{
where }\left\\{\begin{array}[]{ll}x^{*}_{1}=\cdots=x^{*}_{k}=0,~{}\mbox{ if
}\bar{\delta}=1;\\\ x^{*}_{k+1}=\cdots=x^{*}_{m}=0,~{}\mbox{ if
}{\delta}=1.\end{array}\right.$

Due to $g(x^{*})=0$, $\theta$ must be zero. Assumption 4 further implies that
$\bar{\delta}$ and $\delta$ must be $1$ so that
$x^{*}=(0,\cdots,0,x^{*}_{m+1},\cdots,x^{*}_{n})^{T}$ and

$g(x)=(-x_{1}^{2}-\cdots-x_{k}^{2})+(x_{k+1}^{2}+\cdots+x_{m}^{2}).$

Now, let

$\bar{y}=(\bar{y}_{1},\cdots,\bar{y}_{m},\bar{y}_{m+1},\cdots,\bar{y}_{n})^{T}\mbox{
with }\left\\{\begin{array}[]{ll}\bar{y}_{i}=0,~{}\mbox{ for
}i\in\\{1,\cdots,m\\};\\\ \bar{y}_{i}=\bar{x}_{i},~{}\mbox{ for
}i\in\\{m+1,\cdots,n\\},\end{array}\right.$

where $\bar{x}_{i}$ is the coordinates of $\bar{x}$. Then
$\bar{y}\in\\{g=0\\}$ and
$\|\bar{y}-\bar{x}\|=\sqrt{\bar{x}_{1}^{2}+\cdots+\bar{x}_{m}^{2}}$. However,

$\|x^{*}-\bar{x}\|=\sqrt{\bar{x}_{1}^{2}+\cdots+\bar{x}_{m}^{2}+\sum_{i=m+1}^{n}(x^{*}_{i}-\bar{x}_{i})^{2}}\geq\|\bar{y}-\bar{x}\|,$

which together with (3.12) implies that $x^{*}_{i}=\bar{x}_{i}$ for all
$i\in\\{m+1,\cdots,n\\}$. In other words,

$x^{*}=(0,\cdots,0,\bar{x}_{m+1},\cdots,\bar{x}_{n})^{T}.$ (3.13)

By $g(\bar{x})>0$, there exists some $j\in\\{k+1,\cdots,m\\}$ such that
$\bar{x}_{j}\neq 0.$ Without loss of generality, let $j=m$ and

$\bar{x}_{m}\neq 0.$ (3.14)

Consider

$\hat{x}=(\hat{x}_{1},\cdots,\hat{x}_{m},\hat{x}_{m+1},\cdots,\hat{x}_{n})^{T}\mbox{
with
}\left\\{\begin{array}[]{ll}\hat{x}_{i}=\dfrac{\bar{x}_{1}+\bar{x}_{m}}{2},~{}\mbox{
for }i=1,m;\\\ \hat{x}_{i}=0,~{}\mbox{ for }i\in\\{2,\cdots,m-1\\};\\\
\hat{x}_{i}={\bar{x}}_{i},~{}\mbox{ for
}i\in\\{m+1,\cdots,n\\}.\end{array}\right.$

It is easy to see that $\hat{x}\in\\{g=0\\}$ and

$\|\bar{x}-\hat{x}\|=\sqrt{\big{(}\dfrac{\bar{x}_{1}-\bar{x}_{m}}{2}\big{)}^{2}+\big{(}\dfrac{\bar{x}_{m}-\bar{x}_{1}}{2}\big{)}^{2}+\sum_{i=2}^{m-1}\bar{x}_{i}^{2}}.$

On the other hand,

$\|\bar{x}-x^{*}\|=\sqrt{\bar{x}_{1}^{2}+\bar{x}_{m}^{2}+\sum_{i=2}^{m-1}\bar{x}_{i}^{2}}.$

Obviously, $\|\bar{x}-x^{*}\|\geq\|\bar{x}-\hat{x}\|$ and
$\|\bar{x}-x^{*}\|=\|\bar{x}-\hat{x}\|$ if and only if
$\bar{x}_{1}=-\bar{x}_{m}$.

  * •

If $\bar{x}_{1}\neq-\bar{x}_{m},$ then
$\|\bar{x}-x^{*}\|>\|\bar{x}-\hat{x}\|$, contradicting to (3.12).

  * •

Otherwise, $\bar{x}_{1}=-\bar{x}_{m}.$ In this case, choose

$\check{x}=(\check{x}_{1},\cdots,\check{x}_{m},\check{x}_{m+1},\cdots,\check{x}_{n})^{T}\mbox{
with
}\left\\{\begin{array}[]{ll}\check{x}_{1}=-\check{x}_{m}=\dfrac{\bar{x}_{1}-\bar{x}_{m}}{2};\\\
\check{x}_{i}=0,~{}\mbox{ for }i\in\\{2,\cdots,m-1\\};\\\
\check{x}_{i}={\bar{x}}_{i},~{}\mbox{ for
}i\in\\{m+1,\cdots,n\\}.\end{array}\right.$

Then, $\check{x}\in\\{g=0\\}$ and

$\displaystyle\|\bar{x}-\check{x}\|$ $\displaystyle=$
$\displaystyle\sqrt{\big{(}\dfrac{\bar{x}_{1}+\bar{x}_{m}}{2}\big{)}^{2}+\big{(}\dfrac{\bar{x}_{m}+\bar{x}_{1}}{2}\big{)}^{2}+\sum_{i=2}^{m-1}\bar{x}_{i}^{2}}$
(3.15) $\displaystyle=$ $\displaystyle\sqrt{\sum_{i=2}^{m-1}\bar{x}_{i}^{2}}$
$\displaystyle<$
$\displaystyle\sqrt{\bar{x}_{1}^{2}+\bar{x}_{m}^{2}+\sum_{i=2}^{m-1}\bar{x}_{i}^{2}}=\|\bar{x}-x^{*}\|,$

where the inequality (3.15) follows from (3.14). So we have proved that
$\|\bar{x}-\check{x}\|<\|\bar{x}-x^{*}\|$, which again contradicts to (3.12)
since $\check{x}\in\\{g=0\\}$.

In summary, we have proved that $\nabla g(x^{*})\not=0,$ which indicates that

$x^{*}\in\arg\min\\{\|x-\bar{x}\|^{2}:g(x)=0\\}$

is a regular point of $g(x)=0.$ By the KKT condition, there exists a
$\rho\in\mathbb{R}$ such that

$2(x^{*}-\bar{x})+\rho\nabla g(x^{*})=0.$

Since $x^{*}\neq\bar{x},$ $\rho\not=0.$ Then, $\nabla
g(x^{*})=t^{*}\overrightarrow{x^{*}\bar{x}}$ with $t^{*}=\frac{2}{\rho}.$
Since $g(x^{*})=0$ and $~{}g(\bar{x})>0,$ there must be
$t^{*}=\frac{2}{\rho}>0.$ By a similar argument, we can show the same for
$\nabla h(x^{*}).$ The proof is thus complete. $\Box$

Proof for Theorem 3.1: the unsolvability of (1.2) under Assumptions 1 - 5.

###### Proof.

According to Assumption 2, the following two cases must both happen.

  * ($\sharp$)

either $\\{g=0\\}\subset\\{h\leq 0\\}$ or $\\{g=0\\}\subset\\{h\geq 0\\},$ in
which case, by Lemma 3.4, $\\{h=0\\}$ separates neither $\\{g<0\\}$ nor
$\\{g>0\\}.$

  * ($\flat$)

either $\\{h=0\\}\subset\\{g\leq 0\\}$ or $\\{h=0\\}\subset\\{g\geq 0\\},$ in
which case, by Lemma 3.4, $\\{g=0\\}$ separates neither $\\{h<0\\}$ nor
$\\{h>0\\}.$

In ($\flat$), when $\\{h=0\\}\subset\\{g\geq 0\\}$ happens, either case in
($\sharp$) implies that $\\{h=0\\}$ cannot separate $\\{g<0\\}.$ By Lemma 3.3,
there is a $\lambda_{1}\in\mathbb{R}$ such that

$g(x)+\lambda_{1}h(x)\geq 0.$ (3.16)

Analogously, when $\\{h=0\\}\subset\\{-g\geq 0\\}$ happens in ($\flat$),
($\sharp$) implies that $\\{h=0\\}$ cannot separate $\\{-g<0\\}.$ By Lemma 3.3
again, there exists $\lambda_{2}\in\mathbb{R}$ such that

$-g(x)+\lambda_{2}h(x)\geq 0.$ (3.17)

Under the Slater condition (Assumption 4), we can further apply the classical
S-lemma to see that there are 4 possibilities:

\- (3.16) implies that

$\\{h\leq 0\\}\subset\\{g\geq 0\\}\hbox{ when }\lambda_{1}\geq 0;$ (3.18)

or

$\\{h\geq 0\\}\subset\\{g\geq 0\\}\hbox{ when }\lambda_{1}<0;$ (3.19)

\- (3.17) implies that

$\\{h\leq 0\\}\subset\\{g\leq 0\\}\hbox{ when }\lambda_{2}\geq 0;$ (3.20)

or

$\\{h\geq 0\\}\subset\\{g\leq 0\\}\hbox{ when }\lambda_{2}<0.$ (3.21)

Case 1: (3.20) cannot occur since it implies that $\mathcal{D}=\\{h\leq 0\\}$,
which contradicts to Assumption $3$.

Case 2: By the same argument, (3.19) cannot occur, either, since it implies
that $\\{g<0\\}\subset\\{h<0\\}$ so that $\\{g\leq 0\\}\subset\\{h\leq 0\\}$
and thus $\mathcal{D}=\\{g\leq 0\\}.$

Case 3: In case of (3.21), there is $\\{g>0\\}\subset\\{h<0\\}$. Then, the
system

$\begin{cases}\begin{array}[]{l}g(x)>0\\\ h(x)\geq 0\end{array}\end{cases}$

has no solution.

Case 4: In case of (3.18), we have

$\mathcal{D}=\\{h\leq 0\\}\cap\\{g\leq 0\\}\subset\\{g\geq 0\\}\cap\\{g\leq
0\\}=\\{g=0\\}.$

By Assumption 1, $\mathcal{D}=\\{g=0\\}.$ On the other hand, (3.18) also
implies that $\\{g\leq 0\\}\subset\\{h\geq 0\\}$. So $\mathcal{D}=\\{h\leq
0\\}\cap\\{g\leq 0\\}\subset\\{h\leq 0\\}\cap\\{h\geq 0\\}=\\{h=0\\}.$ By
Assumption 1, $\mathcal{D}=\\{h=0\\}.$ That is, when the case (3.18) happens,

$\mathcal{D}=\\{g=0\\}=\\{h=0\\}\not=\emptyset~{}~{}(\hbox{by Assumption 3}).$
(3.22)

Our goal is to prove that, under Case 4, the system of two quadratic
inequalities

$\begin{cases}\begin{array}[]{l}g(x)>0\\\ h(x)\geq 0\end{array}\end{cases}$

has no solution. Suppose on the contrary that this system has a solution
$\bar{x}$ such that $g(\bar{x})>0,h(\bar{x})\geq 0.$ Since $g(\bar{x})\not=0,$
by (3.22), $h(\bar{x})\not=0.$ Namely, one has

$g(\bar{x})>0,~{}h(\bar{x})>0.$

By Lemma 3.5, there exists a largest ball $\mathcal{B}(\bar{x},\bar{r}),$
centered at $\bar{x}$ with $\bar{r}<\infty$ such that

$\mathcal{B}(\bar{x},\bar{r})\subset\\{g>0\\}\cap\\{h>0\\}.$ (3.23)

and there exists some point $x^{*}\in\overline{\mathcal{B}(\bar{x},\bar{r})}$
such that

$g(x^{*})=h(x^{*})=0,\nabla g(x^{*})=t^{*}d\neq 0\text{ and }\nabla
h(x^{*})=s^{*}d\neq 0$

where $d=\overrightarrow{x^{*}\bar{x}}.$ Then, by Taylor’s expansion,

$\displaystyle g(x^{*}+\alpha\nabla g(x^{*}))$ $\displaystyle=$ $\displaystyle
g(x^{*})+\alpha\nabla g(x^{*})^{T}\nabla g(x^{*})+\alpha^{2}\big{(}\nabla
g(x^{*})^{T}B\nabla g(x^{*})\big{)}$ (3.24) $\displaystyle=$
$\displaystyle\alpha\|t^{*}d\|^{2}+\alpha^{2}(t^{*})^{2}\big{(}d^{T}Bd\big{)};$

and

$\displaystyle h(x^{*}+\beta\nabla h(x^{*}))$ $\displaystyle=$ $\displaystyle
h(x^{*})+\beta\nabla h(x^{*})^{T}\nabla h(x^{*})+\beta^{2}\big{(}\nabla
h(x^{*})^{T}C\nabla h(x^{*})\big{)}$ (3.25) $\displaystyle=$
$\displaystyle\beta\|s^{*}d\|^{2}+\beta^{2}(s^{*})^{2}\big{(}d^{T}Cd\big{)}.$

From (3.24) and (3.25), for all sufficiently small negative values of
$\alpha,\beta\in(\gamma,0),~{}\gamma<0,$ one has

$g(x^{*}+\alpha\nabla g(x^{*}))<0;~{}~{}h(x^{*}+\beta\nabla h(x^{*}))<0.$

Let us assume that $t^{*}<s^{*}$ and take
$\alpha=\frac{\gamma}{2},~{}\beta=\frac{\gamma
t^{*}}{2s^{*}},~{}\ddot{x}=x^{*}+\frac{\gamma t^{*}}{2}.$ Then,

$g(\ddot{x})<0,~{}~{}h(\ddot{x})<0,$

so that $\ddot{x}\in\mathcal{D}.$ However, it contradicts to (3.22) that
$\mathcal{D}=\\{g=0\\}=\\{h=0\\}.$

In summary, based on ($\flat$), we have shown that the system
$\\{g(x)>0,h(x)\geq 0\\}$ has no solution. The same analysis to base on
($\sharp$) will lead to the fact that the system $\\{g(x)\geq 0,h(x)>0\\}$
cannot have a solution, either. $\Box$

##  4 Solving $\rm(P)$ under Assumptions 1 and 2

Denote $\nu^{*}(\hbox{[Non-Alter]})$ to be the optimal value of a problem (P)
satisfying Assumptions 1 and 2. The key question in this section is to
investigate the feasibility problem:

Given any real number $\gamma\in\mathbb{R},$ can we check efficiently whether
the sublevel set of the objective function $\\{f<\gamma\\}$ is feasible or not
on the constraint set $\mathcal{D}?$ That is, determine whether or not
$\\{f<\gamma\\}\cap\mathcal{D}=\emptyset.$

The feasibility problem stated above links to the optimal value of a problem
in [Non-Alter] by

$\nu^{*}(\hbox{[Non-
Alter]})=\sup\\{\gamma:~{}\\{f<\gamma\\}\cap\mathcal{D}=\emptyset\\}.$

For an infeasible solution $x$ to $\mathcal{D},~{}x\not\in\mathcal{D},$ either
$g(x)>0,$ or $h(x)>0,$ or both happen. If, in addition, we have Assumptions 3
- 5, by the unsolvability Theorem 3.1, when $g(x)>0,$ $h(x)$ must be negative,
and vice verse. In other words,

$\\{f<\gamma\\}\cap\mathcal{D}=\emptyset\Longrightarrow\\{f<\gamma\\}\subset\big{(}\\{g<0\\}\cap\\{h>0\\}\big{)}\cup\big{(}\\{g>0\\}\cap\\{h<0\\}\big{)}.$
(4.1)

The following theorem shows that, in case of (4.1), $\\{f<\gamma\\}$ must lie,
either entirely in $\big{(}\\{g<0\\}\cap\\{h>0\\}\big{)}$, or entirely on the
other side $\big{(}\\{g>0\\}\cap\\{h<0\\}\big{)},$ except for a case when both
$g,~{}h$ are affine. More importantly, which side $\\{f<\gamma\\}$ would
reside has nothing to do with the choice of $\gamma.$ It is solely determined
by the characteristic of the objective function $f.$

######  Theorem 4.1.

Suppose that neither $g$ nor $h$ is affine and Assumptions $1,2,3,4$ and $5$
hold true. Let
$\Gamma=\big{\\{}\gamma\in\mathbb{R}:\\{f<\gamma\\}\cap\mathcal{D}=\emptyset\big{\\}}.$
Then,

$\displaystyle\text{either }\
(\forall\gamma\in\Gamma),~{}\\{f<\gamma\\}\subset\\{g<0\\}\cap\\{h>0\\};$
(4.2) $\displaystyle\text{ or }\
(\forall\gamma\in\Gamma),~{}\\{f<\gamma\\}\subset\\{g>0\\}\cap\\{h<0\\}.$
(4.3)

###### Proof.

Let $\gamma\in\Gamma.$ Since $f$ is quadratic, the sublevel set
$\\{f<\gamma\\}$ can have at most two connected components. For detailed
proof, please refer to Lemma 1 in Quang and Sheu [9, 2018]). We first observe
that each connected component $L$ of $\\{f<\gamma\\}$ must lie either entirely
in $\\{g<0\\}$ or entirely in $\\{g>0\\}$. Otherwise, by Intermediate value
theorem, there exists $x^{*}\in L\subset\\{f<\gamma\\}$ such that
$g(x^{*})=0.$ By Lemma 3.1, $\\{g\geq 0\\}\cap\\{h>0\\}=\emptyset,$ so that
$h(x^{*})\leq 0$ and thus $x^{*}\in\mathcal{D}.$ It is impossible as
$x^{*}\in\\{f<\gamma\\}\cap\mathcal{D}=\emptyset.$ From (4.1), we conclude
that if $L$ is a connected component of $\\{f<\gamma\\}$, either
$L\subset\big{(}\\{g<0\\}\cap\\{h>0\\}\big{)}$ or
$L\subset\big{(}\\{g>0\\}\cap\\{h<0\\}\big{)}.$

Now suppose that $\\{f<\gamma\\}$ consists of two connected components,
$L_{1}$ and $L_{2},$ such that

$L_{1}\subset\big{(}\\{g<0\\}\cap\\{h>0\\}\big{)}\hbox{ and
}L_{2}\subset\big{(}\\{g>0\\}\cap\\{h<0\\}\big{)}.$

Then, $g(L_{1})g(L_{2})<0$ and $h(L_{1})h(L_{2})<0,$ indicating that both
$\\{g=0\\}$ and $\\{h=0\\}$ separate $\\{f<\gamma\\}$. By [9, Theorem 1], both
$\\{g=0\\}$ and $\\{h=0\\}$ are affine functions, which contradicts to the
assumption of the theorem. So, we have proved that, $\forall\gamma\in\Gamma,$

$\text{either
}\,\\{f<\gamma\\}\subset\big{(}\\{g>0\\}\cap\\{h<0\\}\big{)};\text{ or
}\,\\{f<\gamma\\}\subset\big{(}\\{g<0\\}\cap\\{h>0\\}\big{)}.$ (4.4)

Finally, we have to show, if
$\emptyset\neq\\{f<\gamma^{*}\\}\subset\big{(}\\{g>0\\}\cap\\{h<0\\}\big{)}$
for some $\gamma^{*}\in\Gamma,$ then

$\\{f<\gamma\\}\subset(\\{g>0\\}\cap\\{h<0\\}),~{}~{}\forall\gamma\in\Gamma.$
(4.5)

\- It is obvious that $\\{f<\gamma\\}\subset\\{f<\gamma^{*}\\}$ if
$\gamma<\gamma^{*}.$ Therefore, (4.5) holds for all
$\gamma\in\Gamma,\gamma\leq\gamma^{*}$.

\- If $\gamma>\gamma^{*}$, then $\\{f<\gamma\\}\supset\\{f<\gamma^{*}\\}$.
Suppose contrarily that
$\\{f<\gamma\\}\subset\big{(}\\{g<0\\}\cap\\{h>0\\}\big{)}.$ It would imply
that $\\{f<\gamma^{*}\\}\subset(\\{g<0\\}\cap\\{h>0\\}),$ too. This
contradicts to
$\emptyset\neq\\{f<\gamma^{*}\\}\subset\big{(}\\{g>0\\}\cap\\{h<0\\}\big{)}$.
By (4.4), it follows that (4.5) holds for all
$\gamma\in\Gamma,\gamma>\gamma^{*}$. The proof is thus completed. $\Box$

With Theorem 4.1, we have the following $\mathcal{S}$-procedure for two
quadratic inequalities.

######  Theorem 4.2.

Suppose that Assumptions $1,2,3,4$ and $5$ hold and neither $g$ nor $h$ is
affine. The following two statements are equivalent for any given
$\gamma\in\mathbb{R}$.

${\rm(S_{1})}$ $(\forall x\in\mathbb{R}^{n})~{}\big{(}g(x)\leq 0,~{}h(x)\leq
0\big{)}~{}\Longrightarrow~{}f(x)\geq\gamma$.

${\rm(S_{2})}$ $(\exists\lambda_{1}\geq 0,\lambda_{2}\geq 0)$ such that
$f(x)-\gamma+\lambda_{1}g(x)+\lambda_{2}h(x)\geq 0,~{}~{}\forall
x\in\mathbb{R}^{n}.$

###### Proof.

It is trivial that ${\rm(S_{2})}$ implies ${\rm(S_{1})}$. We just need to
prove ${\rm(S_{1})}$ implies ${\rm(S_{2})}$. When we assume ${\rm(S_{1})}$, by
Theorem 4.1, one of (4.2) and (4.3) must occur.

\- In case of (4.2): $\\{f<\gamma\\}\subset\\{h>0\\}.$ Equivalently, $\\{h\leq
0\\}\subset\\{f-\gamma\geq 0\\}$. By S-lemma, there exists $\lambda\geq 0$
such that $f(x)-\gamma+\lambda h(x)\geq 0,\forall x\in\mathbb{R}^{n}.$ Choose
$\lambda_{1}=0,\lambda_{2}=\lambda$ for ${\rm(S_{2})}$ to follow.

\- In case of (4.3): the same argument as in (4.2) applies. $\Box$

######  Theorem 4.3.

Suppose that Assumptions $1,2$ hold true. Then, $\nu^{*}(\hbox{[Non-Alter]})$
can be computed in polynomial time.

###### Proof.

We divide the proof into the following cases:

$\odot$ If Assumption 3 is violated, then either $\mathcal{D}=\emptyset$ in
which case [Non-Alter] is infeasible; or $\mathcal{D}=\\{g\leq 0\\}$ or
$\mathcal{D}=\\{h\leq 0\\},$ in which case [Non-Alter] is reduced to [QP1QC].

$\odot$ Assumption 4 is the two-sided Slater condition, which is not essential
in proving strong duality of [Non-Alter]. Suppose $g(x)$ fails the Slater
condition. Then, $g(x)\geq 0,~{}\forall x\in\mathbb{R}^{n};$ $g(x)$ is convex,
and

$\\{g\leq 0\\}=\\{g=0\\}=\\{x\in\mathbb{R}^{n}|~{}Bx+b=0\\}$

is a hyperplane in $\mathbb{R}^{n}.$ In this case, $\mathcal{D}$ is the
intersection of $\\{h\leq 0\\}$ with a hyperplane, which reduces [Non-Alter]
to [QP1QC] over $\mathbb{R}^{n-1}.$ Similar arguments can be applied to
$-g,~{}h,~{}-h$ when any of them violates the Slater condition.

$\odot$ Assumption 5, once failed, means that
$g(x)=-x_{1}^{2}+1,~{}h(x)={\bar{c}_{1}}x_{1}+{\bar{c}_{0}},~{}\bar{c}_{1}>0,~{}\bar{c}_{0}=\pm\bar{c}_{1}\not=0$
after coordinate transformation.

\- If $\bar{c}_{0}=\bar{c}_{1},$
$\mathcal{D}=\\{x\in\mathbb{R}^{n}:~{}x_{1}\leq-1\\}.$ Then, [Non-Alter] is a
[QP1QC].

\- If $\bar{c}_{0}=-\bar{c}_{1},$
$\mathcal{D}=\\{x\in\mathbb{R}^{n}:~{}x_{1}\leq-1\\}\cup\\{x\in\mathbb{R}^{n}:~{}x_{1}=1\\}.$
In this case

$\nu^{*}(\hbox{[Non-
Alter]})=\min\big{\\{}\min\limits_{x_{1}\leq-1}f(x);\min\limits_{x_{1}=1}f(x)\big{\\}},$

which can be solved in polynomial time.

$\odot$ When both $g,~{}h$ are affine and satisfy Assumptions 1 and 2, we may
set $g(x)=2b^{T}x+b_{0},h(x)=2c^{T}x+c_{0}$. By Assumption 2, we have
$c=tb,t\neq 0$.

\- If $t>0,$ then $\mathcal{D}=\\{g\leq 0\\}$ or $\mathcal{D}=\\{h\leq 0\\}.$
[Non-Alter] becomes [QP1QC].

\- If $t<0,$ then $\mathcal{D}=\\{x:\frac{-c_{0}}{2t}\leq
b^{T}x\leq-\frac{b_{0}}{2}\\}=\\{x:(b^{T}x+\frac{c_{0}}{2t})(b^{T}x+\frac{b_{0}}{2})\leq
0\\}$ so that [Non-Alter] becomes [QP1QC] again.

$\odot$ Finally, we arrive the latest case when Assumptions 1 - 5 hold, and
neither $g$ nor $h$ is affine so that the $\mathcal{S}$-procedure Theorem 4.2
applies. Then (P) and its SDP relaxation has no gap. Indeed, with the standard
notation defined in (2.2), we have

$\displaystyle\nu^{*}(\hbox{[Non-Alter]})$ $\displaystyle=$
$\displaystyle\inf\left\\{f(x):~{}x\in\mathcal{D}\right\\}$ $\displaystyle=$
$\displaystyle\sup\left\\{\gamma:~{}\\{f<\gamma\\}\cap\mathcal{D}=\emptyset\right\\}~{}$
(4.7) $\displaystyle=$ $\displaystyle\sup_{(\lambda_{1},\lambda_{2})\geq
0}\left\\{\gamma:~{}f(x)-\gamma+\lambda_{1}g(x)+\lambda_{2}h(x)\geq 0,\forall
x\in\mathbb{R}^{n}\right\\}~{}$ (4.8) $\displaystyle=$
$\displaystyle\sup_{(\lambda_{1},\lambda_{2})\geq
0}\left\\{\gamma:Z=M(f)-\gamma\begin{bmatrix}1&\bar{0}^{T}\\\
\bar{0}&[0]\end{bmatrix}+\lambda_{1}M(g)+\lambda_{2}M(h),Z\succeq 0\right\\}$
(4.9) $\displaystyle\leq$ $\displaystyle\min\left\\{M(f)\bullet
X:~{}M(g)\bullet X\leq 0,M(h)\bullet X\leq 0,X_{00}=1,X\succeq 0\right\\}$
(4.10) $\displaystyle\leq$ $\displaystyle\min\left\\{M(f)\bullet
X:~{}M(g)\bullet X\leq 0,M(h)\bullet X\leq 0,X=\begin{bmatrix}1\\\
x\end{bmatrix}\begin{bmatrix}1\\\ x\end{bmatrix}^{T}\right\\}$ (4.11)
$\displaystyle=$ $\displaystyle\min\left\\{f(x):~{}g(x)\leq 0,h(x)\leq
0\right\\}$ $\displaystyle=$ $\displaystyle\nu^{*}(\hbox{[Non-Alter]}).$

Note that (4.7) is the statement ${\rm(S_{1})}$ in Theorem 4.2; (4.8) is the
statement ${\rm(S_{2})}$ in Theorem 4.2; (4.9) is the SDP reformulation of
(4.8); (4.10) follows from the conic weak duality; (4.11) follows from the
fact that

$X=\begin{bmatrix}1\\\ x\end{bmatrix}\begin{bmatrix}1\\\
x\end{bmatrix}^{T}\succeq 0\mbox{ with }X_{00}=1;$

and (4) follows from

$M(f)\bullet\begin{bmatrix}1\\\ x\end{bmatrix}\begin{bmatrix}1\\\
x\end{bmatrix}^{T}=\begin{bmatrix}1\\\
x\end{bmatrix}^{T}M(f)\begin{bmatrix}1\\\ x\end{bmatrix}=f(x).$

Therefore, the optimal value $\gamma^{*}$ of (P) can be solved by solving the
SPD (4.9). All the procedures discussed above are polynomial. The theorem is
thus proved. $\Box$

###  4.1 Finding an optimal solution for [Non-Alter]

As for the optimal solution of [Non-Alter], unlike [YZ] in which the primal-
dual Slater conditions were assumed so that the rank-one decomposition can be
applied for finding an optimal solution from the solution of the SDP
relaxation (SP), here we have to go via another approach.

In general, the objective function in [Non-Alter] can be unbounded from below
on the set of feasible solutions, or bounded from below but not attainable.
Here we aim to find an optimal solution $x^{*}$ for [Non-Alter] when the
optimal value $\nu^{*}(\hbox{[Non-Alter]})$ is finite and attainable.

We divide into two cases.

$\blacktriangleright$ $-\infty<\nu^{*}(\hbox{[Non-
Alter]})=\inf\\{f(x):x\in\mathbb{R}^{n}\\}$:

When the unconstrained minimization of $f$ over $\mathbb{R}^{n}$ happens to
equal $\nu^{*}(\hbox{[Non-Alter]}),$ the objective function $f$ must be
convex. An optimal solution $x^{*}$ to [Non-Alter] can be found by solving a
solution from the following system:

$\left\\{\begin{array}[]{ll}f(x)=\nu^{*}(\hbox{[Non-Alter]}),\\\ g(x)\leq
0,\\\ h(x)\leq 0.\end{array}\right.$ (4.13)

The first equation in (4.13) consists of all the minimizers of $f(x)$ on
$\mathbb{R}^{n}$ and this set is equivalent to

$\left\\{x:\min_{x\in\mathbb{R}^{n}}f(x)=\nu^{*}(\hbox{[Non-
Alter]})\right\\}=\left\\{-A^{+}a+Zy:y\in\mathbb{R}^{m}\right\\},$

where $A^{+}$ is the pseudo-inverse of $A$ and $Z\in\mathbb{R}^{n\times m}$ is
a matrix basis of $\mathcal{N}(A)$, assuming the null space of $A$ has rank
$m.$

The system (4.13) now reduces to finding an $y\in\mathbb{R}^{m}$ satisfying

$\left\\{\begin{array}[]{ll}\bar{g}(y)=g(-A^{+}a+Zy)\leq 0,\\\
\bar{h}(y)=h(-A^{+}a+Zy)\leq 0.\end{array}\right.$ (4.14)

in which both $\bar{g}(y),\bar{h}(y)$ are quadratic in $y.$ By solving the
following [QP1QC]

$\inf\\{\bar{g}(y):\bar{h}(y)\leq 0\\},$ (4.15)

we can get an optimal solution $y^{*}$ to (4.15). Then, $x^{*}=-A^{+}a+Zy^{*}$
is optimal to [Non-Alter].

$\blacktriangleright$ $\nu^{*}(\hbox{[Non-
Alter]})>\inf\\{f(x):x\in\mathbb{R}^{n}\\}=\gamma^{*}$:

We first notice that $\\{f<\nu^{*}(\hbox{[Non-Alter]})\\}\neq\emptyset$ and
$\\{f<\nu^{*}(\hbox{[Non-Alter]})\\}\cap\mathcal{D}=\emptyset.$ According to
Theorem 4.1, one of the following two cases

$\displaystyle\\{f<\nu^{*}(\hbox{[Non-
Alter]})\\}\subset\\{g<0\\}\cap\\{h>0\\},$ (4.16) $\displaystyle\text{ or
}~{}\\{f<\nu^{*}(\hbox{[Non-Alter]})\\}\subset\\{g>0\\}\cap\\{h<0\\}.$ (4.17)

occurs. This is easy to determine by taking a point
$x^{0}\in\\{f<\nu^{*}(\hbox{[Non-Alter]})\\}$ and checking the values of
$g(x)$ and $h(x)$ at $x^{0}$. Without loss of generality, let us assume
(4.16). Then,

$\\{f<\nu^{*}(\hbox{[Non-Alter]})\\}\cap\\{h\leq 0\\}=\emptyset.$

It implies that

$f(x^{*})=\nu^{*}(\hbox{[Non-Alter]})\leq\inf\\{f(x):~{}h(x)\leq 0\\}.$ (4.18)

Obviously, $\inf\\{f(x):~{}h(x)\leq 0\\}\leq\nu^{*}(\hbox{[Non-Alter]}),$
which, together with (4.18) gives

$f(x^{*})=\nu^{*}(\hbox{[Non-Alter]})=\inf\\{f(x):~{}h(x)\leq 0\\}.$ (4.19)

As $x^{*}\in\mathcal{D},$ $x^{*}$ is an optimal solution to
$\inf\\{f(x):~{}h(x)\leq 0\\}$ and $\inf\\{f(x):~{}h(x)\leq 0\\}$ is
attainable. Let us solve the [QP1QC] problem $\inf\\{f(x):~{}h(x)\leq 0\\}$
and assume the point $x_{h}$ to be the optimal solution obtained.

We claim that $h(x_{h})\not<0.$ Otherwise, $x_{h}$ is an interior point so
that

$f(x_{h})=\inf\\{f(x):~{}h(x)\leq 0\\}=\inf\\{f(x):x\in\mathbb{R}^{n}\\}.$
(4.20)

By (4.19) and (4.20)

$f(x_{h})=\nu^{*}(\hbox{[Non-Alter]})=\gamma^{*},$

which contradicts to the assumption at the beginning of this case. So,
$h(x_{h})=0.$ However, by the unsolvability Theorem 3.1, $g(x_{h})\not>0.$
There must be $g(x_{h})\leq 0.$ In other words, $x_{h}\in\mathcal{D}.$ The
point $x_{h}$ is optimal to [Non-Alter].

##  5 Final Discussions

Much of the quadratically constrained quadratic programming literature assumes
that both (SP) and (SD) satisfy the Slater condition and that $g(x)$ and
$h(x)$ do not share any common root. Our paper removes those obstacles by
exploring topological relations (non-alternativeness) between the (sup-/sub-)
level sets of $g$ and $h.$ We have shown that [Non-Alter] covers [QP1QC],
[QP1EQC], [GTRS], and [YZ], but not [CDT].

Our final comment goes to [HQPD]. It is easy to find an example in [HQPD]
fails Assumption 1. For example, let $f(x)=x_{1}^{2}-x_{2}^{2}$,
$g(x)=x_{1}^{2}+x_{2}^{2}-1,h(x)=-x_{1}^{2}+1$, then $A+2B\succ 0,2B+C\succ
0.$ This example belongs to [HQPD]. However, $\mathcal{D}=\\{g\leq
0\\}\cap\\{h\leq 0\\}=\\{(-1,0)^{T},(1,0)^{T}\\}\subset\\{g=0\\}$ but
$\mathcal{D}\neq\\{g=0\\}$ and $\mathcal{D}=\\{g\leq 0\\}\cap\\{h\leq
0\\}=\\{(-1,0)^{T},(1,0)^{T}\\}\subset\\{h=0\\}$ but
$\mathcal{D}\neq\\{h=0\\}$ so they do not satisfy Assumption 1. On the other
hand, $\\{h=0\\}\subset\\{g\geq 0\\}$ and $\\{g=0\\}\subset\\{h\geq 0\\}.$
Assumption 2 is satisfied by this example.

Now consider another example. Let
$f(x)=x_{1}^{2}+x_{2}^{2},~{}g(x)=2x_{1}^{2}+x_{2}^{2}-9,h(x)=x_{1}^{2}+2x_{2}^{2}-9$.
This example belongs to [HQPD] because $A,B,C\succ 0.$ It is easy to see that
$\mathcal{D}\neq\\{g=0\\}$, $\mathcal{D}\neq\\{h=0\\}$ so they satisfy
Assumption 1. However, $\\{g=0\\}\not\subset\\{h\leq 0\\}$,
$\\{g=0\\}\not\subset\\{h\geq 0\\}$, $\\{h=0\\}\not\subset\\{g\leq 0\\}$,
$\\{h=0\\}\not\subset\\{g\geq 0\\}$ so they do not satisfy Assumption 2.

Interestingly, with all $f,g,h$ in homogeneous forms having a pd pencil, we
could not find an example which fails both Assumption 1 and Assumption 2.
Polyak’s result [12, 1998] is a direct consequence of Brickman [3, 1961]. We
wish that we shall be able to extend their results for more general [HQPD] in
the future.

## Acknowledgements

Huu-Quang, Nguyen’s research work was sponsored partially by Taiwan Ministry
of Science and Technology grant number: MOST 108-2811-M-006-537
Ruey-Lin Sheu’s research work was sponsored partially by Taiwan Ministry of
Science and Technology grant number: MOST 107-2115-M-006-011-MY2.

## References

  * 1. Ai, W. and Zhang, S. (2009) Strong duality for the CDT subproblem: A necessary and sufficient condition. SIAM Journal on Optimization, 19, pp. 1735-1756.
  * 2. Bienstock, D. (2016) A note on polynomial solvability of the CDT problem. SIAM Journal on Optimization, 26, pp. 488-498.
  * 3. Brickman, L. (1961): On the field of values of a matrix. Proc. Amer. Math. Soc., 12, pp. 61-66.
  * 4. Celis, M.R., Dennis, J.E. and Tapia, R.A. (1984) A trust region algorithm for nonlinear equality constrained optimization in Numerical Optimization, Boggs R.T., Byrd R.H., and Schnabel R.B., eds., SIAM, Philadelphia, pp. 71-82.
  * 5. Consolini, L. and Locatelli, M. (2017) On the complexity of quadratic programming with two quadratic constraints. Mathematical Programming, 164, pp. 91-128.
  * 6. Hsia, Y., Lin, G.X. and Sheu, R.L. (2014) A revisit to quadratic programming with one inequality quadratic constraint via matrix pencil. Pacific Journal of Optimization, 10, pp. 461-481.
  * 7. Moré, J.J. (1993) Generalizations of the trust region problem. Optimization methods and Software, 2(3-4), pp. 189-209.
  * 8. Murty, K. G. and Kabadi, S. N. (1987) Some NP-complete problems in quadratic and nonlinear programming. Mathematical Programming, 39, pp. 117-129.
  * 9. Nguyen, H.Q., Sheu, R.L. (2018) Geometric properties for level sets of quadratic functions. Journal of Global Optimization, 73(2), pp. 349-369.
  * 10. Polik, I., Terlaky, T. (2007) _A survey of the S-lemma._ SIAM Review, 49(3), pp. 371-418.
  * 11. Pong, TK, Wolkowicz, H. (2014) The generalized trust region subprobelm. Computational Optimization and Applications, 58, pp. 273-322.
  * 12. Polyak, B. T. (1998) _Convexity of quadratic transformations and its use in control and optimization._ Journal of Optimization Theory and Applications, 99(3), pp. 553-583.
  * 13. Porkolab, L and Khachiyan, L. (1997) _On the complexity of semidefinite programs._ Journal of Global Optimization, 10(4), pp. 351-365.
  * 14. Sakaue, S. and Nakatsukasa, Y. and Takeda, A. and Iwata, S. (2016) Solving generalized CDT problems via two-parameter eigenvalues. SIAM Journal on Optimization, 26, pp. 1669-1694.
  * 15. Stern, R., Wolkowicz, H. (1995) Indefinite trust region subproblems and nonsymmetric eigenvalue perturbations. SIAM Journal on Optimization, 5(2), pp. 286-313.
  * 16. Xia, Y. (2020) A survey of hidden convex optimization. Journal of the Operations Research Society of China, 8(1), pp. 1-28.
  * 17. Wang, S., Xia, Y. (2015) Strong Duality for Generalized Trust Region Subproblem: S-Lemma with Interval Bounds. Optimization Letters, 9(6), pp. 1063-1073.
  * 18. Xia, Y., Wang, S., Sheu, R.L. (2016) _S-lemma with equality and its applications._ Mathematical Programming, 156(1), pp. 513-547.
  * 19. Ye, Y. and Zhang, S. (2003) New results on quadratic minimization. SIAM Journal on Optimization, 14, pp. 245-267.