remarkRemark hypothesisHypothesis claimClaim On globally solving trust region
subproblem via PG ex_supplement

# On globally solving nonconvex trust region subproblem via projected gradient
method††thanks: Submitted to the editors DATE. This research was supported by
the National Natural Science Foundation of China (Grant Nos. 12171021 and
11822103), and the Beijing Natural Science Foundation (Grant No. Z180005).

Mengmeng Song School of Mathematical Sciences, Beihang University, Beijing
100191, People’s Republic of China, {songmengmeng, yxia<EMAIL_ADDRESS>Yong Xia22footnotemark: 2 Corresponding author.  Jinyang Zheng22footnotemark:
2

###### Abstract

The trust region subproblem (TRS) is to minimize a possibly nonconvex
quadratic function over a Euclidean ball. There are typically two cases for
(TRS), the so-called “easy case” and “hard case”. Even in the “easy case”, the
sequence generated by the classical projected gradient method (PG) may
converge to a saddle point at a sublinear local rate, when the initial point
is arbitrarily selected from a nonzero measure feasible set. To our surprise,
when applying (PG) to solve a cheap and possibly nonconvex reformulation of
(TRS), the generated sequence initialized with any feasible point almost
always converges to its global minimizer. The local convergence rate is at
least linear for the “easy case”, without assuming that we have possessed the
information that the “easy case” holds. We also consider how to use (PG) to
globally solve equality-constrained (TRS).

###### keywords:

Trust region subproblem, Projected gradient method, Global optimization

90C26, 90C20, 90C52

##  1 Introduction

The trust region subproblem (TRS) plays a great role in the trust region
method for solving nonlinear programming problems, see [10, 33]. Typically, we
can write it as the following (possibly nonconvex) quadratic optimization over
the unit Euclidean ball:

(TRS) $\begin{array}[]{cl}\min\left\\{q(x)=\frac{1}{2}x^{T}Hx+c^{T}x:~{}x\in
B_{n}=\\{x\in{\mathbb{R}}^{n}:x^{T}x\leq 1\\}\right\\},\end{array}$

where $H=H^{T}\in{\mathbb{R}}^{n\times n}$ and $c\in{\mathbb{R}}^{n}$. When
$H$ is not positive semidefinite, (TRS) could have a (unique) local non-global
minimizer, see [23, 32] for full characterizations. However, nonconvex (TRS)
could be efficiently and globally solved based on the necessary and sufficient
global optimality condition [14, 24, 27] or the hidden convexity property, see
[34] and references therein. In the literature, there are numerous algorithms
for globally solving (TRS), including the approaches based on finding the zero
point of the secular function in terms of the dual variable by Newton’s method
[24], by bisection method [17] or by a hybrid algorithm combining the former
two methods [35], the Lanczos methods [9, 15, 36], the sequential subspace
method [16], the eigenvector based methods [2, 28], and so on. A notable
simple first-order method is first computing the minimum eigenvalue of $H$,
denoted by $\lambda_{1}$ throughout this paper, and then employing Nesterov’s
accelerated gradient algorithm to solve the convex programming reformulation
of (TRS):

(C)
$\begin{array}[]{cl}\min\left\\{q(x)+\min\\{\frac{\lambda_{1}}{2},0\\}(1-x^{T}x):\,x\in
B_{n}\right\\}.\end{array}$

This two-stage approach is independently proposed in [18, 31], while the
convex reformulation (C) dates back to [12, 35].

The classical projected gradient algorithm (PG) is an efficient first-order
method to solve convex (TRS). It reads as

(PG) $x^{k+1}=P_{B_{n}}(x^{k}-\eta\nabla q(x^{k}))=\left\\{\begin{aligned}
&x^{k}-\eta\nabla q(x^{k}),&&\ {\rm if}\ \|x^{k}-\eta\nabla q(x^{k})\|\leq
1\\\ &\frac{x^{k}-\eta\nabla q(x^{k})}{\|x^{k}-\eta\nabla q(x^{k})\|},&&\ {\rm
otherwise},\end{aligned}\right.$

for $k=0,1,2,\cdots$, where $x^{0}\in B_{n}$ is the initial point,
$\eta\in(0,2/L)$ is the step size, $L={\|H\|}_{2}$ (the spectral norm of $H$)
is the Lipschitz constant so that the gradient $\nabla q(x)$ is Lipschitz
continuous with the constant $L$, and $P_{Q}{(\cdot)}$ is the operator of
metric projection onto the compact set $Q$ with respect to the Euclidean norm
$\|\cdot\|$, i.e., for $y\in{\mathbb{R}}^{n}$,

$P_{Q}{(y)}:=\left\\{x\in Q:~{}\|x-y\|={\rm min}_{z\in Q}\|z-y\|\right\\}.$

In our case, the feasible set $B_{n}$ is convex so that $P_{B_{n}}{(y)}$ is a
single-point set and has a closed-form expression for all
$y\in{\mathbb{R}}^{n}$. The efficiency can be observed from the fact that the
computation in (PG) only relies on matrix-vector products.

One attempt of extending (PG) to solve nonconvex (TRS) is the D.C.
(difference-of-convex) scheme proposed in [29]. However, there is no guarantee
that the returned solution is a global minimizer. Recently, Beck and Vaisbourd
[6] studied a class of first-order methods, including (PG) as an important
case, for globally solving (TRS). They proved that in the “easy case”, the
sequence $\\{x^{k}\\}_{k=0}^{\infty}$ generated by (PG) with $x^{0}=0$
converges to the globally optimal solution, and in the “hard case”, the
sequence $\\{x^{k}\\}_{k=0}^{\infty}$ generated by (PG) converges to the
globally minimizer with probability one when $x^{0}$ is uniformly and randomly
selected from $B_{n}$. Based on these observations, Beck and Vaisbourd [6]
proposed double-start (PG) for globally solving (TRS). More precisely,
although it is unknown which case (“easy case” or “hard case”) holds, it is
sufficient to employ (PG) twice, each with a different initialization, and
then return the better of the two obtained points. Compared with the two-stage
approach based on (C), double-start (PG) has the benefit of running in
parallel.

At the beginning of this study, we show by examples that two disadvantages
exist for double-start (PG). Firstly, the worst convergence rate of double-
start (PG) even for the “easy case” is only sublinear. It is known that in the
“easy case”, the local convergence rate of $\\{x^{k}\\}_{k=0}^{\infty}$
generated by (PG) with $x^{0}=0$ is linear [20] as the sequence converges to
the global minimizer. However, we can use an example in the “easy case” to
show that in the second run of double-start (PG) with $x^{0}$ being uniformly
and randomly selected from $B_{n}$, $\\{x^{k}\\}_{k=0}^{\infty}$ could
converge locally sublinearly to a saddle point with a probability greater than
zero. Secondly, the final two objective function values returned by double-
start (PG) require a high degree of accuracy for correctly comparing.
Otherwise, one may mistake a saddle point or a local non-global minimizer for
the global minimizer. We have an example to show that the gap between local
non-global minimum and global minimum can be arbitrarily small.

The main contribution of this research is to present a one-stage and single-
start (PG). We first present a cheap but novel reformulation of (TRS), which
is a ($2n$)-dimensional (TRS). Though it is possibly nonconvex, the new
reformulation has the nice property that any second-order stationary point
(including local minimizer) is globally optimal. We prove that the sequence
obtained by applying (PG) to solve the new reformulation almost always
converges to its global minimizer for both “easy case” and “hard case”. If the
“easy case” holds (though we do not possess this information), the local
convergence rate is at least linear. Finally, the global minimizer of original
(TRS) is easily recovered by a closed-form expression.

As an extension, we consider globally solving the equality-constrained (TRS):

(TRSe) $\min\left\\{q(x)=\frac{1}{2}x^{T}Hx+c^{T}x:\,x\in\partial
B_{n}=\\{x\in{\mathbb{R}}^{n}:x^{T}x=1\\}\right\\},$

which itself has fruitful applications [25]. Different from (TRS), the
feasible region of (TRSe) is nonconvex. Generalized projected gradient method
(GPG) has been presented for solving the optimization problems over the
nonconvex set, see [3, 19]. For solving (TRSe), the iterative scheme of (GPG)
is given by

(PGe) $x^{k+1}=P_{\partial B_{n}}(x^{k}-\eta_{e}\nabla
q(x^{k}))=\frac{x^{k}-\eta_{e}\nabla q(x^{k})}{\|x^{k}-\eta_{e}\nabla
q(x^{k})\|},$

where $\eta_{e}\in(0,1/L]$ is the step size. If it holds that
$x^{k}-\eta_{e}\nabla q(x^{k})=0$, then the iteration stops as $x^{k}$ is
already a stationary point. With additional assumptions made in [3, Theorems 1
and 2], (GPG) is guaranteed to find the global minimizer. It is observed that
the additional assumptions required in [3, Theorems 1 and 2] are too
restrictive for (PGe). Jain and Kar claimed in [19, Theorem 3.3] that the
sequence generated by (GPG) converges to the global minimizer under their
assumptions. It is, however, not correct as illustrated by an example of
(TRSe). On the other hand, (TRSe) is an optimization problem on the manifold
$\partial B_{n}$ and can be solved by Riemannian gradient method (RG), see
[1]. Lee et al. [21] proved that (RG) almost always avoids strict saddle
points, where the step size has been corrected in [37]. However, (TRSe) could
have a non-strict saddle point or even a local non-global minimizer which can
not be avoided, see examples in [32]. So (RG) may fail to find the global
minimizer. In the second part of this research, we first show that (TRSe) can
be globally solved by employing (PGe) to solve a reformulation similar to that
of (TRS). Finally, to our surprise, we can build a cheap (TRS)-reformulation
of (TRSe) so that it can be globally solved with a step size larger than that
of (PGe).

In the following, we list the contributions of this study.

  * •

Two disadvantages of double-start (PG) are illustrated by examples.

  * •

We cheaply lift (TRS) to an equivalent (possibly nonconvex) (TRS) in
${\mathbb{R}}^{2n}$ so that any second-order stationary point (including local
minimizer) is globally optimal. The global minimizer of the original (TRS) can
be recovered from that of the new reformulation through a closed-form
expression.

  * •

When solving the new reformulation of (TRS) by (PG) with an initial point
uniformly and randomly selected from $B_{2n}$, we prove that the generated
sequence converges to the global minimizer with probability one.

  * •

In the “easy case”, the local convergence rate of our approach is linear,
while it could be sublinear for the second run of double-start (PG).

  * •

We generalize (PG) to globally solve the new similar reformulation of (TRSe).

  * •

As a new approach for solving (TRSe), we apply (PG) to globally solve a novel
cheap (TRS)-reformulation of (TRSe), with a step size larger than that of the
generalized (PG).

The remainder of this paper is organized as follows. Section 2 first presents
classical optimality conditions for (TRS), and then gives two examples to
illustrate two disadvantages of double-start (PG). Section 3 establishes an
equivalent reformulation of (TRS) with a nice property and then proves that
the iterative sequence generated by (PG) for solving this new reformulation
almost always converges to its global minimizer. Section 4 considers globally
solving (TRSe). We conclude the paper in Section 5.

Notation. Denote by $v(\cdot)$ the optimal value of the problem $(\cdot)$. Let
$I$ be the identity matrix of proper dimension. For a square matrix $B$,
$B\succeq 0$ means that $B$ is positive semidefinite, ${B}^{\dagger}$ stands
for the Moore-Penrose pseudoinverse of $B$, ${\rm tr}(B)$ gives the trace of
$B$, $\lambda_{\min}(B)$ denotes the minimum eigenvalue $B$, and ${\rm
Range}(B)$ returns the range (or column) space of $B$. For a vector $x$,
$\|x\|$ denotes the Euclidean norm of $x$. For two scalars $a<b$,
$(a,b):=\\{x\in{\mathbb{R}}:~{}a<x<b\\}$ and
$(a,b]:=\\{x\in{\mathbb{R}}:~{}a<x\leq b\\}$.

##  2 Preliminaries

###  2.1 Known results of (TRS)

Note that the linear independence constraint qualification (LICQ) always holds
at any feasible point of (TRS). For $x^{*}\in{\mathbb{R}}^{n}$, if there
exists $\lambda^{*}$ such that KKT condition

(1) $\displaystyle\lambda^{*}\geq 0,\ (H+\lambda^{*}I)x^{*}+c=0,$ (2)
$\displaystyle\lambda^{*}(x^{*T}x^{*}-1)=0,\ x^{*T}x^{*}-1\leq 0$

hold, then $x^{*}$ is called a stationary point, the pair
$(x^{*},\lambda^{*}/2)$ is called a KKT point, and the nonnegative number
$\lambda^{*}/2$ is called a KKT multiplier corresponding to $x^{*}$. According
to the classical optimization theory, any local minimizer of (TRS) must be a
stationary point. A stationary point is called a saddle point if it is not
locally optimal. In 1980s, (TRS) is proved to enjoy the following necessary
and sufficient condition at its global minimizer.

######  Lemma 2.1 ([14, 24, 27]).

$x^{*}$ is a global minimizer of (TRS) if and only if there exists a unique
$\lambda^{*}$ such that $(x^{*},\lambda^{*}/2)$ is a KKT point and
$\lambda^{*}\geq-\lambda_{1}$, where $\lambda_{1}$ is the minimum eigenvalue
of $H$.

In the literature, if $c\notin{\rm Range}(H-\lambda_{1}I)$, it is called that
“easy case” holds for (TRS), and “hard case” otherwise. Let $x^{*}$ be a
global minimizer of (TRS), and $\lambda^{*}/2$ be the corresponding KKT
multiplier. If the “easy case” occurs, by Lemma 2.1 and $c\notin{\rm
Range}(H-\lambda_{1}I)$, it must hold that $\lambda^{*}>-\lambda_{1}$. The
“hard case” can be further split into three subcases, see details in Table 1,
where only the third case is called “ill case”. Correspondingly, “easy case”
and the first two subcases of “hard case” are collectively referred to as
“well case”.

Table 1: Three subcases of “hard case” for (TRS). hard case $(c\in{\rm
Range}(H-\lambda_{1}I))$
---
hard case (i) | hard case (ii) | hard case (iii) (ill case)
$\lambda^{*}>-\lambda_{1}$ | $\lambda^{*}=-\lambda_{1},~{}\|(H-\lambda_{1}I)^{\dagger}c\|<1$ | $\lambda^{*}=-\lambda_{1},~{}\|(H-\lambda_{1}I)^{\dagger}c\|=1$

If the iterative sequence generated by (PG) converges to a global minimizer of
(TRS) $x^{*}$, Jiang and Li [20] proved that the local convergence rate is at
least linear and sublinear for “well case” and “ill case”, respectively.

######  Lemma 2.2.

([20, Theorem 5.1]) Let $\\{x^{k}\\}_{k=0}^{\infty}$ be the sequence generated
by (PG) with the constant step size $\eta\in(0,2/L)$ and assume that
$\\{x^{k}\\}_{k=0}^{\infty}$ converges to $x^{*}$. Then for any given
$\epsilon>0$, there exists a sufficiently large positive integer $K$ such that
$\\{x^{k}\\}_{k\geq K}\subset
B(x^{*},\epsilon)=\\{x:~{}\|x-x^{*}\|\leq\epsilon\\}$, and in the “ill case”,
it holds that

$f(x^{k})-f^{*}\leq\frac{1}{{\left(\frac{k-K}{2M^{2}+\frac{3}{2}\sqrt{f(x^{K})-f^{*}}}+\frac{1}{\sqrt{f(x^{K})-f^{*}}}\right)}^{2}},~{}\forall
k\geq K.$

Otherwise, we have

$f(x^{k})-f^{*}\leq{\left(\frac{M^{2}}{M^{2}+1}\right)}^{k}(f(x^{K})-f^{*}),~{}\forall
k\geq K,$

where $M$ is a constant related to the input data in (TRS) and the step size
$\eta$.

###  2.2 Disadvantages of double-start (PG)

Double-start (PG) [6] employs (PG) twice with $x^{0}$ being $0$ and uniformly
distributed over $B_{n}$. The two independently generated iterative sequences
converge to two stationary points, denoted by $x_{0}^{*}$ and $x_{B}^{*}$,
respectively. It is proved in [6] that $x_{0}^{*}$ is globally optimal in the
“easy case”, and $x_{B}^{*}$ is globally optimal with probability one in the
“hard case”. Though it is unknown which case holds, one can output the smaller
one of $q(x_{0}^{*})$ and $q(x_{B}^{*})$ as the global minimum, as done in
double-start (PG).

According to Lemma 2.2, the local convergence rate of the sequence converging
to $x_{0}^{*}$ in the “easy case” is linear. However, the local convergence
rate of the sequence converging to $x_{B}^{*}$ remains unknown in the “easy
case”, in case that $x_{B}^{*}$ is not a global minimizer.

Based on an example motivated by [30], we have the following observation on
the convergence and local convergence rate of double-start (PG).

######  Observation 2.1.

In the “easy case” of (TRS), the iterative sequence generated by (PG) with
$x^{0}$ being uniformly and randomly selected from $B_{n}$ could converge to a
saddle point with a probability larger than zero. Moreover, the local
convergence rate could be sublinear.

######  Example 2.3.

Consider the instance of (TRS) with $n=2$ and

(3)
$q(x)=-\frac{13}{2}x_{1}^{2}+\frac{13}{2}x_{2}^{2}-\frac{250}{169}x_{1}+\frac{3456}{169}x_{2}.$

We can verify that the “easy case” holds. With Lemma 2.1, it can be proved
that $x_{0}^{*}=(0.687,-0.726)$ is a global minimizer and
$x_{B}^{*}=(-5/13,-12/13)$ is a saddle point.

We employ (PG) with the step size $\eta=1/13$ to solve Example 2.3. As
illustrated in Figure 1, initialized with $200$ points uniformly and randomly
selected from $B_{2}$, all the independently generated sequences converge to
either the global minimizer $x_{0}^{*}$ or the saddle point $x_{B}^{*}$. It is
clearly observed that the initial points for returning $x_{B}^{*}$ build a
nonzero measure set in $B_{2}$.

Figure 1: Distribution of $200$ initial points starting from which the
iterative sequences generated by (PG) converge to either the global minimizer
$x_{0}^{*}$ or the saddle point $x_{B}^{*}$.

We plot in Figures 2a and 2b the convergence rates. One can observe that the
rates of convergence to the global minimizer $x_{0}^{*}$ and the saddle point
$x_{B}^{*}$ are linear and sublinear, respectively.

(a) Convergence to the global minimizer $x_{0}^{*}$.

(b) Convergence to the saddle point $x_{B}^{*}$.

Figure 2: The rates of convergence to the global minimizer $x_{0}^{*}$ and the
saddle point $x_{B}^{*}$ initialized with different feasible points.

The second disadvantage of double-start (PG) is that approximating
$q(x_{0}^{*})$ and $q(x_{B}^{*})$ requires high enough precision so that one
can correctly compare both values. Otherwise, double-start (PG) could mistake
saddle point/local non-global minimizer for the global minimizer. The
following example implies that the gap between the global minimum and the
local non-global minimum could be arbitrarily small. We remark that the local
non-global minimizer of (TRS) has the second smallest objective function value
among all KKT points [30].

######  Example 2.4.

Consider the parameterized instance of (TRS)τ with $n=2$ and the objective
function

(4)
$q_{\tau}(x)=\frac{13}{2}x_{1}^{2}-\frac{13}{2}x_{2}^{2}+4x_{1}+\tau{\left(x_{2}-\frac{\sqrt{165}}{13}\right)}^{2},$

where $\tau\geq 0$ is a parameter. When $\tau=0$, there are two global
minimizers of (TRS)0, $\bar{x}=(-2/13,\sqrt{165}/13)$ and
$\tilde{x}=(-2/13,-\sqrt{165}/13)$. For any sufficiently small $\tau>0$, it
holds that

$q_{\tau}(x)\geq q_{0}(x)\geq q_{0}(\bar{x})=q_{\tau}(\bar{x}),~{}{\rm\ for\
all\ }x\in B_{2},$

and hence $\bar{x}$ remains globally optimal for (TRS)τ. For such sufficiently
small $\tau>0$, we can verify that (TRS)τ has a local non-global minimizer,
denoted by $\tilde{x}(\tau)$, satisfying that $\lim_{\tau\rightarrow
0^{+}}\tilde{x}(\tau)=\tilde{x}$. Then we have

$\lim_{\tau\rightarrow
0^{+}}q_{\tau}(\tilde{x}(\tau))-q_{0}(\bar{x})=\lim_{\tau\rightarrow
0^{+}}q_{\tau}(\tilde{x}(\tau))-q_{0}(\tilde{x})=0.$

The computational inaccuracy could make double-start (PG) for solving (TRS)τ
output $\tilde{x}(\tau)$ as the global minimizer. Note that $\tilde{x}(\tau)$
is far from the true global minimizer $\bar{x}$.

##  3 Globally solving (TRS) via (PG)

We employ (PG) to solve a novel reformulation of (TRS). The iterative sequence
almost always converges to its global minimizer. The local convergence rate is
linear for the “easy case” without assuming that we have the information that
“easy case” holds. The global minimizer of (TRS) can be quickly recovered from
that of the reformulation.

###  3.1 A novel reformulation of (TRS)

The two-stage algorithm proposed in [18, 31] is based on the equivalent convex
reformulation (C) of (TRS), which requires calculating the minimum eigenvalue
$\lambda_{1}$ in advance. For details, we have the following lemma.

######  Lemma 3.1.

[12, Theorem 1] (TRS) is equivalent to the convex programming relaxation (C)
in the sense that $v\eqref{eq:TRS}=v\eqref{eq:C}$. Moreover, suppose
$\lambda_{1}<0$ and let $v_{1}$ be the corresponding eigenvector. Then for any
optimal solution of (C), say $\tilde{x}$, we can explicitly recover the global
minimizer of (TRS) $x^{*}$ as follows

(5)
$x^{*}=\tilde{x}+\frac{\sqrt{{(\tilde{x}^{T}v_{1})}^{2}-v_{1}^{T}v_{1}(\tilde{x}^{T}\tilde{x}-1)}-\tilde{x}^{T}v_{1}}{v_{1}^{T}v_{1}}v_{1}.$

Note that the cost of building (C) is almost as high as solving (TRS) itself,
since computing $\min\\{\lambda_{1}/2,0\\}$ is equivalent to solving the
following homogeneous (TRS):

$\begin{array}[]{cl}\min\\{\frac{\lambda_{1}}{2},0\\}=\min_{y\in{\mathbb{R}}^{n}}\\{\frac{1}{2}y^{T}Hy:~{}y^{T}y\leq
1\\}.\end{array}$

Accordingly, for any given $x\in B_{n}$, the additional term in the objective
function of (C) can be rewritten as a homogeneous (TRS):

$\begin{array}[]{cl}\min\\{\frac{\lambda_{1}}{2},0\\}(1-x^{T}x)=\min_{y\in{\mathbb{R}}^{n}}\\{\frac{1}{2}y^{T}Hy:\,y^{T}y\leq
1-x^{T}x\\}.\end{array}$

Therefore, (C) is equivalent to the joint minimization problem in
${\mathbb{R}}^{2n}$:

(6)
$\begin{array}[]{cl}\min_{(x,y)\in{\mathbb{R}}^{2n}}\\{q(x)+\frac{1}{2}y^{T}Hy:\,x\in
B_{n},\ y^{T}y\leq 1-x^{T}x\\}.\end{array}$

Since the constraint $x\in B_{n}$ is redundant as

$y^{T}y\leq 1-x^{T}x~{}\Longrightarrow~{}x^{T}x\leq 1~{}({\rm i.e.,}~{}x\in
B_{n}),$

the joint minimization problem (6) equivalently reduces to

(D)
$\begin{array}[]{cl}\min\\{\frac{1}{2}x^{T}Hx+\frac{1}{2}y^{T}Hy+c^{T}x:\,(x,y)\in
B_{2n}\\},\end{array}$

which remains a (possibly nonconvex) (TRS) in ${\mathbb{R}}^{2n}$. Though at
the cost of double variables, building (D) no longer depends on computing
$\lambda_{1}$ when compared with (C).

######  Theorem 3.2.

(TRS) is equivalent to (D) in the sense that $v\eqref{eq:TRS}=v\eqref{eq:C1}$.
Let $(\tilde{x},\tilde{y})$ be an global minimizer of (D). Then, we can
explicitly recover the global minimizer of (TRS) $x^{*}$ as follows:

  * (i)

if $\tilde{y}=0$, then $x^{*}=\tilde{x}$,

  * (ii)

if $\tilde{y}\neq 0$, then the “hard case (ii)” holds for (TRS) and

(7)
$x^{*}=\tilde{x}+\frac{\sqrt{{(\tilde{x}^{T}\tilde{y})}^{2}+\tilde{y}^{T}\tilde{y}(1-\tilde{x}^{T}\tilde{x})}-\tilde{x}^{T}\tilde{y}}{\tilde{y}^{T}\tilde{y}}\tilde{y}.$

######  Proof 3.3.

According to the above derivation of (D), it is sufficient to prove the second
part on recovering the optimal solution of (TRS). According to Lemma 2.1,
$x^{*}$ is a global minimizer of (TRS) if and only if there exists
$\lambda^{*}\geq-\lambda_{1}$ such that (1)-(2) holds. Since (D) is a (TRS) in
${\mathbb{R}}^{2n}$, for a global minimizer of (D), denoted by
$(\tilde{x},\tilde{y})$, there exists
$\tilde{\lambda}\geq\max\\{-\lambda_{1},0\\}$ such that

(8) $\displaystyle(H+\tilde{\lambda}I)\tilde{x}+c=0,\
(H+\tilde{\lambda}I)\tilde{y}=0,$ (9)
$\displaystyle\tilde{\lambda}(\tilde{x}^{T}\tilde{x}+\tilde{y}^{T}\tilde{y}-1)=0,\
\tilde{x}^{T}\tilde{x}+\tilde{y}^{T}\tilde{y}-1\leq 0.$

If $\tilde{y}=0$, set $x^{*}=\tilde{x}$ and $\lambda^{*}=\tilde{\lambda}$,
then (8)-(9) reduce to (1)-(2) with $\lambda^{*}\geq\max\\{-\lambda_{1},0\\}$.
Hence $\tilde{x}$ is a global minimizer of (TRS).

If $\tilde{y}\neq 0$, by (8), we have $\tilde{\lambda}=-\lambda_{1}$ and then
$(H-\lambda_{1}I)\tilde{x}+c=0$. It follows that

${\|(H-\lambda_{1}I)^{\dagger}c\|}^{2}\leq\tilde{x}^{T}\tilde{x}<1,$

where the last inequality holds since $(\tilde{x},\tilde{y})\in B_{2n}$ and
$\tilde{y}\neq 0$. Therefore, “hard case (ii)” defined in Table 1 holds. With
$x^{*}$ defined in (7) and $\lambda^{*}=\tilde{\lambda}$, (1) holds by
(7)-(8). We can also verify that $\|x^{*}\|=1$ so that (2) holds. Therefore,
according to Lemma 2.1, $x^{*}$ defined in (7) globally solves (TRS).

######  Remark 1.

The following standard semidefinite programming (SDP) relaxation for (TRS),

$\begin{array}[]{cl}\min&\frac{1}{2}{\rm tr}(HX)+c^{T}x\\\ {\rm s.t.}&{\rm
tr}(X)\leq 1,\\\ &X-xx^{T}\succeq 0,\end{array}$

is tight, see [26, 34] and references therein. It follows that the above SDP
relaxation always has a rank-one solution, that is, $X=xx^{T}$ holds at an
optimal solution. So we can add the redundant rank constraint

${\rm rank}(X-xx^{T})\leq 1~{}\Longleftrightarrow~{}X=xx^{T}+yy^{T}~{}({\rm
as}~{}X-xx^{T}\succeq 0)$

to the above SDP relaxation and then rebuild our new reformulation (D).

######  Remark 2.

As a direct corollary of the main result in [5], (TRS) is equivalent to its
complex relaxation:

(10)
$\begin{array}[]{cl}\min\\{\frac{1}{2}z^{H}Hz+\mathcal{R}(c^{H}z):\,z^{H}z\leq
1,~{}z\in\mathbb{C}^{n}\\},\end{array}$

where $\mathbb{C}^{n}$ is the $n$-dimensional complex vector space,
$\mathcal{R}(\cdot)$ (resp., $\mathcal{I}(\cdot)$) denotes the real (resp.,
image) part of $(\cdot)$. By introducing $x=\mathcal{R}(z)$ and
$y=\mathcal{I}(z)$, we recover the new reformulation (D) from (10).

Though (D) remains nonconvex if (TRS) is, it enjoys a nice property that (TRS)
does not have. We call $(x^{*},y^{*})$ a second-order stationary point of (D)
if the standard second-order necessary optimality condition [11, 22] holds at
the stationary point $(x^{*},y^{*})$.

######  Proposition 3.4.

Any second-order stationary point of (D) is globally optimal. It follows that
(D) has no local non-global minimizer.

######  Proof 3.5.

Let $(x^{*},y^{*})$ be a second-order stationary point of (D) associated with
the KKT multiplier $\lambda^{*}/2$. If $x^{*T}x^{*}+y^{*T}y^{*}<1$, then by
(2) we have $\lambda^{*}=0$, and the second-order necessary optimality
condition reduces to $H\succeq 0$. According to Lemma 2.1, $(x^{*},y^{*})$ is
a global minimizer of (D). Now we consider the case
$x^{*T}x^{*}+y^{*T}y^{*}=1$. According to the standard second-order necessary
optimality condition, we have

(11) $u^{T}(H+\lambda^{*}I)u+v^{T}(H+\lambda^{*}I)v\geq 0,~{}\
\forall(u,v)\neq(0,0):\ u^{T}x^{*}+v^{T}y^{*}=0.$

We claim that $H+\lambda^{*}I\succeq 0$. Suppose, on the contrary,
$H+\lambda^{*}I$ has a negative eigenvalue associated with the eigenvector
$w\neq 0$. If $w^{T}x^{*}=w^{T}y^{*}=0$ (resp.
$(w^{T}x^{*})^{2}+(w^{T}y^{*})^{2}\neq 0$), setting $u=v=w$ (resp.
$u=-(w^{T}y^{*})w$ and $v=(w^{T}x^{*})w$) in (11) yields a contradiction.

###  3.2 Projected gradient method for globally solving (D)

Let

(12) $A=\left[\begin{array}[]{cc}H&0\\\
0&H\end{array}\right],~{}a=\left[\begin{array}[]{c}c\\\
0\end{array}\right]\in{\mathbb{R}}^{2n}.$

We can rewrite (D) as the following (TRS) in ${\mathbb{R}}^{2n}$:

(D′) $\begin{array}[]{cl}\min\\{f(z)=\frac{1}{2}z^{T}Az+a^{T}z:\,z\in
B_{2n}\\}.\end{array}$

Employing (PG) to solve (D′) gives the following iterative formula:

(PG2) $z^{k+1}=P_{B_{2n}}(z^{k}-\eta\nabla f(z^{k}))=\left\\{\begin{aligned}
&z^{k}-\eta\nabla f(z^{k}),&&\ {\rm if}\ \|z^{k}-\eta\nabla f(z^{k})\|\leq
1\\\ &\frac{z^{k}-\eta\nabla f(z^{k})}{\|z^{k}-\eta\nabla f(z^{k})\|},&&\ {\rm
otherwise},\end{aligned}\right.$

where $\eta\in(0,2/L)$ is the constant step size, $L=\|A\|_{2}=\|H\|_{2}$ is
the same constant as that in (PG). The following convergence result on (PG2)
has been established in the literature.

######  Lemma 3.6.

([4, Theorem 10.15], [6, Theorem 4.5]) Let $\\{z^{k}\\}_{k=0}^{\infty}$ be a
sequence generated by (PG2) with $\eta\in(0,2/L)$. Then
$\\{z^{k}\\}_{k=0}^{\infty}$ converges to a stationary point of (D′).

Surprisingly, we can further prove that the sequence generated by (PG2) almost
always converges to a global minimizer of (D′).

######  Theorem 3.7.

For any $\eta\in(0,2/L)$, let $\\{z^{k}\\}_{k=0}^{\infty}$ be a sequence
generated by (PG2) with $z^{0}$ being uniformly and randomly selected from
$B_{2n}$. Then $\\{z^{k}\\}_{k=0}^{\infty}$ converges to a global minimizer of
(D′) with probability one.

######  Proof 3.8.

According to Lemma 3.6, for any initial point $z^{0}\in B_{n}$,
$\\{z^{k}\\}_{k=0}^{\infty}$ generated by (PG2) converges to a stationary
point of (D′). When $\lambda_{1}\geq 0$, (D′) is a convex optimization
problem, any stationary point is a global minimizer. We assume
$\lambda_{1}<0$. The following proof consists of two parts. First, we prove
that $\\{z^{k}\\}_{k=0}^{\infty}$ converges to a non-globally-minimal
stationary point $\bar{z}$ only if the initial point $z^{0}$ is included in a
zero measure set related to $\bar{\lambda}$, where $\bar{\lambda}/2$ is the
KKT multiplier associated with $\bar{z}$. Second, we prove that (D′) has only
a finite number of KKT multipliers, which will complete the proof since the
measure of the union of a finite number of zero measure sets remains zero.

Proof of the first part. Since $(\bar{z},\bar{\lambda}/2)$ is a KKT point of
(D′), and $\bar{z}\in B_{2n}$ is not a global minimizer, according to Lemma
2.1, it holds that

(13) $\displaystyle\bar{\lambda}\geq 0,$ (14)
$\displaystyle(A+\bar{\lambda}I)\bar{z}+a=0,$ (15) $\displaystyle
A+\bar{\lambda}I\nsucceq 0,$ (16)
$\displaystyle\bar{\lambda}(\bar{z}^{T}\bar{z}-1)=0.$

The minimum eigenvalue of $A+\bar{\lambda}I$ reads as
$\tilde{\lambda}_{1}=\lambda_{1}+\bar{\lambda}$. It follows from (15) that

(17) $\tilde{\lambda}_{1}<0.$

Define two subspaces

(18) $\displaystyle V_{1}$ $\displaystyle=$
$\displaystyle\\{v\in{\mathbb{R}}^{2n}:~{}(A+\bar{\lambda}I)v=\tilde{\lambda}_{1}v\\},$
(19) $\displaystyle V_{2}$ $\displaystyle=$
$\displaystyle\\{v\in{\mathbb{R}}^{2n}:~{}v^{T}{(A+\bar{\lambda}I)}^{\dagger}a=0\\},$

where $V_{1}$ is the eigenspace of $A+\bar{\lambda}I$ associated with the
minimum eigenvalue $\tilde{\lambda}_{1}$, and $V_{2}$ is a hyperplane if
${(A+\bar{\lambda}I)}^{\dagger}a\neq 0$ and the whole space otherwise.
Clearly, the dimension of $V_{2}$ is at least $2n-1$. By the definition of $A$
(12), the dimension of $V_{1}$ is at least two. Since $(2n-1)+2>2n$, the
intersection of $V_{1}$ and $V_{2}$ is a nontrivial subspace, and hence there
exists a nonzero vector $v_{\bar{\lambda}}$ such that $v_{\bar{\lambda}}\in
V_{1}\cap V_{2}$. Note that given the data in (TRS), $v_{\bar{\lambda}}$
depends only on $\bar{\lambda}$. We can further verify that

$\begin{array}[]{lll}{v_{\bar{\lambda}}}^{T}\bar{z}&={v_{\bar{\lambda}}}^{T}[\bar{z}+{(A+\bar{\lambda}I)}^{\dagger}a]&({\rm
as}~{}v_{\bar{\lambda}}\in V_{2})\\\
&=[(A+\bar{\lambda}I)v_{\bar{\lambda}}]^{T}[\bar{z}+{(A+\bar{\lambda}I)}^{\dagger}a]/\tilde{\lambda}_{1}&({\rm
as}~{}v_{\bar{\lambda}}\in V_{1}~{}{\rm and}~{}\tilde{\lambda}_{1}\neq
0~{}\eqref{eq:102})\\\
&={v_{\bar{\lambda}}}^{T}[(A+\bar{\lambda}I)\bar{z}+a]/\tilde{\lambda}_{1}&({\rm
as}~{}a\in{\rm Range}(A+\bar{\lambda}I)~{}{\rm by}~{}\eqref{eq:10})\\\
&=0.&({\rm by}~{}\eqref{eq:10})\end{array}$

In sum, we obtain

(20) $\displaystyle v_{\bar{\lambda}}\neq 0,\
(A+\bar{\lambda}I)v_{\bar{\lambda}}=\tilde{\lambda}_{1}v_{\bar{\lambda}},~{}v_{\bar{\lambda}}^{T}\bar{z}=0.$

We claim that the sequence $\\{z^{k}\\}_{k=0}^{\infty}$ generated by (PG2)
converges to $\bar{z}$ only if the initial point $z^{0}$ satisfies
$v_{\bar{\lambda}}^{T}z^{0}=0$. Suppose on the contrary that

(21) $v_{\bar{\lambda}}^{T}z^{0}\neq 0.$

We first rewrite the iteration formulation as

(22) $z^{k+1}=\frac{z^{k}-\eta(Az^{k}+a)}{r^{k}},~{}k=0,1,2,\cdots,$

where $r^{k}:=\max\\{\|z^{k}-\eta(Az^{k}+a)\|,1\\}$. According to (20), we
have

(23)
$v_{\bar{\lambda}}^{T}a=\tilde{\lambda}_{1}v_{\bar{\lambda}}^{T}\bar{z}+v_{\bar{\lambda}}^{T}a=v_{\bar{\lambda}}^{T}(A+\bar{\lambda}I)\bar{z}+v_{\bar{\lambda}}^{T}a=v_{\bar{\lambda}}^{T}[(A+\bar{\lambda}I)\bar{z}+a]=0,$

where the last equality holds due to (14). Multiplying both sides of (22) with
$v_{\bar{\lambda}}^{T}$ from left yields that

$\displaystyle v_{\bar{\lambda}}^{T}z^{k+1}$ $\displaystyle=$
$\displaystyle\frac{v_{\bar{\lambda}}^{T}z^{k}-\eta(v_{\bar{\lambda}}^{T}Az^{k}+v_{\bar{\lambda}}^{T}a)}{r^{k}}$
$\displaystyle=$
$\displaystyle\frac{v_{\bar{\lambda}}^{T}z^{k}-\eta[v_{\bar{\lambda}}^{T}(A+\bar{\lambda}I)z^{k}-\bar{\lambda}v_{\bar{\lambda}}^{T}z^{k}]}{r^{k}}$
$\displaystyle=$
$\displaystyle\frac{v_{\bar{\lambda}}^{T}z^{k}-\eta[\tilde{\lambda}_{1}v_{\bar{\lambda}}^{T}z^{k}-\bar{\lambda}v_{\bar{\lambda}}^{T}z^{k}]}{r^{k}}$
(25) $\displaystyle=$
$\displaystyle\frac{(1-\eta\tilde{\lambda}_{1}+\eta\bar{\lambda})v_{\bar{\lambda}}^{T}z^{k}}{r^{k}},$

where (3.8) follows from (23). We also have

(26) $\displaystyle{\rm lim}_{k\rightarrow\infty}r^{k}$ $\displaystyle={\rm
lim}_{k\rightarrow\infty}\max\\{\|z^{k}-\eta(Az^{k}+a)\|,1\\}$
$\displaystyle=\max\\{\|\bar{z}-\eta(A\bar{z}+a)\|,1\\}$
$\displaystyle=\max\\{(1+\eta\bar{\lambda})\|\bar{z}\|,1\\},$

where (26) is due to (14). By (13), (17) and $\eta>0$, we have
$1-\eta\tilde{\lambda}_{1}+\eta\bar{\lambda}>1$. According to (25), the sign
of $v_{\bar{\lambda}}^{T}z^{k}$ remains unchanged for all $k$. It follows from
(21) that $v_{\bar{\lambda}}^{T}z^{k}\neq 0$ for $k=0,1,2,\cdots$. By bringing
(26) into (25), we have

(27) ${\rm
lim}_{k\rightarrow\infty}\frac{v_{\bar{\lambda}}^{T}z^{k+1}}{v_{\bar{\lambda}}^{T}z^{k}}=\frac{(1-\eta\tilde{\lambda}_{1}+\eta\bar{\lambda})}{\max\\{(1+\eta\bar{\lambda})\|\bar{z}\|,1\\}}>1,$

where the inequality follows from $\eta>0$, (13), (17) and $\bar{z}\in
B_{2n}$. Therefore, under the assumption (21), it holds that ${\rm
lim}_{k\rightarrow\infty}v_{\bar{\lambda}}^{T}z^{k}\neq 0$, which contradicts
the last equality in (20). We conclude that $\\{z^{k}\\}_{k=0}^{\infty}$
converges to $\bar{z}$ only if $v_{\bar{\lambda}}^{T}z^{0}=0$.

Proof of the second part. We show that (D′) has only a finite number of KKT
multipliers. Let $A=U\Lambda U^{T}$ be an eigenvalue decomposition of $A$,
where
$\Lambda=\operatorname{diag}(\lambda_{1},\lambda_{1},\lambda_{2},\lambda_{2},\cdots,\lambda_{n},\lambda_{n})$
with $\lambda_{1}\leq\cdots\leq\lambda_{n}$ and
$U=[u_{1},\cdots,u_{2n}]\in{\mathbb{R}}^{(2n)\times(2n)}$ is orthonormal.
Suppose that $(\bar{z},\bar{\lambda}/2)$ is a KKT point of (D′) and $\bar{z}$
is not a global minimizer of (D′). Then we have (13)-(16). According to Lemma
2.1, there are three possible cases for $\bar{\lambda}$:

  * (a)

$\bar{\lambda}=0$;

  * (b)

$\bar{\lambda}=-\lambda_{i}$ for some $i\in\\{2,\cdots,n\\}$;

  * (c)

$\bar{\lambda}\neq-\lambda_{i}$ for all $i\in\\{1,\cdots,n\\}$, and

(28) ${\|{(A+\bar{\lambda}I)}^{-1}a\|}^{2}=1.$

Equivalently, $\bar{\lambda}$ is a zero point of

(29)
$\phi(\lambda)=\sum_{i=1}^{n}\frac{(u_{2i-1}^{T}a)^{2}+(u_{2i}^{T}a)^{2}}{{(\lambda_{i}+\lambda)}^{2}}-1.$

It is proved in [23] that $\phi(\lambda)$ defined in (29) is strictly convex
in $(-\lambda_{i+1},-\lambda_{i})$ for $i=1,\cdots,n-1$, and is monotone in
$(-\lambda_{1},+\infty)$ and $(-\infty,-\lambda_{n})$, respectively. Thus,
there are at most $n-1$ and $2n-1$ KKT multipliers smaller than $-\lambda_{1}$
for cases (b) and (c), respectively. In sum, (D′) has at most $3n-1$ KKT
multipliers corresponding to non-globally-minimal stationary points. Denote by
$M$ the set of all these KKT multipliers. Let

(30) $Z=\bigcup_{\bar{\lambda}/2\in
M}\\{z\in{\mathbb{R}}^{2n}:~{}z^{T}v_{\bar{\lambda}}=0\\},$

where $v_{\bar{\lambda}}$ is a nonzero point in $V_{1}\cap V_{2}$ defined in
(18)-(19). According to the proof of the first part, as long as $z^{0}\not\in
Z$, $\\{z^{k}\\}_{k=0}^{\infty}$ generated by (PG2) does not converge to
$\bar{z}$ associated with any KKT multiplier $\bar{\lambda}/2\in M$. That is,
the convergence point must be a global minimizer. We complete the proof by
noting that the measure of the set $Z$ (30) is zero.

###  3.3 Detailed algorithm and local convergence rate

To globally solve (TRS), we first employ (PG2) to solve (D′), and then recover
the global minimizer of (TRS) according to Theorem 3.2. For completeness, we
summarize the new one-stage single-start algorithm in Algorithm 1.

Algorithm 1 Framework of globally solving (TRS).

0: The input data of (TRS): $n,H,c$; the step size: $\eta\in(0,2/\|H\|_{2})$.

0: Approximation of the global minimizer of (TRS): $x^{*}$.

1: Initialize $(x^{0},y^{0})\in B_{2n}$ and the iteration number $k=0$.

2: while not converged do

3: $\bar{x}^{k}=x^{k}-\eta(Hx^{k}+c),\ \bar{y}^{k}=y^{k}-\eta(Hy^{k}),\
d^{k}=\sqrt{(\bar{x}^{k})^{T}\bar{x}^{k}+(\bar{y}^{k})^{T}\bar{y}^{k}}$;

4: if $d^{k}>1$ then

5: $x^{k+1}=\frac{\bar{x}^{k}}{d^{k}},~{}y^{k+1}=\frac{\bar{y}^{k}}{d^{k}}$;

6: else

7: $x^{k+1}=\bar{x}^{k},~{}y^{k+1}=\bar{y}^{k}$;

8: end if

9: $k=k+1$;

10: end while

11: Denote by $(\tilde{x},\tilde{y})$ the convergence point of
$\\{(x^{k},y^{k})\\}_{k=0}^{\infty}$.

12: if $\tilde{y}=0$ then

13: Output $x^{*}=\tilde{x}$.

14: else

15: Compute
$\theta=\frac{\sqrt{{(\tilde{x}^{T}\tilde{y})}^{2}-\tilde{y}^{T}\tilde{y}(\tilde{x}^{T}\tilde{x}-1)}-\tilde{x}^{T}\tilde{y}}{\tilde{y}^{T}\tilde{y}}$,
and output $x^{*}=\tilde{x}+\theta\tilde{y}$.

16: end if

######  Remark 3.

Initialized with $y^{0}=0$, Algorithm 1 reduces to (PG).

######  Remark 4.

Comparing with the two-stage algorithm [18, 31] based on the equivalent convex
reformulation (C), Algorithm 1 can be regarded as a hybrid of power method and
(PG). The iteration on the artificial variable $y^{k}$ (after normalizing)
corresponds to that of the power method for finding the largest dominant
eigenvalue of $I-\eta H$. In fact, when $\lambda_{1}\leq 0$, the largest
dominant eigenvalue of $I-\eta H$ is $1-\eta\lambda_{1}$, since for any
eigenvalue of $H$, $\lambda_{i}$, it holds that
$\lambda_{1}\leq\lambda_{i}\leq L$ and hence

$-1\leq 1-\eta\lambda_{i}\leq 1-\eta\lambda_{1}~{}{\rm
and}~{}1-\eta\lambda_{1}\geq 1$

for $\eta\in(0,2/L]$. Therefore, in case of $\lambda_{1}\leq 0$, the sequence
$\\{y^{k}/\|y^{k}\|\\}_{k=0}^{\infty}$ converges to $v_{1}$, the unit-
eigenvector of $H$ corresponding to $\lambda_{1}$.

With Lemma 2.2, we can establish the local convergence rate of (PG2) for
solving (D′). To this end, we need the following result.

######  Lemma 3.9.

If the “ill case” of (TRS) holds, so does (D′) and vise versa.

######  Proof 3.10.

According to Table 1, the “ill case” of (TRS) holds if and only if

(31) $\lambda_{1}\leq 0,\ c\in{\rm Range(H-\lambda_{1}I)}\ {\rm\ and\
}\|{(H-\lambda_{1}I)}^{\dagger}c\|=1.$

Note that $\lambda_{1}=\lambda_{\min}(H)$. By the definition of $A$ and $a$
(12), we have $\lambda_{\min}(A)=\lambda_{1}$, and then $a\in{\rm
Range(A-\lambda_{1}I)}$ if and only if $c\in{\rm Range(H-\lambda_{1}I)}$.
Moreover, we have

$(A-\lambda_{1}I)^{\dagger}a=\left[\begin{array}[]{c}(H-\lambda_{1}I)^{\dagger}c\\\
0\end{array}\right],$

and hence
$\|{(A-\lambda_{1}I)}^{\dagger}a\|=\|{(H-\lambda_{1}I)}^{\dagger}c\|$. In sum,
we obtain

(32) $\lambda_{1}\leq 0,\ a\in{\rm Range}(A-\lambda_{\min}(A)I),{\rm\ and\
}\|{(A-\lambda_{\min}(A)I)}^{\dagger}a\|=1.$

Then the “ill case” of (D′) holds. The reverse part is similarly proved.

By Theorem 3.7, Lemmas 2.2 and 3.9, we have the following result.

######  Corollary 3.11.

Initialized with a point uniformly and randomly selected from $B_{2n}$, the
sequence generated by Algorithm 1 converges to a correct point (from which one
can construct the global minimizer of (TRS)) with probability one. The local
convergence rate is linear for the “well case” and sublinear for the “ill
case”.

######  Remark 5.

In comparison with Corollary 3.11, the local convergence rate of the second
run of double-start (PG) presented in [6] could be sublinear even in the “easy
case”, see Example 2.3.

######  Remark 6.

Suppose $H$ has $p$ nonzero entries. The worst-case computational costs of
(PG) and our Algorithm 1 in each iteration are $2p+5n$ and $4p+9n$,
respectively. Therefore, compared with double-start (PG), Algorithm 1 still
has a slight benefit in view of complexity per iteration as
$4p+9n<2\times(2p+5n).$ The reason is that the objective function in (D′) has
no linear term with respect to the artificial variable $y$.

##  4 Globally solving (TRSe)

In this section, we first present the generalized projected gradient method
for globally solving (TRSe) and then suggest a potentially more efficient
approach by reformulating (TRSe) as (TRS).

###  4.1 Generalized projected gradient

We begin with a general nonconvex optimization problem with a single
constraint:

(33) $\min\\{h(x):~{}x\in Q=\\{x\in{\mathbb{R}}^{n}:~{}g(x)=0\\}\\},$

where $h,g:{\mathbb{R}}^{n}\rightarrow{\mathbb{R}}$ are continuously
differentiable, $\nabla h$ is Lipschitz continuous on $Q$ with Lipschitz
constant $L$. Assume that $Q$ is compact and $Q\cap\\{x:\nabla
g(x)=0\\}=\emptyset$ so that LICQ holds for (33).

The generalized projected gradient reads as

(GPG) $x^{k+1}\in{\rm argmin}\\{\|x-x^{k}\|^{2}:~{}x\in
P_{Q}(x^{k}-\eta_{e}\nabla h(x^{k}))\\},$

where $\eta_{e}$ is the step size.

######  Proposition 4.1.

Let $\\{x^{k}\\}_{k=0}^{\infty}$ be the sequence generated by (GPG) with
$x^{0}\in Q$ and constant step size $\eta_{e}\in(0,1/L]$. Then we have the
following results.

  * (i)

For all $k$, it holds that

$\displaystyle
h(x^{k+1})-h(x^{k})\leq\frac{1}{\eta_{e}}\left({\|x^{k+1}-s^{k}\|}^{2}-{\|x^{k}-s^{k}\|}^{2}\right)\leq
0,$

where $s^{k}=x^{k}-\eta_{e}\nabla h(x^{k})$.

  * (ii)

Any accumulation point of $\\{x^{k}\\}_{k=0}^{\infty}$ is a stationary point
of (33).

######  Proof 4.2.

(i) Since $\nabla h$ is $L$-Lipschitz continuous and $\eta_{e}\in(0,1/L]$, we
have

$\displaystyle h(x^{k+1})-h(x^{k})$ $\displaystyle\leq$ $\displaystyle(\nabla
h(x^{k}))^{T}(x^{k+1}-x^{k})+\frac{L}{2}{\|x^{k+1}-x^{k}\|}^{2}$
$\displaystyle\leq$
$\displaystyle\frac{1}{\eta_{e}}(x^{k}-s^{k})^{T}(x^{k+1}-x^{k})+\frac{1}{2\eta_{e}}{\|x^{k+1}-x^{k}\|}^{2}$
$\displaystyle=$
$\displaystyle\frac{1}{2\eta_{e}}\left({\|x^{k+1}-s^{k}\|}^{2}-{\|x^{k}-s^{k}\|}^{2}\right)$
$\displaystyle\leq$ $\displaystyle 0,$

where the last inequality follows from the selection of $x^{k+1}$ in (GPG).

(ii) Since $Q$ is compact, $\\{x^{k}\\}_{k=0}^{\infty}\subseteq Q$ has an
accumulation point. Suppose that the subsequence $\\{x^{m_{k}}\\}$ converges
to $\bar{x}$. Then $\\{s^{m_{k}}\\}$ converges to
$\bar{s}:=\bar{x}-\eta_{e}\nabla h(\bar{x})$ and
$h(x^{m_{k+1}})-h(x^{m_{k}})\rightarrow 0$. By (i), $h(x^{k})$ is non-
increasing with $k$. Thus, $h(x^{k+1})-h(x^{k})\rightarrow 0$ as
$k\rightarrow\infty$. Then it follows from (i) that

(34) ${\|x^{k+1}-s^{k}\|}^{2}-{\|x^{k}-s^{k}\|}^{2}\rightarrow 0,~{}{\rm
as}~{}k\rightarrow\infty.$

Since $Q$ is compact, it holds that

(35)
${\|x^{k+1}-s^{k}\|}^{2}={\|P_{Q}(s^{k})-s^{k}\|}^{2}\rightarrow{\|P_{Q}(\bar{s})-\bar{s}\|}^{2},~{}{\rm
as}~{}k\rightarrow\infty.$

According to ${\rm lim}_{k\rightarrow+\infty}x^{m_{k}}=\bar{x},\ {\rm
lim}_{k\rightarrow+\infty}s^{m_{k}}=\bar{s}$ and (34)-(35), we have

${\|\bar{x}-\bar{s}\|}^{2}={\|P_{Q}(\bar{s})-\bar{s}\|}^{2},$

and then it holds that $\bar{x}\in P_{Q}(\bar{s})=P_{Q}(\bar{x}-\eta_{e}\nabla
h(\bar{x}))$. That is,

(36) $\bar{x}\in{\rm argmin}\\{\|x-(\bar{x}-\eta_{e}\nabla
h(\bar{x}))\|^{2}:~{}g(x)=0\\}.$

By the KKT condition of (36), there exists $\lambda\in{\mathbb{R}}$ such that
$\nabla h(\bar{x})+\lambda/\eta_{e}\nabla g(\bar{x})=0$. Consequently,
$\bar{x}$ is a stationary point of (33).

###  4.2 Solving (TRSe) by (GPG)

Before solving (TRSe), we first present the following lifted reformulation of
(TRSe) similar to (TRSe):

(De) $\min\\{f(z)=\frac{1}{2}z^{T}Az+a^{T}z:\,z\in\partial B_{2n}\\},$

where $A$ and $a$ are defined in (12). Similar to Proposition 3.4, (De) has
the nice property that any second-order stationary point is a global
minimizer.

######  Remark 7.

Our reformulation (De) is new. Recently, Boumal et al. [7] proposed the
following rank-two SDP reformulation for (TRSe) based on Burer-Monteiro
decomposition [8]:

(37) $\min_{Y_{1}\in{\mathbb{R}}^{n\times 2},y_{2}\in{\mathbb{R}}^{2}}\\{{\rm
tr}(CYY^{T}):\,{\rm
tr}(Y_{1}Y_{1}^{T})=1,\,{\|y_{2}\|}^{2}=1,\,Y^{T}=[Y_{1}^{T}~{}y_{2}]\\}.$

It can be regarded as a heavy homogenized version of our reformulation (De)
with more variables and constraints.

Motivated by (PG2), we employ (PGe) to solve (TRSe) and obtain the iterative
formlula

(PGe2) $z^{k+1}=\frac{z^{k}-\eta_{e}\nabla f(z^{k})}{\|z^{k}-\eta_{e}\nabla
f(z^{k})\|}.$

Note that (PGe2) is well-defined, if it holds that $z^{k}-\eta_{e}\nabla
f(z^{k})\neq 0$ for all $k$. Suppose that there is a positive integer $K$ such
that $z^{K}-\eta_{e}\nabla f(z^{K})=0$, we can stop the iteration as
$(z^{K},-1/(2\eta_{e}))$ is already a KKT point of (De). As an extension of
Lemma 3.6, we can establish the convergence result.

######  Lemma 4.3.

Let the sequence $\\{z^{k}\\}_{k\geq 0}$ be generated by (PGe2) for solving
(De) with $z^{0}\in B_{2n}$ and constant step size $\eta_{e}\in(0,1/L]$. Then
either there is a positive integer $K$ such that $z^{K}$ is a stationary point
or $\\{z^{k}\\}_{k=0}^{\infty}$ converges to a stationary point of (De).

######  Proof 4.4.

Define $s^{k}=z^{k}-\eta_{e}\nabla f(z^{k})$ for $k=0,\dots,+\infty$. As shown
above, if there is a positive integer $K$ such that $s^{K}=0$, then $z^{K}$ is
already a stationary point of (De). Now we assume $s^{k}\neq 0$ for all $k\geq
0$.

Suppose that $\\{z^{k}\\}_{k=0}^{\infty}$ has two different accumulation
points, say $\bar{z}$ and $\tilde{z}$. By Proposition 4.1 (ii), both $\bar{z}$
and $\tilde{z}$ are stationary points. Let $\bar{\mu}/2$ and $\tilde{\mu}/2$
be the KKT multipliers corresponding to $\bar{z}$ and $\tilde{z}$,
respectively. According to Proposition 4.1 (i),
$\\{f(z^{k})\\}_{k=0}^{\infty}$ is non-increasing. Then it holds that
$f(\bar{z})=f(\tilde{z})$. As $\bar{z}\neq\tilde{z}$, according to [13,
Theorem 1] or [30, Remark 3.1], we have $\bar{\mu}=\tilde{\mu}$. For
simplicity, we use $\mu$ to represent $\bar{\mu}$ and $\tilde{\mu}$. We first
write down the KKT condition:

(38) $(A+\mu I)\bar{z}+a=(A+\mu I)\tilde{z}+a=0,\
\bar{z}^{T}\bar{z}=\tilde{z}^{T}\tilde{z}=1.$

Denote $\bar{z}=(\bar{x},\bar{y})$ and $\tilde{z}=(\tilde{x},\tilde{y})$.
Based on the eigenvalue decomposition $A=U\Lambda U^{T}$, (38) is equivalent
to

(39) $(\Lambda+\mu I)U^{T}\bar{z}+U^{T}a=(\Lambda+\mu
I)U^{T}\tilde{z}+U^{T}a=0.$

Let $I_{0}=\\{i:~{}\Lambda_{ii}+\mu=0\\}$. By (39), it holds that

(40)
$(U^{T}\bar{z})_{i}=(U^{T}\tilde{z})_{i}=-(U^{T}a)_{i}/(\Lambda_{ii}+\mu){\
\rm for\ all\ }i\not\in I_{0}.$

We obtain that $\bar{z}=\tilde{z}$ if $I_{0}=\emptyset$. Below we consider
$I_{0}\neq\emptyset$. It follows from (39) that

$(U^{T}a)_{i}=0{\ \rm for\ all\ }i\in I_{0}.$

Then the iterative scheme of $z^{k}$ reduces to

$(U^{T}z^{k+1})_{i}=\frac{(U^{T}z^{k})_{i}-\eta_{e}\Lambda_{ii}{(U^{T}z^{k})}_{i}}{\|s^{k}\|}=\frac{(1+\eta_{e}\mu){(U^{T}z^{k})}_{i}}{\|s^{k}\|}{\
\rm for\ all\ }i\in I_{0},$

which implies that

(41)
$(U^{T}z^{k})_{i}=\frac{{(1+\eta_{e}\mu)}^{k}}{\prod\limits_{j=0}^{k}\|s^{j}\|}{(U^{T}z^{0})}_{i}{\
\rm for\ all\ }i\in I_{0}{\rm\ and\ }k=0,\cdots,+\infty.$

Since $\Lambda_{ii}+\mu=0$, $\mu\geq-L$ holds. Then, for any
$\eta_{e}\in(0,1/L]$, we have

$1+\eta_{e}\mu\geq 0.$

Therefore, there are two scalars $\alpha,\beta\geq 0$ such that

(42)
$(U^{T}\bar{z})_{i}=\alpha(U^{T}z^{0})_{i},~{}(U^{T}\tilde{z})_{i}=\beta(U^{T}z^{0})_{i}{\
\rm for\ all\ }i\in I_{0}.$

It follows from the facts
$\|U^{T}\bar{z}\|=\|\bar{z}\|=1=\|\tilde{z}\|=\|U^{T}\tilde{z}\|$ and (40)
that

(43) $\sum_{i\in I_{0}}(U^{T}\bar{z})_{i}^{2}=\sum_{i\in
I_{0}}(U^{T}\tilde{z})_{i}^{2}.$

Substituting (42) into (43) yields that either $\sum_{i\in
I_{0}}(U^{T}z^{0})_{i}^{2}=0$ or $\alpha^{2}=\beta^{2}$ holds. In the former
case, $(U^{T}z^{0})_{i}=0$ and hence
$(U^{T}\bar{z})_{i}=(U^{T}\tilde{z})_{i}=0$ holds for all $i\in I_{0}$ by
(41). In the latter case, we have $\alpha=\beta$ since both are nonnegative.
In sum, we always have

(44) $(U^{T}\bar{z})_{i}=(U^{T}\tilde{z})_{i}~{}{\ \rm for\ all\ }i\in I_{0}.$

Combining (40) with (44) yields the contradiction $\bar{z}=\tilde{z}$.

Similar to Theorem 3.7, we establish the following result.

######  Theorem 4.5.

Initialized with a point uniformly and randomly generated from $\partial
B_{2n}$, the sequence generated by (PGe2) with step size $\eta_{e}\in(0,1/L]$
converges to the global minimizer of (De) with probability one.

######  Proof 4.6.

If $\eta_{e}=1/L$ and $A=L\cdot I$, then by (PGe2),

$z^{1}=\frac{z^{0}-\frac{1}{L}(Lz^{0}+a)}{\|z^{0}-\frac{1}{L}(Lz^{0}+a)\|}=-\frac{a}{\|a\|}.$

By Cauchy-Schwartz inequality, we have

(45) $v\eqref{eq:TRS_e}=\min\left\\{\frac{L}{2}+a^{T}x:\,x\in\partial
B_{n}\right\\}=\frac{L}{2}-\|a\|_{2}=f(z^{1}).$

That is, the global minimizer is obtained after one step. In the following, it
is sufficient to consider the case that either $\eta_{e}<1/L$ or $A\neq L\cdot
I$.

Setting the same $v_{\bar{\lambda}}$ as that in the proof of Theorem 3.7, we
obtain a relation similar to (25) with $\eta$ being replaced by $\eta_{e}$.
Moreover, we have

(46)
$1-\eta_{e}\tilde{\lambda}_{1}+\eta_{e}\bar{\lambda}=1-\eta_{e}\lambda_{1}\geq
1-\eta_{e}L\geq 0.$

In case of $A\neq L\cdot I$, it holds that $\lambda_{1}<L$. So we have either
$\lambda_{1}<L$ or $\eta_{e}<1/L$. It implies that at least one of the two
inequalities in (46) holds strictly. Therefore, according to (25),
$v_{\bar{\lambda}}^{T}z^{k}\neq 0$ and the sign of
$v_{\bar{\lambda}}^{T}z^{k}$ remains unchanged for all $k>0$. Moreover, (27)
holds true if $\eta$ is replaced by $\eta_{e}$. The remaining part of the
proof is the same as that of Theorem 3.7.

######  Remark 8.

None of the proofs of Proposition 4.1, Lemma 4.3 and Theorem 4.5 holds true if
we set $\eta_{e}>1/L$.

######  Remark 9.

In [3, Example 1, Theorem 2], (PGe) is proposed for solving unit-sphere
constrained optimization problem, where the Lez̆anski-Polyak-Lojasiewicz
condition on the sphere is assumed to guarantee the convergence to the global
minimizer. However, this assumption is too restrictive for (TRSe).

######  Remark 10.

Jain and Kar claimed in [19, Theorem 3.3] that the sequence generated by (GPG)
converges to the global minimizer, under the conditions of $\alpha$-restricted
strong smoothness and $\beta$-restricted strong convexity

$\frac{\alpha}{2}{\|x-y\|}^{2}\leq q(x)-q(y)-\langle\nabla
q(y),x-y\rangle\leq\frac{\beta}{2}{\|x-y\|}^{2}$

with $\beta/\alpha<2$ for the objective function $q(\cdot)$ with the constant
step size $\eta_{e}=1/\beta$. We point out that this claim is incorrect, as
the convergence point may be a local non-global minimizer. The following is a
counterexample.

######  Example 4.7.

Consider the instance of (TRSe) in ${\mathbb{R}}^{2}$:

(47)
$\begin{array}[]{cl}\min\\{\frac{27}{2}x_{1}^{2}+\frac{53}{2}x_{2}^{2}-4x_{1}+9x_{2}:\,x\in\partial
B_{2}\\}.\end{array}$

One can verify that the $\alpha$-restricted strong smoothness and
$\beta$-restricted strong convexity with $\beta/\alpha<2$ holds with
$\alpha=27$ and $\beta=53$. According to Example 1.1 of [32], Problem (47) has
both global and local non-global minimizers. Either could be a convergence
point of (GPG).

######  Remark 11.

Lee et al. [21] proved that (RG) almost always avoid strict saddle point of
(TRSe) by regarding it as an optimization problem on the manifold. The related
step size is corrected in [37]. Since (TRSe) could have a local non-global
minimizer (see Example 4.7), (RG) cannot solve (TRSe) globally with
probability $1$.

###  4.3 (TRS)-reformulation of (TRSe)

According to (45), (TRSe) is trivial to solve if $H$ is a scalar matrix.
Throughout this subsection, we only consider nontrivial (TRSe) where $H$ is
not a scalar matrix. We start with a technical lemma.

######  Lemma 4.8.

Let $\tau={\rm tr}(H)/n$. If $H$ is not a scalar matrix, then $H-\tau
I\not\succeq 0$ and

(48) $\|H-\tau I\|_{2}<2\|H\|_{2}.$

######  Proof 4.9.

Let $\lambda_{1}\leq\cdots\leq\lambda_{n}$ be eigenvalues of $H$. As $H$ is
not a scalar matrix, it holds that $\lambda_{1}<\lambda_{n}$. Then, we have

$\tau=\frac{1}{n}{\rm
tr}(H)=\frac{1}{n}\sum_{i=1}^{n}\lambda_{i}>\lambda_{1}.$

It follows that $H-\tau I\not\succeq 0$. Moreover, one can verify that

$\|H-\tau
I\|_{2}\leq\|H\|_{2}+\tau=\|H\|_{2}+\frac{1}{n}\sum_{i=1}^{n}\lambda_{i}<\|H\|_{2}+\lambda_{n}\leq
2\|H\|_{2}.$

######  Theorem 4.10.

(TRSe) has the same global minimizer as the following (TRS):

(49) $\min\left\\{\frac{1}{2}x^{T}(H-\tau I)x+c^{T}x:\,x\in B_{n}\right\\},$

where $\tau={\rm tr}(H)/n$.

######  Proof 4.11.

According to Lemma 4.8, $H-\tau I\not\succeq 0$. Then any local minimizer of
(49), denoted by $x^{*}$, cannot be an interior point of $B_{n}$, i.e.,
$(x^{*})^{T}x^{*}=1$ must hold. It completes the proof of the equivalence.

Based on Theorem 4.10, (TRSe) can be solved by directly employing Algorithm 1
to (49). Note that the supremum of the step size is $\hat{\eta}=2/\hat{L}$,
where $\hat{L}=\|H-\tau I\|_{2}$. According to Lemma 4.8, we have

$\eta_{e}\leq\frac{1}{\|H\|_{2}}<\frac{2}{\hat{L}}=\hat{\eta}.$

Thus, the benefit of this (TRS)-reformulation approach is that the step size
could be larger than that of (PGe). In particular, when $H$ is positive
semidefinite (for example, the least square problem over a sphere [13]), we
have

$\eta_{e}\leq\frac{1}{\|H\|_{2}}<\frac{1}{\hat{L}}=\frac{\hat{\eta}}{2},$

that is, the step size of Algorithm 1 could be twice that of (PGe).

##  5 Conclusion

We show that the sequence generated by the classical projected gradient method
for solving a cheap but novel reformulation of the trust region subproblem
(TRS) almost always converges to its global minimizer. The local convergence
rate is at least linear for the “easy case”. As an extension, we establish and
analyze the generalized projected gradient method for globally solving the
similarly lifted equality-constrained (TRS), denoted by (TRSe). However, an
alternative approach by globally solving a new nonconvex (TRS)-reformulation
of (TRSe) via projected gradient method seems to be better in the sense that
it allows a larger step size. Some problems remain open, including the local
convergence rate of the generalized projected gradient method and the
acceleration version of the projected gradient algorithm for solving our new
reformulations of (TRS) and (TRSe).

## References

  * [1] P.-A. Absil, R. Mahony, and R. Sepulchre, Optimization Algorithms on Matrix Manifolds, Princeton University Press, 2008.
  * [2] S. Adachi, S. Iwata, Y. Nakatsukasa, and A. Takeda, Solving the trust-region subproblem by a generalized eigenvalue problem, SIAM Journal on Optimization, 27 (2017), pp. 269–291.
  * [3] M. V. Balashov, B. T. Polyak, and A. A. Tremba, Gradient projection and conditional gradient methods for constrained nonconvex minimization, Numerical Functional Analysis and Optimization, 41 (2020), pp. 822–849.
  * [4] A. Beck, First-Order Methods in Optimization, MOS-SIAM Ser. Optim. 25, SIAM, Philadelphia, PA, 2017.
  * [5] A. Beck and Y. C. Eldar, Strong duality in nonconvex quadratic optimization with two quadratic constraints, SIAM Journal on Optimization, 17 (2006), pp. 844–860.
  * [6] A. Beck and Y. Vaisbourd, Globally solving the trust region subproblem using simple first-order methods, SIAM Journal on Optimization, 28 (2018), pp. 1951–1967.
  * [7] N. Boumal, V. Voroninski, and A. S. Bandeira, Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs, Communications on Pure and Applied Mathematics, 73 (2019), pp. 581–608.
  * [8] S. Burer and R. Monteiro, A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization, Mathematical Programming, 95 (2003), pp. 329–357.
  * [9] Y. Carmon and J. C. Duchi, Analysis of Krylov subspace solutions of regularized non-convex quadratic problems, in Advances in Neural Information Processing Systems, S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, eds., vol. 31, Curran Associates, Inc., 2018.
  * [10] A. R. Conn, N. I. M. Gould, and P. L. Toint, Trust Region Methods, Society for Industrial and Applied Mathematics, Philadelphia, 2000.
  * [11] R. Fletcher, Practical Methods of Optimization, John Wiley, New York, second ed., 1987.
  * [12] O. E. Flippo and B. Jansen, Duality and sensitivity in nonconvex quadratic optimization over an ellipsoid, European Journal of Operational Research, 94 (1996), pp. 167–178.
  * [13] W. Gander, Least squares with a quadratic constraint, Numerische Mathematik, 36 (1980), pp. 291–307.
  * [14] D. M. Gay, Computing optimal locally constrained steps, SIAM Journal on Scientific and Statistical Computing, 2 (1981), pp. 186–197.
  * [15] N. I. M. Gould, S. Lucidi, M. Roma, and P. L. Toint, Solving the trust-region subproblem using the Lanczos method, SIAM Journal on Optimization, 9 (1999), pp. 504–525.
  * [16] W. W. Hager, Minimizing a quadratic over a sphere, SIAM Journal on Optimization, 12 (2001), pp. 188–208.
  * [17] E. Hazan and T. Koren, A linear-time algorithm for trust region problems, Mathematical Programming, 158 (2016), pp. 363–381.
  * [18] N. Ho-Nguyen and F. Kılınç-Karzan, A second-order cone based approach for solving the trust-region subproblem and its variants, SIAM Journal on Optimization, 27 (2017), pp. 1485–1512.
  * [19] P. Jain and P. Kar, Non-convex optimization for machine learning, 10 (2017), pp. 142–363.
  * [20] R. Jiang and X. Li, Hölderian error bounds and Kurdyka-Lojasiewicz inequality for the trust region subproblem, Mathematics of Operations Research, (2022).  Published online, https://doi.org/10.1287/moor.2021.1243.
  * [21] J. D. Lee, I. Panageas, G. Piliouras, M. Simchowitz, M. I. Jordan, and B. Recht, First-order methods almost always avoid strict saddle points, Mathematical Programming, 176 (2019), pp. 311–337.
  * [22] D. G. Luenberger and Y. Ye, Linear and Nonlinear Programming, Springer, New York, third ed., 2008.
  * [23] J. M. Martínez, Local minimizers of quadratic functions on Euclidean balls and spheres, SIAM Journal on Optimization, 4 (1994), pp. 159–176.
  * [24] J. J. Moré and D. C. Sorensen, Computing a trust region step, SIAM Journal on Scientific and Statistical Computing, 4 (1983), pp. 553–572.
  * [25] A. H. Phan, M. Yamagishi, D. Mandic, and A. Cichocki, Quadratic programming over ellipsoids with applications to constrained linear regression and tensor decomposition., Neural Computing & Applications, (2020), pp. 7097–7120.
  * [26] I. Pólik and T. Terlaky, A survey of the S-lemma, SIAM Review, 49 (2007), pp. 371–418.
  * [27] D. C. Sorensen, Newton’s method with a model trust region modification, SIAM Journal on Numerical Analysis, 19 (1982), pp. 409–426.
  * [28] D. C. Sorensen, Minimization of a large-scale quadratic function subject to a spherical constraint, SIAM Journal on Optimization, 7 (1997), pp. 141–161.
  * [29] P. D. Tao and L. T. H. An, A D.C. optimization algorithm for solving the trust-region subproblem, SIAM Journal on Optimization, 8 (1998), pp. 476–505.
  * [30] J. Wang, M. Song, and Y. Xia, Trust-region and $p$-regularized subproblems: local nonglobal minimum is the second smallest objective function value among all first-order stationary points.  arXiv:2108.07963, 2022.
  * [31] J. Wang and Y. Xia, A linear-time algorithm for the trust region subproblem based on hidden convexity, Optimization Letters, 11 (2017), pp. 1639–1646.
  * [32] J. Wang and Y. Xia, Closing the gap between necessary and sufficient conditions for local nonglobal minimizer of trust region subproblem, SIAM Journal on Optimization, 30 (2020), pp. 1980–1995.
  * [33] Y. x. Yuan, Recent advances in trust region algorithms, Mathematical Programming, 151 (2015), pp. 249–281.
  * [34] Y. Xia, A survey of hidden convex optimization., Journal of the Operations Research Society of China, (2020), pp. 1–28.
  * [35] Y. Ye, A new complexity result on minimization of a quadratic function with a sphere constraint, in Recent Advances in Global Optimization, Princeton University Press, USA, 1992, pp. 19–31.
  * [36] L.-H. Zhang, C. Shen, and R.-C. Li, On the generalized Lanczos trust-region method, SIAM Journal on Optimization, 27 (2017), pp. 2110–2142.
  * [37] J. Zheng and Y. Xia, Comment on “first-order methods almost always avoid strict saddle points”.  arXiv:2204.00521, 2022.