∎

11institutetext:  J. Wang 22institutetext: M. Song 33institutetext: Y. Xia
44institutetext: LMIB of the Ministry of Education, School of Mathematical
Sciences, Beihang University, Beijing, 100191, P. R. China
44email<EMAIL_ADDRESS>(J. L. Wang<EMAIL_ADDRESS>(M. M.
Song<EMAIL_ADDRESS>(Y. Xia, corresponding author) )

# On local minimizers of generalized trust-region subproblem ††thanks: This
research was supported by the Beijing Natural Science Foundation, grant
Z180005 and by the National Natural Science Foundation of China under grants
12171021, and 11822103.

Jiulin Wang  Mengmeng Song  Yong Xia

(Received: date / Accepted: date)

###### Abstract

Generalized trust-region subproblem (GT) is a nonconvex quadratic optimization
with a single quadratic constraint. It reduces to the classical trust-region
subproblem (T) if the constraint set is a Euclidean ball. (GT) is polynomially
solvable based on its inherent hidden convexity. In this paper, we study local
minimizers of (GT). Unlike (T) with at most one local nonglobal minimizer, we
can prove that two-dimensional (GT) has at most two local nonglobal
minimizers, which are shown by example to be attainable. The main contribution
of this paper is to prove that, at any local nonglobal minimizer of (GT), not
only the strict complementarity condition holds, but also the standard second-
order sufficient optimality condition remains necessary. As a corollary,
finding all local nonglobal minimizers of (GT) or proving the nonexistence can
be done in polynomial time. Finally, for (GT) in complex domain, we prove that
there is no local nonglobal minimizer, which demonstrates that real-valued
optimization problem may be more difficult to solve than its complex version.

###### Keywords:

Quadratic optimization Generalized trust-region subproblem Local minimizer
Optimality condition Polynomial solvability

###### MSC:

90C20, 90C26, 90C30, 90C46

##  1 Introduction

Given two quadratic functions

$f(x)=x^{T}Ax+2a^{T}x,~{}g(x)=x^{T}Bx+2b^{T}x+c,$

where $A,B\in\mathbb{R}^{n\times n}$ are symmetric and possibly not positive
semidefinite, $a,b\in\mathbb{R}^{n}$ and $c\in\mathbb{R}$, we consider the
inequality and equality constrained versions of generalized trust-region
subproblem:

$\displaystyle{(\rm GT)}$ $\displaystyle\min\\{f(x):~{}g(x)\leq
0,~{}x\in\mathbb{R}^{n}\\},$ $\displaystyle{(\rm GT_{e})}$
$\displaystyle\min\\{f(x):~{}g(x)=0,~{}x\in\mathbb{R}^{n}\\}.$

The Euclidean-ball constrained (GT) $(B=I,b=0,c<0)$ is known as the classical
trust-region subproblem (T). Problem (T) plays a great role in each iteration
of the trust-region method C00 ; Y15  in nonlinear programming. It also has
applications in robust optimization HK18 , constrained linear regression and
tensor decomposition P20 . In the early 1980s, Gay G81 , Sorensen S82 , Moré
and Sorensen M83  established the necessary and sufficient optimality
condition for the global minimizer of (T) even it is nonconvex. Based on this
optimality condition, (T) is shown to be polynomially solvable in the early
1990s, see V90 ; Y92 . After that, many other polynomial-time algorithms were
proposed to globally solve (T), for example, see A17 ; G99 ; R97 . Recently,
first-order methods were proposed to globally solve large dimensional (T) B18
; H16 ; H17 ; W17 . These make sense due to the inherent hidden convexity of
(T), see the recent survey X20  and references therein.

In addition to the applications of its special case (T), (GT) (or $(\rm
GT_{e})$) not only frequently appears as a subproblem in some algorithm
schemes B09 ; HN16 ; WZ20 , but also has direct applications in constrained
least squares G80 , regularized total least squares B06 , GPS localization and
circle fitting problem B12 .

(GT) and $(\rm GT_{e})$ have attractive properties similar to (T). In 1993,
Moré M93  established the necessary and sufficient optimality condition for
the global minimizer of (GT). Under mild assumptions, (GT) and $(\rm GT_{e})$
admit strong duality thanks to the fundamental S-lemma PT07 ; Y71  and S-lemma
with equality X16 , respectively. Under assumptions such as primal and/or dual
Slater conditions, there are many polynomial-time algorithms A19 ; F12 ; M93 ;
P14 ; S95  and first-order methods J20 ; WK20  for globally solving (GT).
Among these assumptions, a notable assumption for (GT) is simultaneously
diagonalizable (SD) by congruence for matrices $A$ and $B$, see J16  and
references therein. We refer to B20 ; L15  for understanding hidden convexity
of (GT) under SD assumption. Efficient algorithms based on SD assumption can
be found in BH14 ; J19 ; J18 ; S18 . Beyond these regular assumptions, (GT)
may be either unbounded below or bounded below but the optimal value is
unattainable. Necessary and sufficient conditions were established for these
two irregular cases by Hsia et al. H14 .

Local nonglobal minimizers of (T) also have some nice properties. In 1994,
Martínez M94  surprisingly proved that (T) has at most one local nonglobal
minimizer. The proof is based on univariate reformulations of the standard
second-order necessary and sufficient optimality conditions for the local
nonglobal minimizer of (T). In 1998, the strict complementarity condition is
proved to hold at the local nonglobal minimizer of (T) LPR98 . In 2020, Wang
and Xia WX20  proved that, at local nonglobal minimizer of (T), the standard
second-order sufficient optimality condition is surprisingly necessary. This
theoretical observation implies that, by an improved version of generalized
eigenvalue-based algorithm A17 ; S17 , finding the local nonglobal minimizer
of (T) or proving the nonexistence can be done in polynomial time WX20 . Very
recently, Wang et al. W21  proved that the local nonglobal minimizer of (T),
if exists, has the second smallest objective function value among all KKT
points.

Local nonglobal minimizers of (GT) take an irreplaceable role in globally
solving the extended generalized trust-region subproblem TS20 :

$\min\left\\{f(x):~{}g(x)\leq 0,~{}h^{T}x\leq
d,~{}x\in\mathbb{R}^{n}\right\\},$

where $h\in\mathbb{R}^{n}$ and $d\in\mathbb{R}$. The unique global
optimization solution approach, dating back to H13 , is to enumerate
(candidates of) all local minimizers of (GT) satisfying $h^{T}x<d$ and the
global minimizer of the reduced version of (GT) in the hyperplane $h^{T}x=d$,
in the worst case that the linear constraint $h^{T}x\leq d$ cuts the optimal
solution set of (GT).

To our knowledge, there are few investigations on local nonglobal minimizers
of (GT) or $(\rm GT_{e})$. In 2020, Taati and Salahi TS20  extended Martínez’s
analysis M94  to (GT) and established only necessary optimality condition for
local nonglobal minimizers of (GT). In the same paper, they extended the
eigenvalue-based algorithm S17  to find candidates of local nonglobal
minimizers of (GT). Very recently, Song et al. S21  proved that there is no
local nonglobal minimizer for homogeneous (GT) (or $(\rm GT_{e})$). They also
analyzed local optimality conditions for homogeneous quadratic optimization
with two quadratic constraints under a strong assumption, which only covers a
special case of homogenized (GT) with a positive definite matrix $B$.
Comparing with (T), the following questions are unknown.

  * (1)

How many local nonglobal minimizers may (GT) (or $(\rm GT_{e})$) have?

  * (2)

Does the strict complementarity condition hold at any local nonglobal
minimizer of (GT)?

  * (3)

Is there a necessary and sufficient optimality condition for any local
nonglobal minimizer of (GT) (or $(\rm GT_{e})$)?

  * (4)

Can we find all local nonglobal minimizers of (GT) (or $(\rm GT_{e})$) in
polynomial time?

The goal of this paper is to (partially) answer the above four questions. We
overestimate the number of local nonglobal minimizers of (GT) (or $(\rm
GT_{e})$) and show that our bound is tight for two-dimensional case. We can
construct an instance of two-dimensional (GT) with two local nonglobal
minimizers. In contrast, we prove that the complex-valued (GT) in arbitrary
dimension has no local nonglobal minimizer. We provide positive answers to
Questions (2)-(4). More precisely, we prove that, at any local nonglobal
minimizer of (GT) (or $(\rm GT_{e})$), the standard second-order sufficient
optimality condition is necessary. As a corollary, finding all local nonglobal
minimizers of (GT) (or $(\rm GT_{e})$) or proving the nonexistence can be done
in polynomial time.

The remainder of the paper is organized as follows. Section 2 presents
assumptions made on (GT) and $(\rm GT_{e})$ and existing characterizations of
local and global minimizers. Section 3 proves not only the strict
complementarity condition, but also second-order necessary and sufficient
optimality condition. The complexity of finding all local nonglobal minimizers
of (GT) (or $(\rm GT_{e})$) is presented. Section 4 overestimates the number
of local nonglobal minimizers of (GT) and $(\rm GT_{e})$, presents an example
with more than one local nonglobal minimizers, and proves that (GT) (or $\rm
GT_{e}$) in complex domain has no local nonglobal minimizer. Conclusions are
made in Section 5.

Notations. Let $\mathbb{R}^{n}$ and $\mathbb{C}^{n}$ be the $n$-dimensional
real and complex spaces, respectively. The real and imaginary part of scalars,
vectors, and matrices are denoted by $\Re(\cdot)$ and $\Im(\cdot)$,
respectively. Denote by $\mathbb{R}^{n\times n}$ ($\mathbb{C}^{n\times n}$)
the set of real (complex) square matrices of order $n$. $0$ represents a zero
number, an all-zero vector, or an all-zero matrix. For a symmetric matrix $A$,
$A\succ(\succeq)0$ denotes that $A$ is positive (semi)definite.
Diag$(a_{1},\ldots,a_{n})$ returns a diagonal matrix with diagonal components
$a_{1},\cdots,a_{n}$. Denote by $[a_{1};a_{2}]$ the column vector composed of
vectors $a_{1}$ and $a_{2}$. For a real number $a$, $|a|$ represents its
absolute value. For any smooth vector-valued function
$h:\mathbb{R}\rightarrow\mathbb{R}^{m}$ ($m\geq 1$), $h^{\prime}$,
$h^{\prime\prime}$ and $h^{\prime\prime\prime}$ denote the first, second and
third derivatives of $h$, respectively.

##  2 Preliminaries

We present in this section some basic assumptions and existing global and
local optimality conditions for $\rm(GT)$ and $\rm(GT_{e})$.

###  2.1 Assumptions

We assume that $g(x)$ is nonlinear, since otherwise, (GT) (or $\rm(GT_{e})$)
reduces to a quadratic programming problem, which has no local nonglobal
minimizer. Moreover, through a suitable linear transformation if necessary, we
can make the following assumption to simplify $g(x)$.

###### Assumption 1

$\displaystyle B=\left[{\begin{array}[]{*{20}{c}}B_{1}&\\\
&0\end{array}}\right],~{}b=\left[{\begin{array}[]{*{20}{c}}0\\\
b_{2}\end{array}}\right],~{}c\in\\{-1,1,0\\},~{}B_{1}\in\mathbb{R}^{n_{1}\times
n_{1}},~{}b_{2}\in\mathbb{R}^{n_{2}},$ (2.5)

where $B_{1}$ is symmetric and nonsingular, $n_{1}$ and $n_{2}$ are
nonnegative integers satisfying $n_{1}\geq 1$ (so that $g(x)$ is nonlinear)
and $n_{1}+n_{2}=n$.

The primal Slater conditions for (GT) and $\rm(GT_{e})$ are presented as
follows.

###### Assumption 2

The primal Slater condition holds for $(\rm GT)$, i.e., there exists
$\hat{x}\in\mathbb{R}^{n}$ such that $g(\hat{x})<0$.

###### Assumption 3

The primal Slater condition holds for $(\rm GT_{e})$, i.e., there exist
$\hat{x},\bar{x}\in\mathbb{R}^{n}$ such that $g(\hat{x})<0<g(\bar{x})$.

It follows from Assumptions 2 and 3 that the feasible regions of (GT) and
${(\rm GT_{e})}$ are both nonempty. Moreover, if Assumption 2 is violated,
then there is no local nonglobal minimizer for (GT) (see TS20 , Proposition
2.3). If Assumption 3 does not hold, according to (M93, , Lemma 3.1), the
feasible region of ${(\rm GT_{e})}$ is either a linear manifold or a single
point. Therefore, ${(\rm GT_{e})}$ has no local nonglobal minimizer.

In global optimization of (GT) and ${(\rm GT_{e})}$, the following standard
dual Slater conditions are often used, respectively, see for example, A19 ;
J19 ; M93 .

###### Assumption 4

There exists $\hat{\lambda}\geq 0$ such that $A+\hat{\lambda}B\succ 0$.

###### Assumption 5

There exists $\hat{\lambda}\in\mathbb{R}$ such that $A+\hat{\lambda}B\succ 0$.

Assumption 5 is slightly weaker than Assumption 4. It was proved in M93  that
under Assumption 5 (or 4), (GT) (or ${(\rm GT_{e})}$) has a global minimizer.
For the necessary and sufficient condition on the existence of the global
minimizer of (GT) (or ${(\rm GT_{e})}$), we refer to H14 .

In local optimality analysis of (GT), Taati and Salahi TS20  made Assumptions
1, 2 and 5. In particular, if Assumption 5 holds but Assumption 4 fails, Taati
and Salahi presented a lower unbounded example with one local nonglobal
minimizer, see (TS20, , Example 1).

Our local optimality analysis in this paper is based on the following further
relaxed assumption, which was first introduced for (GT) in F12 .

###### Assumption 6

There exist $\mu_{1},\mu_{2}\in\mathbb{R}$ such that $\mu_{1}A+\mu_{2}B\succ
0$.

Actually, Assumption 6 is a well-known sufficient condition for simultaneous
diagonalization (via congruence) of $A$ and $B$.

If Assumption 6 is satisfied but Assumption 5 fails, (GT) may still have a
local nonglobal minimizer even if it is unbounded below.

###### Example 2.1

Consider the following three-dimensional case of $\rm(GT)$:

$\min\\{x_{1}^{2}+2x_{2}^{2}-x_{3}^{2}+2x_{1}-2x_{3}:~{}x_{1}^{2}-x_{2}^{2}+2x_{1}+2x_{3}+1\leq
0,~{}x\in{\mathbb{R}}^{3}\\}.$

We can check the lower unboundedness of this instance. We can further verify
that $x^{*}=[-1,0,0]^{T}$ is a local nonglobal minimizer of $\rm(GT)$ with the
corresponding Lagrangian multiplier $\lambda^{*}=1$.

###  2.2 Optimality conditions

The necessary and sufficient optimality conditions for global minimizers of
$\rm(GT)$ and $\rm(GT_{e})$ are due to Moré M93 .

######  Theorem 2.1 (M93 , Theorem 3.2)

Under Assumptions 1 and 3, $x^{*}$ is a global minimizer of $\rm(GT_{e})$, if
and only if $g(x^{*})=0$ and there exists $\lambda^{*}\in\mathbb{R}$ such that

$\displaystyle(A+\lambda^{*}B)x^{*}+a+\lambda^{*}b=0,$ (2.6) $\displaystyle
A+\lambda^{*}B\succeq 0.$ (2.7)

######  Theorem 2.2 (M93 , Theorem 3.4)

Under Assumptions 1 and 2, $x^{*}$ is a global minimizer of $\rm(GT)$, if and
only if $g(x^{*})\leq 0$, and (2.6)-(2.7) are satisfied for some
$\lambda^{*}\geq 0$ with $\lambda^{*}=0$ if $g(x^{*})<0$.

In order to study local minimizers of $\rm(GT)$, we first show that the
inequality constraint is always active at any local nonglobal minimizer of
$\rm(GT)$.

###### Lemma 2.1

Let $x^{*}$ be a local nonglobal minimizer of $\rm(GT)$. Then $g(x^{*})=0$.

###### Proof

Suppose, on the contrary, $g(x^{*})<0$. The assumptions on $x^{*}$ imply that
it is a local minimizer of the unconstrained optimization $\min f(x)$. We have

$\nabla f(x^{*})=0,~{}\nabla^{2}f(x^{*})\succeq 0.$

As $f(x)$ is a quadratic function, $x^{*}$ is a global minimizer of $\min
f(x)$. Therefore, $x^{*}$ is a global minimizer of $\rm(GT)$, which
contradicts the assumption on $x^{*}$.

Local optimality conditions require some regular assumptions such as the
linear independence constraint qualification (LICQ). Taati and Salahi (TS20, ,
Lemma 2.5) proved that LICQ always holds at any local nonglobal minimizer of
$\rm(GT)$. We extend this result to $\rm(GT_{e})$. Our proof is new and
elegant.

###### Theorem 2.3

Under Assumptions 1 and 2 (or 3), if $x^{*}$ is a local nonglobal minimizer of
$\rm(GT)$ (or $\rm(GT_{e})$), then LICQ holds at $x^{*}$.

###### Proof

Suppose on the contrary that LICQ fails at $x^{*}$, that is,

$\displaystyle\nabla g(x^{*})=2(Bx^{*}+b)=0.$ (2.8)

By Lemma 2.1, $g(x^{*})=0$ even for (GT). Then, it holds that

$g(x^{*}+d)=g(x^{*})+\nabla g(x^{*})^{T}d+d^{T}Bd=d^{T}Bd,~{}\forall
d\in\mathbb{R}^{n}.$

Therefore, for any $d\in\mathbb{R}^{n}$ satisfying $d^{T}Bd\leq 0(=0)$,
$x^{*}+d$ is feasible to $\rm(GT)$ (or $\rm(GT_{e})$). Define

$h(t)=f(x^{*}+td)=f(x^{*})+2(Ax^{*}+a)^{T}dt+d^{T}Adt^{2}.$

It follows from the local optimality of $x^{*}$ that $h^{\prime}(0)=0\leq
h^{\prime\prime}(0)$, i.e.,

$\displaystyle d^{T}Bd\leq
0(=0)~{}\Longrightarrow~{}(Ax^{*}+a)^{T}d=0,~{}d^{T}Ad\geq 0.$ (2.9)

We partition the remainder of the proof into three cases.

  * (a)

$B\succeq 0$. By the fact $g(x^{*})=0$ and (2.8), $g(x)\geq 0$ holds for any
$x\in\mathbb{R}^{n}$. Neither Assumption 2 nor Assumption 3 holds.
Consequently, neither $\rm(GT)$ or $\rm(GT_{e})$ has a local nonglobal
minimizer.

  * (b)

$B\preceq 0$. Similar to (a), we have $g(x)\leq 0$, $\forall
x\in\mathbb{R}^{n}$. Then $\rm(GT)$ reduces to the unconstrained optimization
$\min f(x)$ without local nonglobal minimizer. $\rm(GT_{e})$ has no local
nonglobal minimizer as Assumption 3 does not hold.

  * (c)

$B$ is indefinite. According to (P97, , Lemma 3.10), ${\rm span}\\{v:\
v^{T}Bv=0\\}=\mathbb{R}^{n}$. Then it follows from (2.9) that
$(Ax^{*}+a)^{T}d=0$ for all $d\in\mathbb{R}^{n}$, which implies that

$Ax^{*}+a=0.$ (2.10)

By applying S-lemma PT07 ; Y71  (S-lemma with equality X16 ) to

$d^{T}Bd\leq 0~{}(d^{T}Bd=0)\Longrightarrow d^{T}Ad\geq 0,$

which is given in (2.9), we have

$\exists\lambda\geq 0~{}(\lambda\in\mathbb{R}):~{}A+\lambda B\succeq 0.$
(2.11)

Combining (2.8), (2.10)-(2.11) with (2.6)-(2.7), we conclude that $x^{*}$ is a
global minimizer of $\rm(GT)$ (or $\rm(GT_{e})$) according to Theorem 2.2 (or
2.1). This contradicts the assumption on $x^{*}$.

For completeness, we write down the standard second-order necessary and
sufficient optimality conditions for local minimizers of (GT) and
$\rm(GT_{e})$, respectively.

###### Theorem 2.4

  * (1)

(Necessary optimality condition for $\rm(GT)$) If $x^{*}$ is a local minimizer
of $\rm(GT)$ at which LICQ holds, then $g(x^{*})\leq 0$ and there exists
$\lambda^{*}\geq 0$ such that (2.6) holds. Moreover, if $g(x^{*})=0$ and
$\lambda^{*}>0$, then

$\displaystyle v^{T}(A+\lambda^{*}B)v\geq 0,~{}\forall
v\in\mathbb{R}^{n}~{}\text{such that}~{}v^{T}(Bx^{*}+b)=0,$ (2.12)

and if $g(x^{*})=0$ and $\lambda^{*}=0$, it holds that

$\displaystyle v^{T}(A+\lambda^{*}B)v\geq 0,~{}\forall
v\in\mathbb{R}^{n}~{}\text{such that}~{}v^{T}(Bx^{*}+b)\leq 0.$ (2.13)

  * (2)

(Sufficient optimality condition for $\rm(GT)$) Suppose that $g(x^{*})=0$ and
there exists $\lambda^{*}>0$ satisfying (2.6) and

$\displaystyle v^{T}(A+\lambda^{*}B)v>0,~{}\forall
v\in\mathbb{R}^{n}~{}\text{such that}~{}v^{T}(Bx^{*}+b)=0,~{}v\neq 0.$ (2.14)

Then $x^{*}$ is a strict local minimizer of $\rm(GT)$.

  * (3)

(Necessary optimality condition for $\rm(GT_{e})$) If $x^{*}$ is a local
minimizer of $\rm(GT_{e})$ at which LICQ holds, then $g(x^{*})=0$ and there
exists $\lambda^{*}\in\mathbb{R}$ such that (2.6) and (2.12) hold.

  * (4)

(Sufficient optimality condition for $\rm(GT_{e})$) Suppose that $g(x^{*})=0$
and there exists $\lambda^{*}\in\mathbb{R}$ satisfying (2.6) and (2.14). Then
$x^{*}$ is a strict local minimizer of $\rm(GT_{e})$.

##  3 Local optimality condition for local nonglobal minimizer

In this section, we first show that the strict complementary condition holds
at any local nonglobal minimizer of (GT), and then prove that the standard
second-order sufficient optimality condition for any local minimizer of (GT)
(or $\rm(GT_{e})$) is surprisingly necessary.

###### Theorem 3.1

Under Assumptions 1 and 2, if $x^{*}$ is a local nonglobal minimizer of
$\rm(GT)$, then the strict complementary condition holds at $x^{*}$, i.e., the
corresponding Lagrangian multiplier is positive.

###### Proof

By Lemma 2.1, $g(x^{*})=0$. According to Theorem 2.3, LICQ holds at $x^{*}$.
Let $\lambda^{*}$ be the Lagrangian multiplier corresponding to $x^{*}$.
According to Theorem 2.4, (2.6) holds. Now it is sufficient to prove
$\lambda^{*}>0$. Suppose, on the contrary, it holds that $\lambda^{*}=0$. By
(2.13), we have

$v^{T}Av\geq 0,~{}\forall v\in\mathbb{R}^{n}~{}\text{such
that}~{}v^{T}(Bx^{*}+b)\leq 0,$

which is equivalent to

$v^{T}Av\geq 0,~{}\forall v\in\mathbb{R}^{n},$

since $v^{T}Av=(-v)^{T}A(-v)$. Therefore, we obtain $A\succeq 0$. Now
(2.6)-(2.7) hold with $\lambda^{*}=0$. According to Theorem 2.2, $x^{*}$ is a
global minimizer of (GT). This contradicts the assumption that $x^{*}$ is a
local nonglobal minimizer.

For local nonglobal minimizer of $\rm(GT)$ (or $\rm(GT_{e})$) $x^{*}$ and its
Lagrangian multiplier $\lambda^{*}$, according to Theorem 2.2 (or Theorem
2.1), $A+\lambda^{*}B$ has at least one negative eigenvalue. On the other
hand, as a direct corollary of Theorems 2.3, 2.4 and 3.1, $A+\lambda^{*}B$ has
at most one negative eigenvalue. Consequently, we have established the
following necessary optimality condition for any local nonglobal minimizer of
$\rm(GT)$ (or $\rm(GT_{e})$).

######  Corollary 3.1 (TS20 , Lemma 3.1)

Let $x^{*}$ be a local nonglobal minimizer of $\rm(GT)$ (or $\rm(GT_{e})$) and
$\lambda^{*}\geq 0$ (or $\lambda^{*}\in\mathbb{R}$) be the corresponding
Lagrangian multiplier. Under Assumptions 1 and 2 (or Assumptions 1 and 3),
$A+\lambda^{*}B$ has exactly one negative eigenvalue.

As a main result, we prove that the standard second-order sufficient
optimality condition for any local nonglobal minimizer of $\rm(GT_{e})$ is
necessary.

###### Theorem 3.2

Suppose Assumptions 1, 3 and 6 hold, and $x^{*}$ is not a global minimizer of
$\rm(GT_{e})$. Then $x^{*}$ is a local minimizer of $\rm(GT_{e})$ if and only
if $g(x^{*})=0$ and there exists a $\lambda^{*}\in\mathbb{R}$ satisfying (2.6)
and (2.14).

###### Proof

Suppose that $x^{*}$ is a local nonglobal minimizer of $\rm(GT_{e})$. Let
$\lambda^{*}\in\mathbb{R}$ be the corresponding Lagrangian multiplier. Then
$g(x^{*})=0$, (2.6) and (2.12) hold by Theorem 2.4. Then
$A+\lambda^{*}B\nsucceq 0$ by Theorem 2.1. Let $G=A+\lambda^{*}B$. We rewrite
the corresponding Lagrangian function as follows:

$\displaystyle L_{1}(x)=f(x)+\lambda^{*}g(x)$ $\displaystyle=$ $\displaystyle
x^{T}Gx+2(a+\lambda^{*}b)^{T}x+\lambda^{*}c$ (3.1) $\displaystyle=$
$\displaystyle x^{T}Gx-2x^{*T}Gx+\lambda^{*}c,$

where the second equality (3.1) follows from (2.6).

It is sufficient to prove that (2.14) holds. Suppose, on the contrary, there
exists a vector $\bar{v}\neq 0$ such that

$\displaystyle\bar{v}^{T}G\bar{v}=0,$ (3.2)
$\displaystyle\bar{v}^{T}(Bx^{*}+b)=0.$ (3.3)

We first claim that

$\displaystyle\bar{v}^{T}B\bar{v}\neq 0.$ (3.4)

If this is not true, we have $\bar{v}^{T}B\bar{v}=0$. By (3.2), we obtain
$\bar{v}^{T}A\bar{v}=0$. Thus, for any $\mu_{1},\mu_{2}\in\mathbb{R}$, we have

$\bar{v}^{T}(\mu_{1}A+\mu_{2}B)\bar{v}=0,$

which contradicts Assumption 6.

We partition the remainder of the proof into two cases.

Case (a). Assume

$\displaystyle G\bar{v}=0.$ (3.5)

According to Corollary 3.1, $G$ has exactly one negative eigenvalue. Let
$w\in\mathbb{R}^{n}$ be a nonzero eigenvector of $G$ corresponding to the
unique negative eigenvalue. Then we must have

$w^{T}(Bx^{*}+b)\neq 0,$

since otherwise, according to (2.12), it holds that $w^{T}Gw\geq 0$, which
contradicts the definition of $w$.

Define the function $h:\mathbb{R}^{2}\mapsto\mathbb{R}$ as

$\displaystyle h(s,t)$ $\displaystyle:=$ $\displaystyle g(x^{*}+t\bar{v}+sw)$
(3.6) $\displaystyle=$
$\displaystyle(x^{*}+t\bar{v}+sw)^{T}B(x^{*}+t\bar{v}+sw)+2b^{T}(x^{*}+t\bar{v}+sw)+c$
$\displaystyle=$ $\displaystyle\bar{v}^{T}B\bar{v}\cdot t^{2}+w^{T}Bw\cdot
s^{2}+2w^{T}(B(x^{*}+t\bar{v})+b)\cdot s,$

where (3.6) follows from the fact $g(x^{*})=0$ and (3.3). We can verify that

$h(0,0)=0,~{}\frac{\partial h}{\partial s}(0,0)=2w^{T}(Bx^{*}+b)\neq 0.$

According to the implicit function theorem in multi-variable calculus, there
are two open intervals $I_{1},I_{2}\subset\mathbb{R}$ with $0\in I_{1}\bigcap
I_{2}$ and a continuous function $s(t):I_{1}\mapsto I_{2}$ such that $s(0)=0$.
Moreover, for any $t\in I_{1}$, the point $s(t)\in I_{2}$ is a unique point
satisfying

$\displaystyle h(s(t),t)=0.$ (3.7)

By (3.4), (3.6) and (3.7), it holds that

$\displaystyle s(t)\neq 0,~{}\forall t\neq 0.$ (3.8)

Define $x(t):=x^{*}+t\bar{v}+s(t)w$. By the definition of $h(s,t)$ and (3.7),
we have $g(x(t))=0$. Therefore, for any sufficiently small $|t|$ and $t\neq
0$, $x(t)$ is a feasible point in the neighborhood of $x^{*}$. Moreover,
according to (3.1), (3.5) and (3.8), we can verify that

$f(x(t))=L_{1}(x(t))=w^{T}Gw\cdot
s(t)^{2}+L_{1}(x^{*})<L_{1}(x^{*})=f(x^{*}),$

which contradicts the assumption that $x^{*}$ is a local minimizer of
$\rm(GT_{e})$.

Case (b). Assume

$\displaystyle G\bar{v}\neq 0.$ (3.9)

We further consider three subcases with different values of
$c\in\\{-1,1,0\\}$.

Subcase (b1). $c=-1$. For any real number $t$, we can verify that

$\displaystyle(x^{*}+t\bar{v})^{T}B(x^{*}+t\bar{v})+2b^{T}(x^{*}+t\bar{v})$
(3.10) $\displaystyle=$ $\displaystyle
x^{*T}Bx^{*}+2b^{T}x^{*}+2\bar{v}^{T}(Bx^{*}+b)\cdot
t+\bar{v}^{T}B\bar{v}\cdot t^{2}$ $\displaystyle=$ $\displaystyle
1+\bar{v}^{T}B\bar{v}\cdot t^{2},$ (3.11)

where (3.11) follows from the fact $g(x^{*})=0$, (3.3) and $c=-1$.

Let $x^{*}=[x^{*}_{1};x^{*}_{2}]$ and $\bar{v}=[\bar{v}_{1};\bar{v}_{2}]$,
where $x^{*}_{1},\bar{v}_{1}\in\mathbb{R}^{n_{1}}$ and
$x^{*}_{2},\bar{v}_{2}\in\mathbb{R}^{n_{2}}$. We define
$x(t)=[x_{1}(t);x_{2}(t)]$ as

$\displaystyle
x_{1}(t)=\frac{x^{*}_{1}+t\bar{v}_{1}}{\sqrt{1+\bar{v}^{T}B\bar{v}\cdot
t^{2}}},~{}x_{2}(t)=\frac{x^{*}_{2}+t\bar{v}_{2}}{1+\bar{v}^{T}B\bar{v}\cdot
t^{2}}.$ (3.12)

Then for any sufficiently small $|t|$, the parametric curve $x(t)$ is well
defined. In the remainder of the proof, we always assume that $|t|$ is
sufficiently small. According to (3.10)-(3.12), we have $x(0)=x^{*}$ and
$g(x(t))=0$. Thus, for any $t$, $x(t)$ is a feasible solution of
$\rm(GT_{e})$. Consequently, $0$ is a local minimizer of the univariate
function defined by

$F(t):=f(x(t))=L_{1}(x(t))=x(t)^{T}Gx(t)-2x^{*T}Gx(t)-\lambda^{*}.$

Notice that both $x(t)$ and $F(t)$ are sufficiently smooth. By elementary
analysis, we can verify that

$\displaystyle x^{\prime}(0)$ $\displaystyle=$ $\displaystyle\bar{v},$ (3.13)
$\displaystyle x^{\prime\prime}(0)$ $\displaystyle=$
$\displaystyle-\bar{v}^{T}B\bar{v}\cdot[x^{*}_{1};2x^{*}_{2}],$ (3.14)
$\displaystyle F^{\prime}(0)$ $\displaystyle=$ $\displaystyle 0,$
$\displaystyle F^{\prime\prime}(0)$ $\displaystyle=$ $\displaystyle
2x^{\prime}(0)^{T}Gx^{\prime}(0)=2\bar{v}^{T}G\bar{v}=0,$ (3.15)
$\displaystyle F^{\prime\prime\prime}(0)$ $\displaystyle=$ $\displaystyle
6x^{\prime}(0)^{T}Gx^{\prime\prime}(0)=6\bar{v}^{T}Gx^{\prime\prime}(0),$
(3.16)

where the item $x^{\prime}(0)$ in (3.15)-(3.16) is replaced by $\bar{v}$ due
to (3.13), and the last equality in (3.15) follows from (3.2).

Let $W\in\mathbb{R}^{n\times(n-1)}$ be a full column-rank matrix whose columns
form a basis of the $(n-1)$-dimensional subspace given by

$\displaystyle\\{v\in\mathbb{R}^{n}:~{}v^{T}(Bx^{*}+b)=0\\}.$ (3.17)

That is, $W^{T}(Bx^{*}+b)=0$. By (2.12) in Theorem 2.4, we have

$\displaystyle W^{T}GW=W^{T}(A+\lambda^{*}B)W\succeq 0.$ (3.18)

According to (3.3) and $\bar{v}\neq 0$, there exists a nonzero
$\bar{u}\in\mathbb{R}^{n-1}$ such that

$\displaystyle\bar{v}=W\bar{u}.$ (3.19)

Substituting (3.19) into (3.2) yields that

$\displaystyle\bar{u}^{T}W^{T}GW\bar{u}=0.$ (3.20)

Then it follows from (3.18)-(3.20) that

$\displaystyle 0=W^{T}GW\bar{u}=W^{T}G\bar{v}.$ (3.21)

Since $W^{T}(Bx^{*}+b)=0$ and $W$ is of full column-rank, (3.21) implies that

$\displaystyle G\bar{v}=\gamma(Bx^{*}+b)$ (3.22)

with $\gamma\neq 0$ due to (3.9). Substituting (3.14) and (3.22) into (3.16)
leads to

$\displaystyle
F^{\prime\prime\prime}(0)=-6\gamma\cdot\bar{v}^{T}B\bar{v}\cdot(x^{*T}Bx^{*}+2b^{T}x^{*})=-6\gamma\cdot\bar{v}^{T}B\bar{v}\neq
0,$

where the second equality holds as $g(x^{*})=0$ and $c=-1$, and the last
inequality follows from $\gamma\neq 0$ and (3.4). Therefore, $t=0$ is not a
local minimizer of $F(t)$. This contradicts the fact that $x^{*}$ is a local
minimizer of $\rm(GT_{e})$.

Subcase (b2). $c=1$. By (3.10), we have

$(x^{*}+t\bar{v})^{T}B(x^{*}+t\bar{v})+2b^{T}(x^{*}+t\bar{v})=-1+\bar{v}^{T}B\bar{v}\cdot
t^{2}.$

Then we define $x(t)=[x_{1}(t);x_{2}(t)]$ by

$\displaystyle
x_{1}(t)=\frac{x^{*}_{1}+t\bar{v}_{1}}{\sqrt{1-\bar{v}^{T}B\bar{v}\cdot
t^{2}}},~{}x_{2}(t)=\frac{x^{*}_{2}+t\bar{v}_{2}}{1-\bar{v}^{T}B\bar{v}\cdot
t^{2}},$

as a replacement of the definition $x(t)$ in (3.12). Based on a proof similar
to that of Subcase (b1), we can obtain a contradiction for Subcase (b2).

Subcase (b3). $c=0$. We first consider the case that $n_{2}\geq 1$ and
$b_{2}\neq 0$. For any feasible point of $\rm(GT_{e})$ with the partition
$x=[x_{1};x_{2}]$ where $x_{1}\in\mathbb{R}^{n_{1}}$ and
$x_{2}\in\mathbb{R}^{n_{2}}$, we have

$g(x)=x_{1}^{T}B_{1}x_{1}+2b_{2}^{T}x_{2}+0=x_{1}^{T}B_{1}x_{1}+2b_{2}^{T}\left(x_{2}+\frac{b_{2}}{2\|b_{2}\|^{2}}\right)-1.$

Then by a linear transformation, we are back to Subcase (b1) with respect to
the new variables

$\hat{x}:=\left[x_{1};x_{2}+\frac{b_{2}}{2\|b_{2}\|^{2}}\right].$

The remainder case is either $n_{2}\geq 1$ and $b_{2}=0$ or $n_{2}=0$. In this
case, we always have $b=0$. $\rm(GT_{e})$ can be equivalently homogenized to
the following equality-constrained quadratic optimization:

${\rm(QQ_{2})}~{}~{}\min\left\\{q_{0}(y):~{}q_{1}(y)=1,~{}q_{2}(y)=1,~{}y\in\mathbb{R}^{n+1}\right\\},$

where $q_{i}(y)=y^{T}A_{i}y$ for $i=0,1,2$, and

$A_{0}=\left[{\begin{array}[]{*{20}{c}}A&a\\\
a^{T}&0\end{array}}\right],~{}A_{1}=\left[{\begin{array}[]{*{20}{c}}0&0\\\
0&1\end{array}}\right],~{}A_{2}=\left[{\begin{array}[]{*{20}{c}}B&0\\\
0&1\end{array}}\right].$ (3.23)

Clearly, $x^{*}$ is a local nonglobal minimizer of $\rm(GT_{e})$, if and only
if $y^{*}:=[x^{*};1]$ is a local nonglobal minimizer of ${\rm(QQ_{2})}$. The
corresponding Lagrangian function is given by

$\displaystyle L_{2}(y)$ $\displaystyle=$ $\displaystyle
q_{0}(y)+\lambda_{1}(q_{1}(y)-1)+\lambda_{2}(q_{2}(y)-1)$ (3.24)
$\displaystyle=$ $\displaystyle
y^{T}(A_{0}+\lambda_{1}A_{1}+\lambda_{2}A_{2})y-\lambda_{1}-\lambda_{2}.$

Since LICQ clearly holds at $y^{*}$, by the first-order optimality condition,
it holds that

$\displaystyle(A+\lambda_{2}B)x^{*}+a=0,$ (3.25) $\displaystyle
a^{T}x^{*}+\lambda_{1}+\lambda_{2}=0.$ (3.26)

Substituting (2.6) into (3.25) yields that

$(\lambda_{2}-\lambda^{*})Bx^{*}=0.$

By Theorem 2.3, $\nabla g(x^{*})=2Bx^{*}\neq 0$. Therefore, we have
$\lambda_{2}=\lambda^{*}$. It follows from (2.6) and $g(x^{*})=0$ that

$\displaystyle a^{T}x^{*}=-x^{*T}(A+\lambda^{*}B)x^{*}=-x^{*T}Ax^{*}.$ (3.27)

Then, by (3.26)-(3.27) and $\lambda_{2}=\lambda^{*}$, we have
$\lambda_{1}=x^{*T}Ax^{*}-\lambda^{*}$. Therefore, by introducing
$H=A_{0}+(x^{*T}Ax^{*}-\lambda^{*})A_{1}+\lambda^{*}A_{2}$, (3.24) reduces to

$\displaystyle L_{2}(y)=y^{T}Hy-x^{*T}Ax^{*}.$

Define $\bar{w}:=[\bar{v};0]\in{\mathbb{R}}^{n+1}$, where $\bar{v}$ satisfies
(3.2)-(3.3) and (3.22) with $\gamma\neq 0$. We can verify that

$\displaystyle Hy^{*}=0,$ (3.28)
$\displaystyle\bar{w}^{T}H\bar{w}=\bar{v}^{T}G\bar{v}=0,$ (3.29)
$\displaystyle\bar{w}^{T}A_{1}y^{*}=0,~{}\bar{w}^{T}A_{2}y^{*}=0,$ (3.30)
$\displaystyle a^{T}\bar{v}=-x^{*T}G\bar{v}=-\gamma x^{*T}Bx^{*}=0,$ (3.31)

where (3.28) follows from (2.6) and (3.27), (3.29)-(3.30) hold due to
(3.2)-(3.3), and the three equalities in (3.31) are implied from (2.6), (3.22)
and the fact $g(x^{*})=0$, respectively. Then, by (3.22) and (3.31), we have

$\displaystyle H\bar{w}=[G\bar{v};a^{T}\bar{v}]=[\gamma Bx^{*};0].$ (3.32)

The following proof is extended from the proof for Case (c) in Theorem 4.2 in
S21 . Actually, (S21, , Theorem 4.2) states that the standard second-order
sufficient optimality condition for any strict local nonglobal minimizer of
$\rm(QQ_{2})$ is necessary under the assumption
$\mu_{1}A_{1}+\mu_{2}A_{2}\succ 0$ for some $\mu_{1},\mu_{2}\in\mathbb{R}$.
However, according to the definitions (3.23), this assumption fails to hold
for our case except that $B\succ 0$.

Under Assumption 6, $A$ and $B$ are simultaneously diagonalizable by
congruence. Through a suitable linear transformation, we can directly assume
that both $A$ and $B$ are diagonal matrices. Let

$A={\rm Diag}(\alpha_{1},\cdots,\alpha_{n}),~{}B={\rm
Diag}(\beta_{1},\cdots,\beta_{n_{1}},0,\cdots,0),$ (3.33)

where $n_{1}\geq 1$ and $\beta_{1},\cdots,\beta_{n_{1}}\neq 0$. Since $\nabla
g(x^{*})=2Bx^{*}\neq 0$ due to Theorem 2.3, without loss of generality, we can
assume that the first component of $y^{*}$ (the same as the first component of
$x^{*}$) is nonzero, i.e., $y^{*}_{1}\neq 0$. We further assume $y^{*}_{1}>0$,
as the negative case can be proved similarly.

Let $\bar{I}={\rm Diag}(0,1,\cdots,1)$ and $e_{1}=[1,0,\cdots,0]^{T}$ and
define

$\displaystyle
z(t)=\bar{I}(y^{*}+t\bar{w}),~{}y(t)=z(t)+\sqrt{\frac{1-z(t)^{T}A_{2}z(t)}{\beta_{1}}}\cdot
e_{1}.$

Notice that

$\displaystyle z(0)=[0,y^{*}_{2},\cdots,y^{*}_{n},1]^{T},$
$\displaystyle\frac{1-z(0)^{T}A_{2}z(0)}{\beta_{1}}=y_{1}^{*2}>0,$ (3.34)
$\displaystyle
y(0)=z(0)+\sqrt{\frac{1-z(0)^{T}A_{2}z(0)}{\beta_{1}}}e_{1}=\bar{I}y^{*}+y^{*}_{1}e_{1}=y^{*}.$
(3.35)

It follows from (3.34) that $y(t)$ is well defined for sufficiently small
$|t|$. Moreover, we can verify that $y(t)$ is a feasible point of
$\rm(QQ_{2})$ by the following equalities:

$\displaystyle y(t)^{T}A_{1}y(t)=1,$ $\displaystyle
y(t)^{T}A_{2}y(t)=z(t)^{T}A_{2}z(t)+\beta_{1}\left(\sqrt{\frac{1-z(t)^{T}A_{2}z(t)}{\beta_{1}}}\right)^{2}=1.$

According to (3.3), we can verify that

$\displaystyle z^{\prime}(0)=\bar{I}\bar{w},~{}z^{\prime\prime}(0)=0,$
$\displaystyle
y^{\prime}(0)=\bar{w},~{}y^{\prime\prime}(0)=-\frac{\bar{v}^{T}B\bar{v}}{\beta_{1}y^{*}_{1}}e_{1}.$
(3.36)

For any sufficiently small $|t|$, we define

$\phi(t):=q_{0}(y(t))=L_{2}(y(t))=y(t)^{T}Hy(t)-x^{*T}Ax^{*}.$

Under the assumption that $y^{*}$ is a local minimizer of $\rm(QQ_{2})$, $t=0$
is a local minimizer of $\phi(t)$. Elementary analysis shows that

$\displaystyle\phi^{\prime}(0)$ $\displaystyle=$ $\displaystyle
2y(0)^{T}Hy^{\prime}(0),$ $\displaystyle\phi^{\prime\prime}(0)$
$\displaystyle=$ $\displaystyle
2y(0)^{T}Hy^{\prime\prime}(0)+2y^{\prime}(0)^{T}Hy^{\prime}(0),$
$\displaystyle\phi^{\prime\prime\prime}(0)$ $\displaystyle=$ $\displaystyle
2y(0)^{T}Hy^{\prime\prime\prime}(0)+6y^{\prime}(0)^{T}Hy^{\prime\prime}(0).$

By (3.28)-(3.29), (3.32) and (3.35)-(3.36), we can simplify the above three
equalities as

$\displaystyle\phi^{\prime}(0)$ $\displaystyle=$ $\displaystyle 0,$ (3.37)
$\displaystyle\phi^{\prime\prime}(0)$ $\displaystyle=$ $\displaystyle
2\bar{w}^{T}H\bar{w}=0,$ (3.38) $\displaystyle\phi^{\prime\prime\prime}(0)$
$\displaystyle=$
$\displaystyle-6\frac{\bar{v}^{T}B\bar{v}}{\beta_{1}y_{1}}e_{1}^{T}H\bar{w}=-6\gamma\bar{v}^{T}B\bar{v}.$

According to the fact $\gamma\neq 0$ and (3.4), we have
$\phi^{\prime\prime\prime}(0)\neq 0$, which, together with (3.37)-(3.38),
implies that $t=0$ is not a local minimizer of $\phi(t)$. This contradiction
completes the proof.

Based on Theorem 3.1 and the proof of Theorem 3.2, we can show the necessity
of the standard second-order sufficient optimality condition for any local
nonglobal minimizer of (GT).

###### Theorem 3.3

Under Assumptions 1, 2 and 6, $x^{*}$ is a local nonglobal minimizer of
$\rm(GT)$ if and only if $g(x^{*})=0$ holds, and there exists a
$\lambda^{*}>0$ satisfying (2.6), (2.14) and $A+\lambda^{*}B\nsucceq 0$.

Since the standard second-order sufficient optimality condition implies
strictness of any local nonglobal minimizer, according to Theorems 3.2 and
3.3, we have the following result.

###### Corollary 3.2

Under Assumptions 1, 2 (or 3) and 6, any local nonglobal minimizer of
$\rm(GT)$ (or $\rm(GT_{e})$) is isolated.

Taati and Salahi TS20  extended the eigenvalue-based algorithm S17  to find at
most $2n+1$ candidates of local nonglobal minimizers of (GT) (or
$\rm(GT_{e})$). The worst-case complexity is $O(n^{4})$. With the help of
Theorem 3.2 (or 3.3), now one can check whether a candidate solution is a
local nonglobal minimizer of (GT) (or $\rm(GT_{e})$) in $O(n^{3})$ time. As a
conclusion, we have the following result.

###### Corollary 3.3

All local nonglobal minimizers of $\rm(GT)$ (or $\rm(GT_{e})$) can be found in
$O(n^{4})$ time.

##  4 Number of local nonglobal minimizers

In this section, we first overestimate the number of local nonglobal
minimizers of $\rm(GT)$ (or $\rm(GT_{e})$). Then, by an example, we show that
$\rm(GT)$ (or $\rm(GT_{e})$) may have two local nonglobal minimizers. In
contrast, we can prove that $\rm(GT)$ (or $\rm(GT_{e})$) in complex domain has
no local nonglobal minimizer. It demonstrates that real-valued optimization
problem is more difficult to solve than its complex version.

###  4.1 Real case

Based on the above results, we can now overestimate the number of local
nonglobal minimizers of $\rm(GT)$ (or $\rm(GT_{e})$).

###### Theorem 4.1

Under Assumptions 1, 2 (or 3) and 6, the number of local nonglobal minimizers
of $\rm(GT)$ (or $\rm(GT_{e})$) is at most $\min\\{n_{1}+1,n\\}$.

###### Proof

Let $x^{*}$ be a local nonglobal minimizer of $\rm(GT)$ (or $\rm(GT_{e})$) and
$\lambda^{*}\geq 0$ (or $\lambda^{*}\in\mathbb{R}$) be the corresponding
Lagrangian multiplier. Under Assumptions 1, 2 (or 3) and 6, according to
Corollary 3.1, Theorems 3.2 and 3.3, we have that $A+\lambda^{*}B$ is
nonsingular. It then follows from (2.6) that

$x^{*}=-(A+\lambda^{*}B)^{-1}(a+\lambda^{*}b).$ (4.1)

By substituting (4.1) into $g(x^{*})=0$, we can see that $\lambda^{*}$ is a
zero point of the following secular function

$\varphi(\lambda)=(a+\lambda b)^{T}(A+\lambda B)^{-1}B(A+\lambda
B)^{-1}(a+\lambda b)-2b^{T}(A+\lambda B)^{-1}(a+\lambda b)+c.$

According to (3.33) under Assumption 6, we can rewrite $\varphi(\lambda)$ as

$\varphi(\lambda)=\sum_{i=1}^{n_{1}}\frac{\beta_{i}(a_{i}+\lambda
b_{i})^{2}}{(\alpha_{i}+\lambda\beta_{i})^{2}}+\sum_{i=n_{1}+1}^{n_{1}+n_{2}}\frac{\beta_{i}(a_{i}+\lambda
b_{i})^{2}}{\alpha_{i}^{2}}-2\sum_{i=n_{1}+1}^{n_{1}+n_{2}}\frac{b_{i}(a_{i}+\lambda
b_{i})}{\alpha_{i}}+c.$

Therefore, if $n_{1}<n$, the fraction polynomial $\varphi(\lambda)$ has at
most $2(n_{1}+1)$ zero points, and otherwise $n_{1}=n$, then
$\varphi(\lambda)=0$ has at most $2n_{1}$ roots. As a summary,
$\varphi(\lambda)$ has at most $2\min\\{n_{1}+1,n\\}$ zero points.

On the other hand, based on the proof of Theorem 3.7 in TS20 , one can observe
that (2.14) (which holds due to Theorems 3.2 and 3.3) implies

$\varphi^{\prime}(\lambda^{*})>0.$ (4.2)

Since $\varphi(\lambda)$ is a univariate fraction polynomial and hence
$\varphi^{\prime}(\lambda_{1})\varphi^{\prime}(\lambda_{2})\leq 0$ for any two
adjacent zero points of $\varphi(\lambda)$ denoted by $\lambda_{1}$ and
$\lambda_{2}$, half of the $2\min\\{n_{1}+1,n\\}$ zero points satisfy (4.2).
This completes the proof.

The next example shows that the upper bound given in Theorem 4.1 is tight at
least for two-dimensional $\rm(GT)$ (or $\rm(GT_{e})$).

###### Example 4.1

Consider an example of $\rm(GT_{e})$ with $n=2$:

$\min\\{y^{2}+z^{2}+12y+8z:~{}yz=1,~{}(y,z)\in\mathbb{R}^{2}\\}.$ (4.3)

By substituting $z=1/y$ into the objective function, we obtain the following
equivalent univariate unconstrained optimization:

$\min\left\\{y^{2}+\frac{1}{y^{2}}+12y+\frac{8}{y}:~{}y\in\mathbb{R}\right\\}.$
(4.4)

As plotted in Fig. 1, the problem (4.4) is upper unbounded and has four
critical points including two local nonglobal minimizers.

Figure 1:  Variation of the objective function of (4.4).

We modify (4.3) to the following two-dimensional example of $\rm(GT)$:

$\min\\{y^{2}+z^{2}+12y+8z:~{}yz-1\leq 0,~{}(y,z)\in\mathbb{R}^{2}\\}.$ (4.5)

Problem (4.5) has the same two local nonglobal minimizers as (4.3).

Example 4.1 also implies the following observation.

###### Proposition 4.1

$\rm(GT)$ (or $\rm(GT_{e})$) may have more than one local nonglobal minimizer.

###  4.2 Complex case

Complex-valued optimization problems naturally arise in many applications
including estimation problems in Fourier domain, signal constellations and
narrow-band array processing. The subproblem (34) in Yu16  for designing the
hybrid precoder in millimeter wave MIMO system is exactly a complex-valued
trust-region subproblem. In this subsection, we study the generalized trust-
region subproblem in the complex domain:

$\displaystyle(\rm GT^{c})$
$\displaystyle\min\\{z^{H}Az+2\Re(a^{H}z):~{}z^{H}Bz+2\Re(b^{H}z)+c\leq
0,~{}z\in\mathbb{C}^{n}\\},$ $\displaystyle(\rm GT_{e}^{c})$
$\displaystyle\min\\{z^{H}Az+2\Re(a^{H}z):~{}z^{H}Bz+2\Re(b^{H}z)+c=0,~{}z\in\mathbb{C}^{n}\\},$

where $A,B\in\mathbb{C}^{n\times n}$ are Hermitian matrices,
$a,b\in\mathbb{C}^{n}$ and $c\in\mathbb{R}$. Notice that with the setting
$x={\Re(z)}$ and $y={\Im(z)}$, we can verify that

$\displaystyle z^{H}Az+2\Re(a^{H}z)$ $\displaystyle=$ $\displaystyle
x^{T}\Re(A)x+y^{T}\Re(A)y+2{\Re(a)}^{T}x+2{\Im(a)}^{T}y$ $\displaystyle-$
$\displaystyle x^{T}\Im(A)y+y^{T}\Im(A)x,$

where $\Im(A)\in\mathbb{R}^{n\times n}$ is a skew-symmetric matrix, i.e.,
$\Im(A)^{T}=-\Im(A)$. Then $(\rm GT^{c})$ and $(\rm GT_{e}^{c})$ can be
rewritten as the following problems in $\mathbb{R}^{2n}$:

$\displaystyle(\rm GT^{r})$ $\displaystyle\min\\{F(w):~{}G(w)\leq
0,~{}w\in\mathbb{R}^{2n}\\},$ $\displaystyle(\rm GT_{e}^{r})$
$\displaystyle\min\\{F(w):~{}G(w)=0,~{}w\in\mathbb{R}^{2n}\\},$

respectively, where

$\displaystyle F(w)=w^{T}\begin{bmatrix}\Re(A)&-\Im(A)\\\
\Im(A)&\Re(A)\end{bmatrix}w+2{(\Re(a),\Im(a))}^{T}w,$ $\displaystyle
G(w)=w^{T}\begin{bmatrix}\Re(B)&-\Im(B)\\\
\Im(B)&\Re(B)\end{bmatrix}w+2{(\Re(b),\Im(b))}^{T}w+c.$

The above linear transformation establishes the following equivalence.

###### Lemma 4.1

$\bar{z}$ is a local/global minimizer of $(\rm GT^{c})$ (or $(\rm
GT_{e}^{c})$) if and only if $(\Re(\bar{z}),\Im(\bar{z}))$ is that of $(\rm
GT^{r})$ (or $(\rm GT_{e}^{r})$).

Different from real-valued generalized trust-region subproblem, the complex
version has no local nonglobal minimizer.

###### Theorem 4.2

Under complex versions of Assumptions 1, 2 (or 3) and 6, neither $(\rm
GT^{c})$ nor $(\rm GT_{e}^{c})$ has a local nonglobal minimizer.

###### Proof

Under complex versions of Assumptions 1, 2 (or 3) and 6, we can first verify
that Assumptions 1, 2 (or 3) and 6 are satisfied for $(\rm GT^{r})$ (or $(\rm
GT_{e}^{r})$).

Notice that the Hessian matrix of the Lagrangian function of $(\rm GT^{r})$
(or $(\rm GT_{e}^{r})$) is given by

$\displaystyle H(\lambda):=\begin{bmatrix}\Re(A)&-\Im(A)\\\
\Im(A)&\Re(A)\end{bmatrix}+\lambda\begin{bmatrix}\Re(B)&-\Im(B)\\\
\Im(B)&\Re(B)\end{bmatrix}.$

For any fixed $\lambda\in\mathbb{R}$, let $\mu$ be an eigenvalue of
$H(\lambda)$ and $[v_{1};v_{2}](\neq 0)$ be the corresponding eigenvector,
then $[v_{1};v_{2}]^{T}[-v_{2};v_{1}]=0$ and

$H(\lambda)[v_{1};v_{2}]=\mu[v_{1};v_{2}]\Longleftrightarrow
H(\lambda)[-v_{2};v_{1}]=\mu[-v_{2};v_{1}].$

Thus, for any $\lambda\in\mathbb{R}$, the multiplicity of each eigenvalue of
$H(\lambda)$ is greater than or equal to two. Therefore, according to
Corollary 3.1, $(\rm GT^{r})$ (or $(\rm GT_{e}^{r})$) has no local nonglobal
minimizer. By Lemma 4.1, there is no local nonglobal minimizer for $(\rm
GT^{c})$ $\rm(or\ (GT_{e}^{c}))$.

As an application of Theorem 4.2, the extended generalized trust-region
subproblem in complex domain

${\min}\\{z^{H}Az+2\Re(a^{H}z):~{}z^{H}Bz+2\Re(b^{H}z)+c\leq(=)0,~{}h^{H}z+d\leq
0,~{}z\in\mathbb{C}^{n}\\}$

with $h\in\mathbb{C}^{n}$ and $d\in\mathbb{R}$ can be solved efficiently. More
precisely, we first check whether there is a global minimizer of $(\rm
GT^{c})$ (or$(\rm GT_{e}^{c})$) satisfying $h^{H}z+d\leq 0$, and if not then
it is sufficient to solve

$\displaystyle{\min}\\{z^{H}Az+2\Re(a^{H}z):~{}z^{H}Bz+2\Re(b^{H}z)+c\leq(=)0,~{}h^{H}z+d=0,~{}z\in\mathbb{C}^{n}\\},$

which can be reformulated as $(\rm GT^{c})$ (or $(\rm GT_{e}^{c})$) in
$\mathbb{C}^{n-1}$ via variable reduction.

##  5 Conclusions

Trust-region subproblem (T) is fundamental in the area of nonconvex
optimization. It is polynomially solvable based on the inherent hidden
convexity. (T) is shown to have at most one local nonglobal minimizer, which
has been fully characterized recently. We study in this paper the generalized
trust-region subproblem (GT). It inherits the hidden convexity and the global
optimality condition from (T). Different from (T), we show that there may be
more than one local nonglobal minimizer of (GT). Our main contribution in this
paper is to prove that, at any local nonglobal minimizer of (GT), not only the
strict complementarity condition holds, but also the standard second-order
sufficient optimality condition surprisingly remains necessary. As a
corollary, finding all local nonglobal minimizers of (GT) or proving the
nonexistence can be done in $O(n^{4})$ time, where $n$ is the dimension. It is
unknown whether there is an algorithm with lower complexity. We also study
(GT) in complex domain, and show that it has no local nonglobal minimizer. It
is the future work to further tighten the upper bound of the number of local
nonglobal minimizers of real-valued (GT). Though we have proved that two is
tight for two-dimensional problems, in general, the tight upper bound remains
unknown.

## References

  * (1) S. Adachi, S. Iwata, Y. Nakatsukasa, A. Takeda, Solving the trust-region subproblem by a generalized eigenvalue problem, SIAM J. Optim., 27(1) (2017), pp. 269–291.
  * (2) S. Adachi, Y. Nakatsukasa, Eigenvalue-based algorithm and analysis for nonconvex QCQP with one constraint, Math. Program., 173(1) (2019), pp. 79–116.
  * (3) A. Beck, A. Ben-Tal, M. Teboulle, Finding a global optimal solution for a quadratically constrained fractional quadratic problem with applications to the regularized total least squares, SIAM J. Matrix Anal. Appl. 28(2) (2006), pp. 425–445.
  * (4) A. Beck, D. Pan On the solution of the GPS localization and circle fitting problems, SIAM J. Optim., 22(1) (2012), pp. 108–134.
  * (5) A. Beck, M. Teboulle, A convex optimization approach for minimizing the ratio of indefinite quadratic functions over an ellipsoid, Math Progrm., 118(1) (2009), pp. 13–35.
  * (6) A. Beck, Y. Vaisbourd, Globally solving the trust region subproblem using simple first-order methods, SIAM J. Optim., 28(3) (2018), pp. 1951–1967.
  * (7) A. Ben-Tal, D. den Hertog, Hidden conic quadratic representation of some nonconvex quadratic optimization problems, Math. Program., 143(1-2) (2014), pp. 1–29.
  * (8) S. Burer, Y. Ye, Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs, Math. Program. Ser. A., 181 (2020), pp. 1–17.
  * (9) A. R. Conn, N. I. M. Gould, P. L. Toint, Trust-region methods, MPS/SIAM Series on Optimization. SIAM, Philadelphia, PA, 2000.
  * (10) J. M. Feng, G. X. Lin, R. L. Sheu, Y. Xia, Duality and solutions for quadratic programming over single non-homogeneous quadratic constraint, J. Glob. Optim. 54(2) (2012), pp. 275–293.
  * (11) W. Gander, Least squares with a quadratic constraint, Numer. Math., 36(3) (1980), pp. 291–307.
  * (12) D. M. Gay, Computing optimal locally constrained steps, SIAM J. Sci. Stat. Comput., 2(2) (1981), pp. 186–197.
  * (13) N. I. M. Gould, S. Lucidi, M. Roma, P. L. Toint, Solving the trust-region subproblem using the Lanczos method, SIAM J. Optim., 9(2) (1999), pp. 504–525.
  * (14) E. Hazan, T. Koren, A linear-time algorithm for trust region problems, Math. Program., 158 (2016), pp. 363–381.
  * (15) N. Ho-Nguyen, F. Kılınç-Karzan, A second-order cone based approach for solving the trust-region subproblem and its variants, SIAM J. Optim., 27 (2017), pp. 1485–1512.
  * (16) N. Ho-Nguyen, F. Kılınç-Karzan, Online first-order framework for robust convex optimization, Oper. Res., 66(6) (2018), pp. 1670–1692.
  * (17) Y. Hsia, R.L. Sheu, Trust region subproblem with a fixed number of additional linear inequality constraints has polynomial complexity, (2013). arXiv:1312.1398.
  * (18) Y. Hsia, G. X. Lin, R. L. Sheu, A revisit to quadratic programming with one inequality quadratic constraint via matrix pencil, Pac. J. Optim. 10(3) (2014), pp. 461-481.
  * (19) K. Huang, N. D. Sidiropoulos, Consensus-ADMM for general quadratically constrained quadratic programming, IEEE Trans. Signal Process., 64 (2016), pp. 5297–5310.
  * (20) R. Jiang, D. Li, Simultaneous diagonalization of matrices and its applications in quadratically constrained quadratic programming, SIAM J. Optim., 26(3) (2016), pp. 1649–1668.
  * (21) R. Jiang, D. Li, Novel reformulations and efficient algorithms for the generalized trust region subproblem, SIAM J. Optim., 29(2) (2019), pp. 1603–1633.
  * (22) R. Jiang, D. Li, A linear-time algorithm for generalized trust region subproblems, SIAM J. Optim., 30(1) (2020), pp. 915–932.
  * (23) R. Jiang, D. Li, B. Wu, SOCP reformulation for the generalized trust region subproblem via a canonical form of two symmetric matrices, Math. Program., 169(2) (2018), pp. 531–563.
  * (24) M. Locatelli, Some results for quadratic problems with one or two quadratic constraints, Oper. Res. Lett., 43(2) (2015), pp. 126–131.
  * (25) S. Lucidi, L. Palagi, M. Roma, On some properties of quadratic programs with a convex quadratic constraint, SIAM J. Optim., 8(1) (1998), pp. 105–122.
  * (26) J. M. Martínez, Local minimizers of quadratic functions on Euclidean balls and spheres, SIAM J. Optim., 4(1) (1994), pp. 159–176.
  * (27) J. J. Moré, D. C. Sorensen, Computing a trust region step, SIAM J. Sci. Statist. Comput., 4(3) (1983), pp. 553–572.
  * (28) J. J. Moré, Generalization of the trust region problem, Optim. Methods Softw., 2(3) (1993), pp. 189–209.
  * (29) J. Peng, Y. Yuan, Optimality conditions for the minimization of a quadratic with two quadratic constraints, SIAM J. Optim., 7 (1997), pp. 579–594.
  * (30) A. H. Phan, M. Yamagishi, D. Mandic, A. Cichocki, Quadratic programming over ellipsoids with applications to constrained linear regression and tensor decomposition, Neural Comput. Appl., 32(2020), pp. 7097–7120.
  * (31) I. Pólik, T. Terlaky, A survey of the S-lemma, SIAM Rev., 49(3) (2007), pp. 371–418.
  * (32) T. K. Pong, H. Wolkowicz, The generalized trust region subproblem, Comput. Optim. Appl., 58(2) (2014), pp. 273–322.
  * (33) F. Rendl, H. Wolkowicz, A semidefinite framework for trust region subproblems with applications to large scale minimization, Math. Program., 77(2) (1997), pp. 273–299.
  * (34) M. Salahi, A. Taati, H. Wolkowicz, Local nonglobal minima for solving large-scale extended trust-region subproblems, Comput. Optim. Appl., 66(2) (2017), pp. 223–244.
  * (35) M. Salahi, A. Taati, An efficient algorithm for solving the generalized trust region subproblem, Comput. Appl. Math., 37(1) (2018), pp. 395–413.
  * (36) M. M. Song, H. Y. Liu, Y. Xia, On local minimizers of quadratically constrained nonconvex homogeneous quadratic optimization with at most two constraints, (2021). arXiv:2107.05816.
  * (37) D. C. Sorensen, Newton’s method with a model trust region modification, SIAM J. Numer. Anal., 19(2) (1982), pp. 409–426.
  * (38) R. J. Stern, H. Wolkowicz, Indefinite trust region subproblems and nonsymmetric eigenvalue perturbations., SIAM J. Optim. 5(2) (1995), pp. 286–313.
  * (39) A. Taati, M. Salahi, On local nonglobal minimizers of quadratic optimization problem with a single quadratic constraint, Numer. Funct. Anal. Optim., 41(8) (2020), pp. 969–1005.
  * (40) S. A. Vavasis, R. Zippel, Proving polynomial time for sphere-constrained quadratic programming, Technical Report 90-1182, Department of Computer Science, Cornell University, Ithaca, NY, 1990.
  * (41) A. L. Wang, F. Kılınç-Karzan, The generalized trust region subproblem: solution complexity and convex hull results, Math. Program., (2020), https://doi.org/10.1007/
s10107-020-01560-8.

  * (42) J. Wang, Y. Xia, A linear-time algorithm for the trust region subproblem based on hidden convexity, Optim. Lett., 11(8) (2017), pp. 1639–1646.
  * (43) J. Wang, Y. Xia, Closing the gap between necessary and sufficient conditions for local nonglobal minimizer of trust region subproblem, SIAM J. Optim., 30(3) (2020), pp. 1980–1995.
  * (44) J. Wang, M. Song, Y. Xia, Trust-region and p-regularized subproblems: local nonglobal minimum is the second smallest objective function value among all first-order stationary points, (2021). arXiv:2108.07963.
  * (45) X. Wang, H. Zhang, Y. Xia, GPS localization problem: a new model and its global optimization, Optim. Engin., 21(3) (2020), pp. 851–866.
  * (46) Y. Xia, A survey of hidden convex optimization, J. Oper. Res. Soc. China, 8(1) (2020), pp. 1–28.
  * (47) Y. Xia, S. Wang, R.L. Sheu, S-Lemma with equality and its applications, Math. Program. Ser. A., 156(1) (2016), pp. 513–547.
  * (48) V. A. Yakubovich, S-procedure in nonlinear control theory, Vestnik Leningrad University, (1971), pp. 64–77.
  * (49) Y. Ye, A new complexity result on minimization of a quadratic function with a sphere constraint, In C. Floudas and P. Pardalos, editors, Recent Advances in Global Optimization. Princeton University Press, Princeton, NJ, 1992.
  * (50) X. Yu, ,J. Shen , J. Zhang, K. B. Letaief, Alternating Minimization Algorithms for Hybrid Precoding in Millimeter Wave MIMO Systems, IEEE Journal of Selected Topics in Signal Processing, 10(3), (2016), pp. 485–500.
  * (51) Y. Yuan, Recent advances in trust region algorithms, Math. Program., 151(1) (2015), pp. 249–281.