M. Song et al.

Local Optimality for Hidden Convex Optimization

Local Optimality Conditions for a Class of Hidden Convex Optimization

Mengmeng Song1<EMAIL_ADDRESS> Yong Xia1<EMAIL_ADDRESS>Hongying Liu1, Corresponding Author<EMAIL_ADDRESS>
$1$, School of Mathematical Sciences, Beihang University, Beijing, 100191,
People’s Republic of China, Hidden convex optimization is such a class of
nonconvex optimization problems that can be globally solved in polynomial time
via equivalent convex programming reformulations. In this paper, we focus on
checking local optimality in hidden convex optimization. We first introduce a
class of hidden convex optimization problems by jointing the classical
nonconvex trust-region subproblem (TRS) with convex optimization (CO), and
then present a comprehensive study on local optimality conditions. In order to
guarantee the existence of a necessary and sufficient condition for local
optimality, we need more restrictive assumptions. To our surprise, while (TRS)
has at most one local non-global minimizer and (CO) has no local non-global
minimizer, their joint problem could have more than one local non-global
minimizer.

Optimality condition, Hidden convexity, Local optimality, Trust region
subproblem 90C26, 90C46, 90C30

##  1 Introduction

As a fundamental topic in operations research, convex optimization has a rapid
development in the last two decades [2, 18], thanks to its popular
applications in machine learning [3]. One of the key to the algorithmic
success in convex optimization is that any local minimizer is in fact a global
one. The situation is different in nonconvex optimization, which is in general
NP-hard, and often has many local non-global minimizers. Local optimal
solutions play a great role in globally solving structured nonconvex
optimization problem [1]. However, as shown in [17, 20], checking local
optimality of a nonconvex quadratic program is already NP-hard. That is, local
optimization is as difficult as global optimization. On the other hand, we
notice that not all nonconvex optimization problems are difficult to globally
solve. For example, hidden convex optimization admits an equivalent
polynomial-solvable convex programming reformulation, see [25] for a recent
survey. Accordingly, we ask

###### Question 1.1

Can we go far beyond the standard local optimality conditions for hidden
convex optimization?

A typical hidden convex optimization is the following trust region subproblem
(TRS):

$\begin{array}[]{cl}\min\limits_{x\in{\mathbb{R}}^{n}}\\{\tfrac{1}{2}x^{T}Hx+c^{T}x:x^{T}x\leq\Delta\\},\end{array}$
(TRS)

where $H=H^{T}\in{\mathbb{R}}^{n\times n},c\in{\mathbb{R}}^{n}$ and
$\Delta>0$. (TRS) plays a key role in trust region methods for solving
nonlinear programming problems [5, 28]. In the early 1980s, Gay [9], Sorensen
[21], Moré and Sorensen [16] have established necessary and sufficient
optimality condition for the global minimizer of (TRS). Observing this, Ye
[27] showed that (TRS) can be globally solved in polynomial time. In 1994,
Martínez [15] proved that (TRS) has at most one local non-global minimizer,
and then established a necessary optimality condition and a sufficient one for
the local non-global minimizer of (TRS). Observing the gap between necessary
and sufficient conditions, Tao and An [22] pointed out that “For the trust-
region subproblem, it is interesting to note the following paradox: checking a
global solution is easier than checking a local nonglobal one.” It seems that
the answer to Question 1.1 is negative on (TRS). In 2020, Wang and Xia [23]
broke Tao and An’s paradox by proving that Martínez’s sufficient optimality
condition [15] for (TRS) is also necessary. In the same paper, it is also
shown that the local non-global minimizer can be found or proved to do not
exist in polynomial time. Thus, Wang and Xia’s result gives a positive answer
to Question 1.1 on (TRS).

Towards answering Question 1.1, we introduce in this paper a class of
nonconvex optimization, which joints nonconvex trust-region subproblem with
convex optimization:

$\begin{array}[]{cl}\min\limits_{x\in{\mathbb{R}}^{n},y\in{\mathbb{R}}^{m}}&\tfrac{1}{2}x^{T}Hx+c^{T}x+f_{0}(y)\\\
{\rm s.t.}&x^{T}x+f_{1}(y)\leq 0\\\ &\ \ \ \ \ \ \ \ \,f_{j}(y)\leq
0,j=2,\cdots,k,\end{array}$ (TRS-C)

where $H=H^{T}\in{\mathbb{R}}^{n\times
n},c\in{\mathbb{R}}^{n},k\in\mathbb{Z}^{+}$, and
$f_{j}(\cdot)~{}(j=0,1,\cdots,k)$ are convex and twice continuously
differentiable. Throughout this paper, we assume $H\nsucceq 0$, otherwise
(TRS-C) is a convex optimization problem. In particular, setting
$m=1,k=1,f_{0}\equiv 0,f_{1}\equiv-\Delta$, (TRS-C) reduces to (TRS).

As we have mentioned above, (TRS) has at most one local non-global minimizer,
and convex optimization problem has no local non-global minimizer. Notice that
(TRS-C) joints (TRS) with convex optimization. So, it is natural to expect a
positive answer to the following question:

###### Question 1.2

Does (TRS-C) have at most one local non-global minimizer?

We may consider another special case of (TRS-C) by setting
$m=1,k=1,f_{0}(y)=\tfrac{\sigma}{p}y^{\tfrac{p}{2}},f_{1}(y)=-y$, where
$\sigma>0$ and $p>2$ are two parameters:

$\min\limits_{x\in{\mathbb{R}}^{n},y\in{\mathbb{R}}}\\{\tfrac{1}{2}x^{T}Hx+c^{T}x+\tfrac{\sigma}{p}y^{\tfrac{p}{2}}:x^{T}x-y\leq
0\\}.$ (1)

The univariate variable $y$ can be removed by substituting the constraint into
the objection. Then (1) is equivalent to the following unconstrained
optimization

$\min\limits_{x\in{\mathbb{R}}^{n}}\tfrac{1}{2}x^{T}Hx+c^{T}x+\tfrac{\sigma}{p}\|x\|^{p},$
($p$-RS)

which is known as $p-$regularized subproblem [11]. In particular, the cubic
regularization ($p=3$) was first introduced in [12] and then widely applied in
nonlinear programming, see for example, [4, 19, 24]. The other special case of
($p$-RS) with $p=4$ corresponds to the double-well potential optimization [6,
26]. Recently, Hsia et al. [13] established necessary and sufficient
optimality conditions for both global and local minimizers of ($p$-RS) with
any $p>2$. In the same paper, ($p$-RS) is shown to have at most one local non-
global minimizer. Thus, both Question 1.1 and 1.2 have positive answers on
($p$-RS).

In this paper, we give a comprehensive study on (TRS-C). We first reveal its
hidden convexity by establishing necessary and sufficient optimality condition
for global minimizer. It makes sense as (TRS-C) joints a hidden convex with a
convex optimization problem. We then establish necessary and sufficient
optimality conditions for local non-global minimizer, respectively. However,
the gap of two conditions exists for the general case. In order to close this
gap, we need more assumptions. It supports the conjecture that Question 1.1
has no positive answer. For Question 1.2, to our surprise, the answer is
negative. Actually, (TRS-C) may have a finite number of local non-global
minimizers. Only for very special cases including (TRS) and ($p$-RS), (TRS-C)
has at most one local non-global minimizer. Consequently, we conclude that the
existence of many local minimizers is NOT a (or at least not a unique) reason
making global optimization difficult.

The remainder of this paper is organized as follows. Section 2 presents
necessary and sufficient conditions for global minimizers of (TRS-C). Section
3 establishes necessary and sufficient conditions for local non-global
minimizer of (TRS-C), respectively. These conditions are further characterized
by a scalar function for a special case of (TRS-C) with $k=1$ in Section 4. We
consider another special case of (TRS-C) where $f_{1}(y)$ is a linear function
in Section 5. Two instances with more than one local non-global minimizer are
constructed. Then a sufficient condition is presented to guarantee that
(TRS-C) has at most one local non-global minimizer. As an extension of (TRS)
and ($p$-RS), we identify a class of cases of (TRS-C) where local non-global
minimizer enjoys a necessary and sufficient optimality condition. We conclude
the paper in the last section with a few open questions.

_Notations._ For any matrix $P\in{\mathbb{R}}^{n\times n}$, $P^{T}$ and
$\det{(P)}$ denote the transposition and determination of $P$, respectively.
$P\succ(\succeq)0$ denotes that $P$ is positive (semi)definite. Let $I$ stand
for the identity matrix of order $n$. For a vector $x\in{\mathbb{R}}^{n}$,
${\rm Diag}(x)$ returns a diagonal matrix with diagonal elements being
$x_{1},\cdots,x_{n}$. Let $f^{-1}(\cdot)$ represent the inverse of function
$f(\cdot)$, if it exists. $\mathbb{Z}^{+}$ denotes the set of all positive
integers. The eigenvalue decomposition of the symmetric matrix $H$ is given by

$H=V{\rm Diag}(\lambda_{1},\cdots,\lambda_{n})V^{T},$ (2)

where $V=(v_{1},v_{2},\cdots,v_{n})\in{\mathbb{R}}^{n\times n}$ is orthogonal,
and $\lambda_{i}$ is the $i$-th smallest eigenvalue of $H$.

##  2 Global Optimality Condition

In this section, we present the necessary and sufficient optimality condition
for the global minimizer of (TRS-C), where the Slater condition is assumed.

###### Theorem 2.1

Assume that $(x_{*},y_{*})\in{\mathbb{R}}^{n}\times{\mathbb{R}}^{m}$ is a
global minimizer of (TRS-C) and there exists $\bar{y}$ such that
$f_{j}(\bar{y})<0,~{}j=1,\cdots,k$. There exist $\mu^{*}_{j}\geq 0$
($j=1,\cdots,k$) such that

$\displaystyle(H+\mu^{*}_{1}I)x_{*}+c=0,$ (3) $\displaystyle\nabla
f_{0}(y_{*})+\frac{\mu^{*}_{1}}{2}\nabla
f_{1}(y_{*})+\sum_{j=2}^{k}\mu^{*}_{j}\nabla f_{j}(y_{*})=0,$ (4)
$\displaystyle x_{*}^{T}x_{*}+f_{1}(y_{*})=0,\ \
\mu^{*}_{j}f_{j}(y_{*})=0,~{}j=2,\cdots,k,$ (5) $\displaystyle
H+\mu^{*}_{1}I\succeq 0.$ (6)

_Proof._ Note that $\lambda_{1}<0$ for $H\nsucceq 0$. Since $(x_{*},y_{*})$ is
a global minimizer of (TRS-C), then $x_{*}$ solves

$\min_{x\in{\mathbb{R}}^{n}}\\{\tfrac{1}{2}x^{T}Hx+c^{T}x:~{}x^{T}x\leq-
f_{1}(y_{*})\\}.$ (7)

We conclude that

$x_{*}^{T}x_{*}+f_{1}(y_{*})=0.$ (8)

Otherwise, it follows from $x_{*}^{T}x_{*}+f_{1}(y_{*})<0$ that $H$ is
positive semidefinite by second order necessary optimality, which contradicts
the fact $\lambda_{1}<0$.

Therefore, $(x_{*},y_{*})$ remains a global minimizer of

$\begin{array}[]{cl}\min\limits_{x\in{\mathbb{R}}^{n},y\in{\mathbb{R}}^{m}}&F(x,y):=\tfrac{1}{2}x^{T}Hx+c^{T}x+f_{0}(y)-\frac{\lambda_{1}}{2}(x^{T}x+f_{1}(y))\\\
{\rm s.t.}&x^{T}x+f_{1}(y)=0\\\ &\ \ \ \ \ \ \ \,\ f_{j}(y)\leq
0,~{}j=2,\cdots,k.\end{array}$

Now, consider a convex optimization relaxation of the above problem:

$\begin{array}[]{cl}\min\limits_{x\in{\mathbb{R}}^{n},y\in{\mathbb{R}}^{m}}&F(x,y)=\tfrac{1}{2}x^{T}(H-\lambda_{1}I)x+c^{T}x+f_{0}(y)-\frac{\lambda_{1}}{2}f_{1}(y)\\\
{\rm s.t.}&x^{T}x+f_{1}(y)\leq 0\\\ &\ \ \ \ \ \ \ \ \,f_{j}(y)\leq
0,j=2,\cdots,k.\end{array}$ (9)

Let $(x,y)$ be any feasible solution to (9) with $x^{T}x+f_{1}(y)<0$. Let
$v_{1}$ be an eigenvector of $H$ corresponding to $\lambda_{1}$ (i.e.,
$Hv_{1}=\lambda_{1}v_{1}$) and satisfy $c^{T}v_{1}\leq 0$. Then there is a
$\tau>0$ such that $\bar{x}=x+\tau v_{1}$ satisfies
$\bar{x}^{T}\bar{x}+f_{2}(y)=0$. We can verify that $(\bar{x},y)$ is feasible
to (9), and

$\displaystyle\frac{1}{2}{\bar{x}}^{T}(H-\lambda_{1}I)\bar{x}+c^{T}\bar{x}$
$\displaystyle=$ $\displaystyle\frac{1}{2}x^{T}(H-\lambda_{1}I)x+c^{T}x+\tau
c^{T}v_{1}$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}x^{T}(H-\lambda_{1}I)x+c^{T}x.$

Therefore, $F(\bar{x},y)\leq F(x,y)$. It follows that $(x_{*},y_{*})$ must be
a global minimizer of (9). Notice that (9) is a convex optimization problem
where Slater condition holds by assumption. According to the first order
necessary optimality condition, there exist $\bar{\mu}_{1}\geq 0$ and
$\mu^{*}_{j}\geq 0,j=2,\cdots,k$, which satisfy

$\displaystyle(H+\bar{\mu}_{1}I-\lambda_{1}I)x_{*}=-c,\ \ \nabla
f_{0}(y_{*})+\frac{\bar{\mu}_{1}-\lambda_{1}}{2}\nabla
f_{1}(y_{*})+\sum_{j=2}^{k}\mu^{*}_{j}\nabla f_{j}(y_{*})=0,$ (10)
$\displaystyle\bar{\mu}_{1}(x_{*}^{T}x_{*}+f_{1}(y_{*}))=0,\ \
\mu^{*}_{j}f_{j}(y_{*})=0,j=2,\cdots,k.$ (11)

Define $\mu^{*}_{1}=\bar{\mu}_{1}-\lambda_{1}$. Equations (8), (10) and (11)
imply that $\mu^{*}_{j},j=1,\cdots,k$, satisfy (3), (4) and (5). Since
$H-\lambda_{1}I\succeq 0$ and $\bar{\mu}_{1}\geq 0$, we have
$H+\mu^{*}_{1}I\succeq 0$, i.e., (6) holds true.

###### Remark 2.2

(TRS-C) admits an equivalent convex reformulation (9), which reveals the
hidden convexity of (TRS-C).

Theorem 2.1 establishes a necessary condition for global optimality of
$(x_{*},y_{*})$. The next result shows that it is also a sufficient condition.

###### Theorem 2.3

Let $(x_{*},y_{*})\in{\mathbb{R}}^{n}\times{\mathbb{R}}^{m}$ be a feasible
solution to (TRS-C). If there exist $\mu^{*}_{j}\geq 0,j=1,\cdots,k$,
satisfying (3)-(6). Then $(x_{*},y_{*})$ is a global minimizer of (TRS-C).

_Proof._ Define $\bar{\mu}_{1}=\mu^{*}_{1}+\lambda_{1}$. It follows from
$H+\mu^{*}_{1}I\succeq 0$ that $\bar{\mu}_{1}\geq 0$. Substituting
$\mu^{*}_{1}=\bar{\mu}_{1}-\lambda_{1}$ into (3), (4) and (5) yields (10) and
(11), respectively. That is, $(x_{*},y_{*})$ is a global minimizer of (9).
Therefore, for any feasible solution $(x,y)$ to (TRS-C), we have

$\tfrac{1}{2}x^{T}Hx+c^{T}x+f_{0}(y)\geq F(x,y)\geq
F(x_{*},y_{*})=\tfrac{1}{2}x_{*}^{T}Hx_{*}+c^{T}x_{*}+f_{0}(y_{*}),$

where the first inequality follows from the feasibility of $(x,y)$ and the
fact $\lambda_{1}<0$, the second inequality holds since $(x_{*},y_{*})$ is a
global minimizer of (9), and the equality is implied from (5). Thus,
$(x_{*},y_{*})$ is a global minimizer of (TRS-C).

##  3 Local Non-Global Optimality Conditions: General Case

In this section, we present local non-global optimality conditions for
(TRS-C). In contrast with linear independence constraint qualification (LICQ)
made in general nonlinear programming, we need the following relaxed
constraint qualification throughout this section: Let $(x_{*},y_{*})$ be any
candidate local minimizer of (TRS-C). The gradients $\nabla f_{i}(y_{*})$ for
$i\in\\{j\in\\{1,\cdots,k\\}:~{}f_{j}(y_{*})=0\\}$ are linearly independent.

Applying the classical optimality conditions in nonlinear programming to
(TRS-C) under Assumption 3, we immediately have

###### Lemma 3.1

  1. (a)

Let $(x_{*},y_{*})$ be a local minimizer of (TRS-C). Under Assumption 3, there
exist $\mu^{*}_{j}\geq 0$ ($j=1,\cdots,k$) satisfying (3), (4), and (5).
Moreover,

$\displaystyle\begin{bmatrix}s^{T}&t^{T}\end{bmatrix}$
$\displaystyle\begin{bmatrix}H+\mu^{*}_{1}I&0\\\
0&\nabla^{2}f_{0}(y_{*})+\frac{\mu^{*}_{1}}{2}\nabla^{2}f_{1}(y_{*})+\sum_{j=2}^{k}\mu^{*}_{j}\nabla^{2}f_{j}(y_{*})\\\
\end{bmatrix}\begin{bmatrix}s\\\ t\\\ \end{bmatrix}\geq 0$ (12)

holds for any $(s,t)\in T,$ where

$\displaystyle T=\\{(s,t):$ $\displaystyle~{}2s^{T}x_{*}+t^{T}\nabla
f_{1}(y_{*})=0;$ $\displaystyle~{}t^{T}\nabla
f_{i}(y_{*})=0,~{}i\in\\{j\in\\{2,\cdots,k\\}:f_{j}(y_{*})=0,\mu^{*}_{j}>0\\};$
$\displaystyle~{}t^{T}\nabla f_{i}(y_{*})\leq
0,~{}i\in\\{j\in\\{2,\cdots,k\\}:f_{j}(y_{*})=0,\mu^{*}_{j}=0\\}\\}.$

  2. (b)

Suppose $(x_{*},y_{*})$ is feasible to (TRS-C) and there exist
$\mu^{*}_{j}\geq 0$ ($j=1,\cdots,k$) satisfying (3), (4), (5), and

$\displaystyle\begin{bmatrix}s^{T}&t^{T}\end{bmatrix}\begin{bmatrix}H+\mu^{*}_{1}I&0\\\
0&\nabla^{2}f_{0}(y_{*})+\frac{\mu^{*}_{1}}{2}\nabla^{2}f_{1}(y_{*})+\sum_{j=2}^{k}\mu^{*}_{j}\nabla^{2}f_{j}(y_{*})\\\
\end{bmatrix}\begin{bmatrix}s\\\ t\\\ \end{bmatrix}>0,~{}\forall(s,t)\in
T\setminus\\{0\\}.$

Then $(x_{*},y_{*})$ is a strict local minimizer of (TRS-C).

_Proof._ Firstly, we show that LICQ is true at $(x_{*},y_{*})$ under
Assumption 3. If $x_{*}=0$, as $(0,\nabla f_{i}(y_{*})^{T})$ for
$i\in\\{j\in\\{1,\cdots,k\\}:~{}f_{j}(y_{*})=0\\}$ are linearly independent
according to Assumption 3, LICQ holds; If $x_{*}\neq 0$, $(0,\nabla
f_{i}(y_{*})^{T})$ for $i\in\\{j\in\\{2,\cdots,k\\}:~{}f_{j}(y_{*})=0\\}$
together with $(x_{*}^{T},\nabla f_{1}(y_{*})^{T})$ are linearly independent
according to Assumption 3 and the fact that $x_{*}\neq 0$.

With LICQ holding, the proof except (8) in (5) follows from the classical
optimality conditions in nonlinear programming (see [8], Chapter 9; [7],
Chapter 11). We conclude that (8) hold with the same reason as in Theorem 2.1.

Next, we show that under Assumption 3, for any local non-global minimizer
$(x_{*},y_{*})$, $x_{*}\neq 0$.

###### Theorem 3.2

Suppose $(0,y_{*})$ is a local minimizer of (TRS-C). Under Assumption 3,
$(0,y_{*})$ is a global minimizer of (TRS-C).

_Proof._ According to Lemma 3.1 (a), there exist $\mu^{*}_{j}\geq 0$
($j=1,\cdots,k$) such that (3),(4), and (5) hold. Furthermore, the inequality
(12) holds for any $(s,t)\in T$ in (a) with $x^{*}=0$. Taking $t=0$ and
$x^{*}=0$ into (12) and (a) gives

$s^{T}(H+\mu^{*}_{1}I)s\geq 0,~{}\forall s\in{\mathbb{R}}^{n}.$

Thus, $H+\mu^{*}_{1}I\succeq 0$ and hence $(0,y_{*})$ is a global minimizer of
(TRS-C) due to Theorem 2.

Finally, we present additional necessary conditions of local non-global
minimizer for (TRS-C). To this end, the following key lemma is required.

###### Lemma 3.3

  * (a)

[Lemma 2.8, [21]] If $x_{*}\in{\mathbb{R}}^{n}$ is a global minimizer of
(TRS), there exists $\mu^{*}_{1}\geq\max\\{-\lambda_{1},0\\}$ satisfying (3).

  * (b)

[Lemma 3.2,[15]] If $c$ is orthogonal to some eigenvector associated with
$\lambda_{1}$, there is no local non-global minimizer of (TRS).

  * (c)

[Lemma 3.3,[15]] If $x_{*}$ is a local non-global minimizer of (TRS), (3)
holds with $0\leq\mu^{*}_{1}\in(-\lambda_{2},-\lambda_{1})$ and
$x_{*}^{T}x_{*}-\Delta=0$.

  * (d)

[Proposition 3.5, [14]] At the local non-global minimizer of (TRS), the strict
complementarity condition holds.

###### Theorem 3.4

Let $(x_{*},y_{*})$ be a local non-global minimizer of (TRS-C). Under
Assumption 3, it holds that $\lambda_{1}<\lambda_{2}$, there exist
$\mu^{*}_{j}\geq 0$ ($j=1,\cdots,k$) such that (3), (4) and (5) with
$\max\\{0,-\lambda_{2}\\}<\mu^{*}_{1}<-\lambda_{1}$, and $c$ is not orthogonal
to any eigenvectors associated with $\lambda_{1}$.

_Proof._ According to Lemma 3.1 (a), there exist $\mu^{*}_{j}\geq 0$
($j=1,\cdots,k$) satisfying (3), (4), and (5). Moreover, $x_{*}$ is a local
minimizer of (7), since $(x_{*},y_{*})$ is locally optimal for (TRS-C). By
Theorem 3.2 and the fact that $(x_{*},y_{*})$ be a local non-global minimizer
of (TRS-C), $x_{*}\neq 0$. Then (7) is an instance of (TRS) with
$\Delta=-f_{1}(y_{*})>0$. We claim that $x_{*}$ is a local non-global
minimizer of (7). Suppose this is not true, then $x_{*}$ is a global minimizer
of (7). There exists $\bar{\mu}_{1}\geq-\lambda_{1}$ such that

$(H+\bar{\mu}_{1}I)x_{*}+c=0$ (14)

according to Lemma 3.3 (a). Combining (3), (14) with $x_{*}\neq 0$, we have
$\mu^{*}_{1}=\bar{\mu}_{1}\geq-\lambda_{1}$. Therefore, $(x_{*},y_{*})$ is
globally optimal for (TRS-C) due to Theorem 2.3. It contradicts the fact that
$(x_{*},y_{*})$ is a local non-global minimizer of (TRS-C).

Since $x_{*}^{T}x_{*}+f_{2}(y_{*})=0$ according to Lemma 3.3 (c), we get
$\mu^{*}_{1}>0$ from Lemma 3.3 (d). Then the remaining results to be proved
follow from Lemma 3.3 (b), (c) and the fact that $x_{*}$ is a local non-global
minimizer of (7).

##  4 Local Non-Global Optimality Conditions: Single-Constraint Case

In this section, we study local non-global optimality conditions of the
single-constrained case of (TRS-C):

$\begin{array}[]{cl}\min\limits_{x\in{\mathbb{R}}^{n},y\in{\mathbb{R}}^{m}}&\tfrac{1}{2}x^{T}Hx+c^{T}x+f_{0}(y)\\\
{\rm s.t.}&x^{T}x+f(y)\leq 0,\end{array}$ (15)

where $f_{0}(y),f(y)$ are convex and twice continuously differentiable. Note
that we do not make Assumption 3 in this section.

We first identify a trivial case without local non-global minimizer.

###### Remark 4.1

If $\\{y:f(y)<0\\}=\emptyset$ holds, (15) has no local nonglobal minimizer.

_Proof._ If $(x_{*},y_{*})$ is a local minimizer of (15), we have $f(y_{*})=0$
and $x_{*}=0$, as $\\{y:f(y)<0\\}=\emptyset$ and $f(y_{*})\leq-
x_{*}^{T}x_{*}\leq 0$. Then (15) reduces to the problem

$\min_{f(y)\leq 0}f_{0}(y),$

which is a convex optimization problem. It follows that (15) under the
assumption $\\{y:f(y)<0\\}=\emptyset$ has no local non-global minimizer.

In the remainder of this section, without loss of generality, we assume
$\\{y:f(y)<0\\}\neq\emptyset$.

###### Lemma 4.2

LICQ holds at any local nonglobal minimizer of (15).

_Proof._ Let $(x_{*},y_{*})$ be a local nonglobal minimizer of (15). If
$x_{*}\neq 0$, $(x_{*}^{T},\nabla f(y_{*})^{T})\neq 0$, LICQ holds. It’s
sufficient to consider the case $x_{*}=0$, which implies that $f(y_{*})=0$
since $x_{*}^{T}x_{*}+f(y_{*})=0$. Under the assumption
$\\{y:f(y)<0\\}\neq\emptyset$ and the convexity of $f(y)$, we have $\nabla
f(y_{*})\neq 0$, which guarantees LICQ.

Let $(x_{*},y_{*})$ be a local non-global minimizer of (15). According to
Lemma 4.2 and Theorem 3.2, $x_{*}\neq 0$. Moreover, it follows from Lemma 4.2
and Theorem 3.4 that there is a unique
$\mu^{*}\in(\max\\{0,-\lambda_{2}\\},-\lambda_{1})$ such that

$\displaystyle(H+\mu^{*}I)x_{*}=-c,$ (16) $\displaystyle\nabla
f_{0}(y_{*})+\frac{\mu^{*}}{2}\nabla f(y_{*})=0,$ (17) $\displaystyle
x_{*}^{T}x_{*}+f(y_{*})=0.$ (18)

Define the following scalar function similar to Martínez [15]

$\varphi(\mu)=\|{(H+\mu I)}^{-1}c\|^{2},~{}\mu\in(-\lambda_{2},-\lambda_{1}).$

Using (2), one can verify that

$\varphi(\mu)=\sum_{i=1}^{n}\frac{g_{i}^{2}}{{(\lambda_{i}+\mu)}^{2}},\
\varphi^{\prime}(\mu)=-\sum_{i=1}^{n}\frac{2g_{i}^{2}}{{(\lambda_{i}+\mu)}^{3}},\
\text{and}\
\varphi^{\prime\prime}(\mu)=\sum_{i=1}^{n}\frac{6g_{i}^{2}}{{(\lambda_{i}+\mu)}^{4}}$
(19)

for all $\mu\in(-\lambda_{2},-\lambda_{1})$, where $g=V^{T}c$. If a local non-
global minimizer exists, we must have $g_{1}\neq 0$ and
$\lambda_{1}<\lambda_{2}$ due to Theorem 3.4.

For easy analysis, we introduce the following nonsingular assumption, which
automatically holds if either $f_{0}(y)$ or $f(y)$ is strongly convex. At any
$y\in{\mathbb{R}}^{m}$ with $f(y)<0$,
$\nabla^{2}f_{0}(y)+\frac{\mu_{y}}{2}\nabla^{2}f(y)\succ 0$ for some
$\mu_{y}>0$. Assumption 4 implies the following property.

###### Lemma 4.3

Suppose Assumption 4 holds,
$\nabla^{2}f_{0}(y)+\frac{\mu}{2}\nabla^{2}f(y)\succ 0$ for any $\mu>0$ and
any $y$ such that $f(y)<0$.

_Proof._ Under Assumption 4, for any $y$ with $f(y)<0$ and any $\mu>0$, if
$\mu\geq\mu_{y}$,

$\nabla^{2}f_{0}(y)+\frac{\mu}{2}\nabla^{2}f(y)\succeq\nabla^{2}f_{0}(y)+\frac{\mu_{y}}{2}\nabla^{2}f(y)\succ
0.$

Otherwise, $\mu<\mu_{y}$ and it holds that

$\nabla^{2}f_{0}(y)+\frac{\mu}{2}\nabla^{2}f(y)=\frac{\mu}{\mu_{y}}\left(\nabla^{2}f_{0}(y)+\frac{\mu_{y}}{2}\nabla^{2}f(y)\right)+\frac{\mu_{y}-\mu}{\mu_{y}}\nabla^{2}f_{0}(y)\succ
0.$

The last inequality dues to the convexity of $f_{0}(y)$ and $\mu<\mu_{y}$. The
proof is complete.

Let $(x_{*},y_{*})$ be a local non-global minimizer of (15). We first have
$\varphi(\mu^{*})=-f(y_{*})$ by (16) and (18). Since $x_{*}$ is a local non-
global minimizer of (7), it holds that $\varphi^{\prime}(\mu^{*})\geq 0$ by
Theorem 3.1 (i) of Martínez [15]. While in our case, we have a stronger
result.

###### Theorem 4.4

Suppose $(x_{*},y_{*})$ is a local non-global minimizer of (15), there exist
$\mu^{*}\in(\max\\{0,-\lambda_{2}\\},-\lambda_{1})$ such that (16), (17) and
(18) hold. Furthermore, under Assumption 4, we have

$\varphi^{\prime}(\mu^{*})\geq\frac{1}{2}\nabla
f(y_{*})^{T}\left[\nabla^{2}f_{0}(y_{*})+\frac{\mu^{*}}{2}\nabla^{2}f(y_{*})\right]^{-1}\nabla
f(y_{*}).$ (20)

_Proof._ Theorem 3.2 implies $x_{*}\neq 0$. According to Theorem 3.4, there is
a unique $\mu^{*}$ such that (16), (17) and (18) hold with
$\mu^{*}\in(\max\\{0,-\lambda_{2}\\},-\lambda_{1})$. Moreover, According to
Lemma 3.1 (a), we have

$\begin{bmatrix}s^{T}&t^{T}\end{bmatrix}\begin{bmatrix}H+\mu^{*}I&0\\\
0&\nabla^{2}f_{0}(y_{*})+\frac{\mu^{*}}{2}\nabla^{2}f(y_{*})\end{bmatrix}\begin{bmatrix}s\\\
t\end{bmatrix}\geq 0$ (21)

for all $s\in{\mathbb{R}}^{n},t\in{\mathbb{R}}^{m}$ satisfying

$x_{*}^{T}s+\tfrac{1}{2}\nabla f(y_{*})^{T}t=0.$ (22)

Since $H+\mu^{*}I$ is nonsingular, it follows from (2) and (16) that

$x_{*}=-(H+\mu^{*}I)^{-1}c=-\sum_{i=1}^{n}\frac{g_{i}}{\lambda_{i}+\mu^{*}}v_{i}.$
(23)

For any $\mu\in(-\lambda_{2},-\lambda_{1})$, define
$W(\mu)\in{\mathbb{R}}^{(n+m)\times(n+m-1)}$:

$W(\mu)=\begin{bmatrix}V&0\\\
0&I_{m}\end{bmatrix}\begin{bmatrix}\frac{g_{2}}{\lambda_{2}+\mu}&\frac{g_{3}}{\lambda_{3}+\mu}&\cdots&\frac{g_{n}}{\lambda_{n}+\mu}&-\frac{1}{2}\frac{\partial
f(y_{*})}{\partial y_{1}}&-\frac{1}{2}\frac{\partial f(y_{*})}{\partial
y_{2}}&\cdots&-\frac{1}{2}\frac{\partial f(y_{*})}{\partial y_{m}}\\\
-\frac{g_{1}}{\lambda_{1}+\mu}&0&\cdots&0&0&0&\cdots&0\\\
0&-\frac{g_{1}}{\lambda_{1}+\mu}&\cdots&0&0&0&\cdots&0\\\
\vdots&\vdots&&\vdots&\vdots&\vdots&&\vdots\\\
0&0&\cdots&-\frac{g_{1}}{\lambda_{1}+\mu}&0&0&\cdots&0\\\
0&0&\cdots&0&-\frac{g_{1}}{\lambda_{1}+\mu}&0&\cdots&0\\\
0&0&\cdots&0&0&-\frac{g_{1}}{\lambda_{1}+\mu}&\cdots&0\\\
\vdots&\vdots&&\vdots&\vdots&\vdots&&\vdots\\\
0&0&\cdots&0&0&0&\cdots&-\frac{g_{1}}{\lambda_{1}+\mu}\\\ \end{bmatrix}.$ (24)

By Theorem 3.4, we have $g_{1}=v_{1}^{T}c\neq 0$. Therfore,

${\rm rank}(W(\mu))=n+m-1,~{}\forall\mu\in(-\lambda_{2},-\lambda_{1}).$ (25)

Moreover, by (23) and (24) we have

$\begin{bmatrix}x_{*}^{T},&\tfrac{1}{2}\nabla
f(y_{*})^{T}\end{bmatrix}W(\mu^{*})e_{j}=0,~{}j=1,\cdots,n+m-1,$ (26)

where $e_{j}$ is the $j$-th standard unit vector in ${\mathbb{R}}^{n+m-1}$.
According to (25) and (26), all columns of $W(\mu^{*})$ form a basis of the
hyperplane (22). For any $\mu\in(-\lambda_{2},-\lambda_{1})$, define

$B(\mu)=W(\mu)^{T}\begin{bmatrix}H+\mu I&0\\\
0&\nabla^{2}f_{0}(y_{*})+\frac{\mu^{*}}{2}\nabla^{2}f(y_{*})\end{bmatrix}W(\mu).$
(27)

Then, we have

$B(\mu)=\begin{bmatrix}\hat{B}(\mu)+\sigma uu^{T}&-\tfrac{\sigma}{2}u\nabla
f(y_{*})^{T}\\\ -\tfrac{\sigma}{2}\nabla
f(y_{*})u^{T}&~{}\frac{g_{1}^{2}}{\sigma^{2}}\left(\nabla^{2}f_{0}(y_{*})+\frac{\mu^{*}}{2}\nabla^{2}f(y_{*})\right)+\frac{\sigma}{4}\nabla
f(y_{*})\nabla f(y_{*})^{T}\end{bmatrix}$

where

$\hat{B}(\mu)=\begin{bmatrix}\frac{g_{1}^{2}(\lambda_{2}+\mu)}{{(\lambda_{1}+\mu)}^{2}}&\cdots&0\\\
\vdots&\ddots&\vdots\\\
0&\cdots&\frac{g_{1}^{2}(\lambda_{n}+\mu)}{{(\lambda_{1}+\mu)}^{2}}\end{bmatrix},~{}u=\begin{bmatrix}\frac{{g_{2}}}{\lambda_{2}+\mu}\\\
\vdots\\\ \frac{{g_{n}}}{\lambda_{n}+\mu}\\\
\end{bmatrix},~{}\sigma=\lambda_{1}+\mu.$

Equivalently,

$B(\mu)=\bar{B}(\mu)+\sigma\bar{u}\bar{u}^{T},$ (28)

where

$\bar{B}(\mu)=\begin{bmatrix}\hat{B}(\mu)&0\\\
0&(\frac{g_{1}}{\sigma})^{2}(\nabla^{2}f_{0}(y_{*})+\frac{\mu^{*}}{2}\nabla^{2}f(y_{*}))\end{bmatrix},~{}\bar{u}=\begin{bmatrix}u\\\
-\frac{1}{2}\nabla f(y_{*})\end{bmatrix}.$

As $g_{1}\neq 0$, $\hat{B}(\mu)\succ 0$ for all
$\mu\in(-\lambda_{2},-\lambda_{1})$. Since both $f_{0}(\cdot)$ and $f(\cdot)$
are convex and $\mu^{*}>0$, according to Assumption 4 and Lemma 4.3, we have

$\nabla^{2}f_{0}(y_{*})+\frac{\mu^{*}}{2}\nabla^{2}f(y_{*})\succ 0.$

Now, $\bar{B}(\mu)\succ 0$ for all $\mu\in(-\lambda_{2}.-\lambda_{1})$. So

$\displaystyle{\rm det}(\bar{B}(\mu))>0.$ (29)

Hence, $B(\mu)=\bar{B}(\mu)(I+\sigma\bar{B}(\mu)^{-1}\bar{u}\bar{u}^{T})$ and
(see [10])

${\rm det}(B(\mu))={\rm
det}(\bar{B}(\mu))(1+\sigma\bar{u}^{T}[\bar{B}(\mu)]^{-1}\bar{u}).$ (30)

Notice that

$\displaystyle 1+\sigma\bar{u}^{T}[\bar{B}(\mu)]^{-1}\bar{u}$ $\displaystyle=$
$\displaystyle 1+\sigma
u^{T}\hat{B}^{-1}(\mu)u+\frac{\sigma^{3}}{4g_{1}^{2}}\nabla
f(y_{*})^{T}\left[\nabla^{2}f_{0}(y_{*})+\frac{\mu^{*}}{2}\nabla^{2}f(y_{*})\right]^{-1}\nabla
f(y_{*})$ $\displaystyle=$
$\displaystyle-\frac{\sigma^{3}}{2g_{1}^{2}}\left[\frac{-2g_{1}^{2}}{(\lambda_{1}+\mu)^{3}}+\cdots+\frac{-2g_{n}^{2}}{(\lambda_{n}+\mu)^{3}}-\frac{1}{2}\nabla
f(y_{*})^{T}\left[\nabla^{2}f_{0}(y_{*})+\frac{\mu^{*}}{2}\nabla^{2}f(y_{*})\right]^{-1}\nabla
f(y_{*})\right]$ $\displaystyle=$
$\displaystyle-\frac{\sigma^{3}}{2g_{1}^{2}}\left[\varphi^{\prime}(\mu)-\frac{1}{2}\nabla
f(y_{*})^{T}\left[\nabla^{2}f_{0}(y_{*})+\frac{\mu^{*}}{2}\nabla^{2}f(y_{*})\right]^{-1}\nabla
f(y_{*})\right],$ (31)

where the third equality follows from (19). It follows from (30) and (31) that

${\rm det}(B(\mu))=-\frac{\sigma^{3}}{2g_{1}^{2}}{\rm
det}(\bar{B}(\mu))\left[\varphi^{\prime}(\mu)-\frac{1}{2}\nabla
f(y_{*})^{T}\left[\nabla^{2}f_{0}(y_{*})+\frac{\mu^{*}}{2}\nabla^{2}f(y_{*})\right]^{-1}\nabla
f(y_{*})\right].$ (32)

According to the definition of $\sigma$ and the fact $g_{1}\neq 0$, for
$\mu^{*}\in(-\lambda_{2},-\lambda_{1})$, it holds that

$-\frac{\sigma^{3}}{2g_{1}^{2}}>0.$ (33)

It implies from (21), (22) and (27) that $B(\mu^{*})\succeq 0$ and hence ${\rm
det}(B(\mu^{*}))\geq 0$. Consequently, by (29), (32) and (33), we get (20).

Based on the above defined $\varphi(\mu)$, we now characterize the second-
order sufficient optimality condition.

###### Theorem 4.5

Under Assumption 4, if there is a
$\mu^{*}\in(\max\\{0,-\lambda_{2}\\},-\lambda_{1})$ satisfying (16)-(18), and

$\varphi^{\prime}(\mu^{*})>\frac{1}{2}\nabla
f(y_{*})^{T}\left[\nabla^{2}f_{0}(y_{*})+\frac{\mu^{*}}{2}\nabla^{2}f(y_{*})\right]^{-1}\nabla
f(y_{*}),$ (34)

then $(x_{*},y_{*})$ is a strict local minimizer of (15).

_Proof._ Assume that $(x_{*},y_{*})$ satisfies (16)-(18) for some
$\mu^{*}\in(\max\\{0,-\lambda_{2}\\},-\lambda_{1})$ and (34) holds. Since
$\varphi^{\prime}(\cdot)$ is strictly increasing in
$(-\lambda_{2},-\lambda_{1})$, we have

$\varphi^{\prime}(\mu)>\frac{1}{2}\nabla
f(y_{*})^{T}\left[\nabla^{2}f_{0}(y_{*})+\frac{\mu^{*}}{2}\nabla^{2}f(y_{*})\right]^{-1}\nabla
f(y_{*}),~{}\forall\mu\in[\mu^{*},-\lambda_{1}).$ (35)

Suppose that $(x_{*},y_{*})$ is not a strictly local minimizer of (15). Define
$W(\mu)$ and $B(\mu)$ as in (24) and (27), respectively. Notice that (32) and
(33) hold for all $\mu\in[\mu^{*},-\lambda_{1})$. All the eigenvalues of
$\bar{B}(\mu)$ are positive for $\mu\in(-\lambda_{2},-\lambda_{1})$. If
$(x_{*},y_{*})$ is not a strict local minimizer of (15), according to Lemma
3.1 (b), $B(\mu^{*})$ has at least one eigenvalue less than or equal to zero.
Now by (28), all the eigenvalues of $B(\mu)$ are strictly positive if
$\mu\in(-\lambda_{2},-\lambda_{1})$ is close enough to $-\lambda_{1}$.
Therefore, there exists $\tilde{\mu}\in[\mu^{*},-\lambda_{1})$ such that
$B(\tilde{\mu})$ is singular. So,

$0={\rm det}(B(\tilde{\mu}))=-\frac{\tilde{\sigma}^{3}}{2g_{1}^{2}}{\rm
det}(\bar{B}(\tilde{\mu}))\left[\varphi^{\prime}(\tilde{\mu})-\frac{1}{2}\nabla
f(y_{*})^{T}\left[\nabla^{2}f_{0}(y_{*})+\frac{\mu^{*}}{2}\nabla^{2}f(y_{*})\right]^{-1}\nabla
f(y_{*})\right],$ (36)

where $\tilde{\sigma}=\lambda_{1}+\tilde{\mu}$. It implies from (36) and ${\rm
det}(\bar{B}(\tilde{\mu}))>0$ that

$\varphi^{\prime}(\tilde{\mu})=\frac{1}{2}\nabla
f(y_{*})^{T}\left[\nabla^{2}f_{0}(y_{*})+\frac{\mu^{*}}{2}\nabla^{2}f(y_{*})\right]^{-1}\nabla
f(y_{*}),$

which contradicts (35). Thus, the fact
$\mu^{*}\in(\max\\{0,-\lambda_{2}\\},-\lambda_{1})$, (16)-(18), and (34) imply
that $(x_{*},y_{*})$ is a strict minimizer of (15).

Under Assumption 4, we show how to find the local non-global minimizer of
(15). For $\mu\in(\max\\{-\lambda_{2},0\\},-\lambda_{1})$, define

$x(\mu)=-(H+\mu I)^{-1}c,~{}y(\mu)=\arg\min\limits_{y\in{\mathbb{R}}^{m}}\
f_{0}(y)+\frac{\mu}{2}f(y).$

Then, we have

$\nabla f_{0}(y(\mu))=-\frac{\mu}{2}\nabla f(y(\mu)).$ (37)

Notice that, under Assumption 4, $y(\mu)$ is uniquely defined and continuously
differential in terms of $\mu$, according to the well-known implicit function
theorem. Denote by $y^{\prime}(\mu)$ the derivative of $y(\mu)$.
Differentiating both sides of equation (37) with respect to $\mu$ yields that

$\left[\nabla^{2}f_{0}(y(\mu))+\frac{\mu}{2}\nabla^{2}f(y(\mu))\right]y^{\prime}(\mu)=-\frac{1}{2}\nabla
f(y(\mu)).$

Note that Assumption 4 and Lemma 4.3 imply the non-singularity of
$\nabla^{2}f_{0}(y(\mu))+\frac{\mu}{2}\nabla^{2}f(y(\mu))$. Then we have

$y^{\prime}(\mu)=-\frac{1}{2}{[\nabla^{2}f_{0}(y(\mu))+\frac{\mu}{2}\nabla^{2}f(y(\mu))]}^{-1}\nabla
f(y(\mu)).$ (38)

Define

$\psi(\mu)=-f(y(\mu)).$

Applying the chain rule to calculate the derivative of $\psi(\cdot)$ gives

$\psi^{\prime}(\mu)=-\nabla f(y(\mu))^{T}y^{\prime}(\mu)=\frac{1}{2}\nabla
f(y(\mu))^{T}{[\nabla^{2}f_{0}(y(\mu))+\frac{\mu}{2}\nabla^{2}f(y(\mu))]}^{-1}\nabla
f(y(\mu)),$

where the second equality holds due to (38). According to Theorem 4.5, if
there exists $\mu\in(\min\\{-\lambda_{2},0\\},-\lambda_{1})$ such that

$\varphi(\mu)=\psi(\mu),~{}\varphi^{\prime}(\mu)>\psi^{\prime}(\mu),$

then $(x(\mu),y(\mu))$ is a local non-global minimizer of (15). It is
sufficient to find the root of the scalar function

$\phi(\mu)=\varphi(\mu)-\psi(\mu),~{}\mu\in(\max\\{-\lambda_{2},0\\},-\lambda_{1})$
(39)

satisfying $\phi^{\prime}(\mu)>0$.

##  5 Local Non-Global Optimality Conditions: an Intensive Analysis on
Quadratic Single-Constraint Case.

In this section, we focus on a more special single-constraint case of (TRS-C):

$\begin{array}[]{cl}\min\limits_{x\in{\mathbb{R}}^{n},y\in{\mathbb{R}}}&\tfrac{1}{2}x^{T}Hx+c^{T}x+f_{0}(y)\\\
{\rm s.t.}&x^{T}x-ay-b\leq 0,\end{array}$ (40)

where $f_{0}$ is twice continuously differentiable and strongly convex in
$S:=\\{y:ay+b>0\\}$. We show that in this case, there may be more than one
local non-global minimizer, and under some assumptions there is a necessary
and sufficient optimality condition for local non-global minimizer.

Specially structured, (40) contains two well-known cases, (TRS) and (1).
Specifically, (40) with $a=0,b=\Delta,f_{0}(y)=y^{2}$ reduces to (TRS), and
(1) corresponds to the case of (40) with
$a=1,b=0,f_{0}(y)=\tfrac{\sigma}{p}y^{\tfrac{p}{2}}$. A common property of
both cases is that there is at most one local non-global minimizer,
characterized by a necessary and sufficient condition [15, 13, 23].

Without loss of generality, we can assume that $a>0$. Actually, if $a=0$, (40)
separates into (TRS) and an unconstrained convex optimization problem in terms
of $x$ and $y$, respectively. If $a<0$. let $z=-y$. Then (40) is equivalent to

$\begin{array}[]{cl}\min\limits_{x\in{\mathbb{R}}^{n},z\in{\mathbb{R}}}&\tfrac{1}{2}x^{T}Hx+c^{T}x+f_{0}(-z)\\\
{\rm s.t.}&x^{T}x-(-a)z-b\leq 0,\end{array}$

where $f_{0}(-z)$ is convex in terms of $z$.

As shown in Section 2, there are necessary and sufficient optimality
conditions for global minimizers of (40) (see Theorems 2.1 and 2.3). According
to Theorem 4.4, for any local non-global minimizer of (40) denoted by
$(x_{*},y_{*})$, we have $x_{*}\neq 0$, and there is a unique
$\max\\{0,-\lambda_{2}\\}<\mu^{*}<-\lambda_{1}$ such that

$(H+\mu^{*}I)x_{*}=-c,~{}f_{0}^{\prime}(y_{*})-\frac{\mu^{*}a}{2}=0,~{}x_{*}^{T}x_{*}-ay_{*}-b=0,~{}\varphi^{\prime}(\mu^{*})\geq\frac{a^{2}}{2f^{\prime\prime}_{0}(y_{*})}.$

Since $f_{0}(\cdot)$ is strongly convex and twice continuously differentiable
in $S$, we have $f^{\prime\prime}_{0}(\cdot)>0$, and $f^{\prime}_{0}(\cdot)$
is strictly increasing so that $(f^{\prime}_{0})^{-1}(\frac{\mu a}{2})$
exists. Define

$y(\mu)={(f^{\prime}_{0})}^{-1}\left(\frac{\mu a}{2}\right).$ (41)

Finding a local non-global minimizer of (40) amounts to search in
$(\max\\{-\lambda_{2},0\\},-\lambda_{1})$ a root of $\varphi(\mu)=\psi(\mu)$
such that $\varphi^{\prime}(\mu)>\psi^{\prime}(\mu)$, where

$\psi(\mu)=ay(\mu)+b=a{(f^{\prime}_{0})}^{-1}\left(\frac{\mu a}{2}\right)+b.$
(42)

Then, by Theorem 4.5, $(x(x),y(\mu))$ is a local non-global minimizer of (40).

While either (TRS) or (1) has at most one local non-global minimizer, the
answer to Question 1.2 could be surprisingly negative. The following two
examples illustrate that (40) could have more than one local non-global
minimizer.

######  Example 5.1 (A quartic example of (40) with two local non-global
minimizers)

Consider (40) with $n=2,H={\rm Diag}\\{-5,-1\\},c=(1,1),a=1,b=0$ and
$f_{0}(y)$ is a quartic polynomial function:

$f_{0}(y)=\left(\tfrac{12377}{51072}-\tfrac{25\sqrt{210}}{3648}\right)y^{4}+\left(\tfrac{5\sqrt{210}}{228}-\tfrac{9257}{7980}\right)y^{3}+\left(\tfrac{1366171}{638400}-\tfrac{35\sqrt{210}}{1824}\right)y^{2}+\left(\tfrac{\sqrt{210}}{190}+\tfrac{4667}{26600}\right)y.$

One can verify the strong convexity of $f_{0}$. It follows from (19) and (42)
that

$\displaystyle\varphi(\mu)=\frac{1}{{(\mu-5)}^{2}}+\frac{1}{{(\mu-1)}^{2}},$
(43)
$\displaystyle\psi(\mu)=y(\mu)={(f^{\prime}_{0})}^{-1}\left(\tfrac{\mu}{2}\right).$

We plot in Figure 1 the functions $\varphi(\mu)$ and $\psi(\mu)$. It is
observed that, in the interval $(1,5)$, there are four roots of
$\varphi(\mu)=\psi(\mu)$,
$\mu_{1}=3.13,\mu_{2}=3.72,\mu_{3}=4.17,\mu_{4}=4.25$. As
$\varphi^{\prime}(\mu_{i})>\psi^{\prime}(\mu_{i})$ for $i=2,4$,
$(x(\mu_{2})^{T},y(\mu_{2}))$ and $(x(\mu_{4})^{T},y(\mu_{4}))$ are two local
non-global minimizers of Example 5.1 by Theorem 4.5.

Actually, at $\mu_{2}$ and $\mu_{4}$, the corresponding solutions are
$(x(\mu_{2})^{T},y(\mu_{2}))=(0.78,-0.37,0.74)$ and
$(x(\mu_{4})^{T},y(\mu_{4}))=(1.34,-0.31,1.89)$, respectively. The reduced
Hessian matrices (27) at $\mu_{2},\mu_{4}$ are given by

$B(\mu_{2})=\begin{bmatrix}1.48&-0.24\\\ -0.24&0.24\\\ \end{bmatrix}\succ
0,~{}B(\mu_{4})=\begin{bmatrix}5.77&-0.11\\\ -0.11&0.36\\\ \end{bmatrix}\succ
0.$

Therefore, according to Lemma 3.1 (b), both $(x(\mu_{2})^{T},y(\mu_{2}))$ and
$(x(\mu_{4})^{T},y(\mu_{4}))$ are local minimizers of Example 5.1. On the
other hand, there is a root $\mu_{0}=5.63$ of $\varphi(\mu)=\psi(\mu)$ in the
interval $(5,+\infty)$. The corresponding solution
$(x(\mu_{0})^{T},y(\mu_{0}))=(-1.58,-0.22,2.56)$ is a global minimizer by
Theorem 2.3.

Figure 1: Variations of $\varphi(\mu)$ and $\psi(\mu)$ in Example 5.1.

In the following, we show that (40) could have arbitrary number of local non-
global minimizers.

######  Example 5.2 (An example of (40) with $d$ local non-global minimizers)

Let $n=2,H={\rm Diag}\\{-5,-1\\},c=(1,1),a=1,b=0$, and $d$ is a given positive
integer. We first select a strictly increasing sequence
$\\{\mu_{1},\cdots,\mu_{2d}\\}$ from
$(\max\\{0,-\lambda_{2}\\},-\lambda_{1})$. We assume that $\mu_{1}$ is
sufficiently close to $-\lambda_{1}$ so that $\varphi(\mu)$ strictly increases
when $\mu>\mu_{1}$. For each $j\in\\{1,\cdots,d\\}$, let
$L_{j}(\mu):~{}{\mathbb{R}}\rightarrow{\mathbb{R}}$ be a linear function
passing through two points $(\mu_{2j-1},\varphi(\mu_{2j-1}))$ and
$(\mu_{2j},\varphi(\mu_{2j}))$. Define

$L(\mu)=\max\\{L_{1}(\mu),\cdots,L_{d}(\mu)\\},$

which is piecewise linear and convex in terms of $\mu$. $L(\mu)$ is nonsmooth
at each intersection point of $L_{j}(\mu)$ and $L_{j+1}(\mu)$, denoted by
$o_{j}$, for $j=1,\cdots,d-1$. Let

$\epsilon=\tfrac{1}{2}\min\\{\min\\{|o_{j}-\mu_{2j}|,|o_{j}-\mu_{2j+1}|\\}:~{}j=1,\cdots,d-1\\}.$

Define $l_{j}=o_{j}-\epsilon,~{}r_{j}=o_{j}+\epsilon$. For $j=1,\cdots,d-1$,
let $Q_{j}(\mu):~{}{\mathbb{R}}\rightarrow{\mathbb{R}}$ be a quadratic
function not only connecting two endpoints $(l_{j},L_{j}(l_{j}))$ and
$(r_{j},L_{j+1}(r_{j}))$, but also tangent to $L_{j}(\mu)$ and $L_{j+1}(\mu)$
at these two endpoints, respectively. Define

$\psi(\mu)=\left\\{\begin{array}[]{lll}L_{j}(\mu),&\mu\in[r_{j-1},l_{j}],&\text{for}~{}j=1,\cdots,d,\\\
Q_{j}(\mu),&\mu\in[l_{j},r_{j}],&\text{for}~{}j=1,\cdots,d-1,\end{array}\right.$

where $r_{0}:=-\lambda_{2}$ and $l_{d}:=-\lambda_{1}$. We can verify that
$\psi(\mu)$ is continuously differentiable and strictly increasing.

With the above definitions, we can see that $\psi(\mu)$ intersects
$\varphi(\mu)$ at $(\mu_{i},\varphi(\mu_{i})),i=1,2,\cdots,2d$, and it holds
that
$\varphi^{\prime}(\mu_{2j})>\psi^{\prime}(\mu_{2j})=L^{\prime}_{j}(\mu_{2j})$
for $j=1,\cdots,d$. According to (42) and $(a,b)=(1,0)$, we have
$y(\mu)=\psi(\mu)$. It follows from $f_{0}^{\prime}(y)=\tfrac{\mu}{2}$ that

$f_{0}^{\prime}(y)=\frac{1}{2}\psi^{-1}(y),$

which implies that

$f_{0}(y)=\frac{1}{2}\int\psi^{-1}(y)dy$

is convex, and $f^{\prime\prime}_{0}(y)>0$ in $(-\lambda_{2},-\lambda_{1})$ as
$\psi^{-1}(y)$ is strictly increasing. Since
$\varphi^{\prime}(\mu_{2j})>\psi^{\prime}(\mu_{2j})$ for $j=1,\cdots,d$, by
Theorem 4.5, $(x(\mu_{2j}),\psi(\mu_{2j}))$ ($j=1,\cdots d$) are all local
non-global minimizers.

When $d=3$, setting
$\mu_{1}=3.00,\mu_{2}=3.58,\mu_{3}=3.94,\mu_{4}=4.13,\mu_{5}=4.40,\mu_{6}=4.45,o_{1}=3.80,o_{2}=4.30$
in the above scheme gives

$f_{0}(y)=\left\\{\begin{aligned}
y^{2}+\frac{y}{2},&&y\in\left(-\infty,\frac{27}{40}\right]\\\
\frac{1433y}{780}+\frac{2\cdot
10^{1/2}{{(195y-131)}^{3/2}}}{114075}-\frac{3263447}{7300800},&&y\in\left(\frac{27}{40},\frac{23}{25}\right]\\\
\frac{5y^{2}}{44}+\frac{383y}{200}-\frac{38363}{88000},&&y\in\left(\frac{23}{25},\frac{79}{50}\right]\\\
\frac{871y}{420}+\frac{{(2100y-3197)}^{3/2}}{1323000}-\frac{7189183}{10584000},&&y\in\left(\frac{79}{50},\frac{143}{50}\right]\\\
\frac{5y^{2}}{212}+\frac{2189y}{1060}-\frac{206802453584843}{281474976710656},&&y\in\left(\frac{143}{50},\infty\right)\\\
\end{aligned}\right..$

In this case, $\varphi(\mu)$ is given in (43) and

$\psi(\mu)=y(\mu)=\left\\{\begin{aligned}
\frac{\mu}{4}-\frac{1}{4},&&\mu\in\left(-\infty,\frac{37}{10}\right]\\\
\frac{39{\mu}^{2}}{8}-\frac{1433}{40}\mu+\frac{53191}{800},&&\mu\in\left(\frac{37}{10},\frac{39}{10}\right]\\\
\frac{11}{5}\mu-\frac{383}{50},&&\mu\in\left(\frac{39}{10},\frac{42}{10}\right)\\\
{{21}{\mu}^{2}}-\frac{871}{5}\mu+\frac{18139}{50},&&\mu\in\left(\frac{42}{10},\frac{44}{10}\right]\\\
\frac{53}{5}\mu-\frac{2189}{50},&&\mu\in\left(\frac{44}{10},\infty\right)\\\
\end{aligned}\right..$

We plot both in Figure 2. We observe that $\varphi(\mu_{j})=\psi(\mu_{j})$ for
$j=1,2,\cdots,6$ and $\varphi^{\prime}(\mu_{2j})>\psi^{\prime}(\mu_{2j})$ for
$j=1,2,3$. Thus, $(x(\mu_{2j}),\psi(\mu_{2j}))$ ($j=1,2,3$) are three local
non-global minimizers of Example 5.2 according to Theorem 4.5.

Figure 2: Variations of $\varphi(\mu)$ and $\psi(\mu)$ in Example 5.2.

Now, we are interested in when (40) has at most one local non-global
minimizer, and whether(40) could have necessary and sufficient optimality
condition at local non-global minimizer. The proof is a combination of those
of Theorem 3.2 in [13] and Theorem 3.1 in [23].

###### Theorem 5.3

Suppose $f_{0}(y)$ is thrice continuously differentiable and strongly convex
in $S$ and $\psi(\mu)$ defined in (42) is log-concave in
$(\max\\{-\lambda_{2},0\\},-\lambda_{1})$, then

(i) (40) has at most one local non-global minimizer.

(ii) $(x_{*},y_{*})$ is a local non-global minimizer of (40) if and only if

$(H+\mu^{*}I)x_{*}+c=0,~{}f^{\prime}_{0}(y_{*})-\tfrac{a\mu^{*}}{2}=0,$ (44)

where $\mu^{*}$ is a root of the scalar function $\phi(\mu)$ defined in (39)
in $(\max\\{-\lambda_{2},0\\},-\lambda_{1})$ such that
$\phi^{\prime}(\mu^{*})>0$.

_Proof._ (i) We first observe that the scalar function $\phi(\mu)$ in (39) has
the same roots as

$p(\mu)=\ln\varphi(\mu)-\ln\psi(\mu),~{}\mu\in(\max\\{-\lambda_{2},0\\},-\lambda_{1}).$

By Theorem 3.4, it is necessary to assume $g_{1}\neq 0$. Using chain rule,
(19) gives

$p^{\prime\prime}(\mu)=\frac{\left[\sum_{i=1}^{n}\frac{6g_{i}^{2}}{(\lambda_{i}+\mu)^{4}}\right]\left[\sum_{i=1}^{n}\frac{g_{i}^{2}}{(\lambda_{i}+\mu)^{2}}\right]-{\left[\sum_{i=1}^{n}\frac{2g_{i}^{2}}{{(\lambda_{i}+\mu)}^{3}}\right]}^{2}}{[\varphi(\mu)]^{2}}-{\left(\ln\psi(\mu)\right)}^{\prime\prime}.$

Define two vectors in ${\mathbb{R}}^{n}$:

$s=\begin{bmatrix}\frac{\sqrt{6}g_{1}}{{(\lambda_{1}+\mu)}^{2}},\cdots,\frac{\sqrt{6}g_{n}}{{(\lambda_{n}+\mu)}^{2}}\end{bmatrix}^{T},~{}t=\begin{bmatrix}\frac{g_{1}}{\lambda_{1}+\mu},\cdots,\frac{g_{n}}{\lambda_{n}+\mu}\end{bmatrix}^{T}$

It follows from Cauchy-Schwartz inequality that

${\left[\sum_{i=1}^{n}\frac{2g_{i}^{2}}{{(\lambda_{i}+\mu)}^{3}}\right]}^{2}<{(s^{T}t)}^{2}\leq(s^{T}s)(t^{T}t)=\left[\sum_{i=1}^{n}\frac{6g_{i}^{2}}{{(\lambda_{i}+\mu)}^{4}}\right]\left[\sum_{i=1}^{n}\frac{g_{i}^{2}}{{(\lambda_{i}+\mu)}^{2}}\right].$

The assumption that $\psi(\mu)$ is log-concave implies that
${\left(\ln\psi(\mu)\right)}^{\prime\prime}\leq 0$. Therefore, we have
$p^{\prime\prime}(\mu)>0$ and hence $p(\mu)$ is strictly convex for all
$\mu\in(\max\\{-\lambda_{2},0\\},-\lambda_{1})$. Thus the equation $p(\mu)=0$,
as well as $\phi(\mu)=0$, has at most two real roots in the above interval,
denoted by $\mu_{1}<\mu_{2}$. Suppose $\phi^{\prime}(\mu_{1})\geq 0$ and
$\phi^{\prime}(\mu_{2})\geq 0$. Then, for any sufficiently small
$\epsilon\in(0,(\mu_{2}-\mu_{1})/2)$, we have

$\phi(\mu_{1}+\epsilon)\geq\phi(\mu_{1})=0,~{}\phi(\mu_{2}-\epsilon)\leq\phi(\mu_{2})=0.$

Therefore, there is a $\tilde{\mu}\in[\mu_{1}+\epsilon,\mu_{2}-\epsilon]$ such
that $\phi(\tilde{\mu})=0$, which is a contradiction. Consequently, the scalar
function $\phi(\mu)$ has at most one real root satisfying
$\phi^{\prime}(\mu)\geq 0$. Following Theorem 4.4, the proof is complete.

(ii) Firstly, we prove that the assumption that $\psi(\mu)$ is log-concave in
$(\max\\{-\lambda_{2},0\\},-\lambda_{1})$ is equivalent to

$\displaystyle
f_{0}^{\prime\prime\prime}(y(\mu))+\frac{a}{ay(\mu)+b}f_{0}^{\prime\prime}(y(\mu))\geq
0,\mu\in(\max\\{-\lambda_{2},0\\},-\lambda_{1}).$ (45)

Applying the inverse function theorem to (41), one can verify that

$\begin{array}[]{ll}y^{\prime}(\mu)=\frac{a}{2f^{\prime\prime}_{0}(y(\mu))},~{}y^{\prime\prime}(\mu)=-\frac{af^{\prime\prime\prime}_{0}(y(\mu))y^{\prime}(\mu)}{2(f^{\prime\prime}_{0}(y(\mu)))^{2}}.\end{array}$

Combining with (42),

$\begin{array}[]{ll}(\ln(\psi(\mu)))^{\prime\prime}&=\frac{\psi^{\prime\prime}(\mu)\psi(\mu)-{(\psi^{\prime}(\mu))}^{2}}{{(\psi(\mu))}^{2}}\\\
&=-\frac{a^{3}}{4(ay(\mu)+b){[f_{0}^{\prime\prime}(y(\mu))]}^{3}}[f_{0}^{\prime\prime\prime}(y(\mu))+\frac{a}{ay(\mu)+b}f_{0}^{\prime\prime}(y(\mu))].\end{array}$

which implies (45).

It is sufficient to prove that the optimality condition in Theorem 4.5 is
necessary, if (45) hold. Let $(x_{*},y_{*})$ be a local non-global minimizer
of (40). It follows from Theorem 4.4 and the discussion after Theorem 4.5 that
(44) holds and $\mu^{*}$ is a root of the scalar function $\phi$ in
$(\max\\{-\lambda_{2},0\\},-\lambda_{1})$ such that
$\phi^{\prime}(\mu^{*})\geq 0$. The remaining part is to show
$\phi^{\prime}(\mu^{*})>0$. Suppose this is not true, that is, we assume
$\phi^{\prime}(\mu^{*})=0$. According to (32), the reduced Hessian

$B:=W^{T}GW$

has a zero eigenvalue, where

$G=\begin{bmatrix}H+\mu^{*}I&0\\\
0&f_{0}^{\prime\prime}(y_{*})\end{bmatrix},~{}W=\begin{bmatrix}V&0\\\
0&1\end{bmatrix}\begin{bmatrix}\frac{g_{2}}{\lambda_{2}+\mu^{*}}&\frac{g_{3}}{\lambda_{3}+\mu^{*}}&\cdots&\frac{g_{n}}{\lambda_{n}+\mu^{*}}&\frac{a}{2}\\\
-\frac{g_{1}}{\lambda_{1}+\mu^{*}}&0&\cdots&0&0\\\
0&-\frac{g_{1}}{\lambda_{1}+\mu^{*}}&\cdots&0&0\\\
\vdots&\vdots&&\vdots&\vdots\\\
0&0&\cdots&-\frac{g_{1}}{\lambda_{1}+\mu^{*}}&0\\\
0&0&\cdots&0&-\frac{g_{1}}{\lambda_{1}+\mu^{*}}\end{bmatrix}.$ (46)

Let $q\neq 0$ be an eigenvector of $B$ corresponding to the zero eigenvalue.
That is,

$W^{T}GWq=0.$ (47)

Since columns of $W$ form a basis of the hyperplane
$x_{*}^{T}s-\tfrac{a}{2}t=0$, i.e.,

$W^{T}\begin{bmatrix}x_{*}^{T}&-\tfrac{a}{2}\end{bmatrix}^{T}=0,$

and $W$ is of full column rank. It follows from (47) that

$GWq=\gamma\begin{bmatrix}x_{*}\\\ -\tfrac{a}{2}\end{bmatrix}$ (48)

for some $\gamma\in{\mathbb{R}}$. It follows from the linearly independence of
columns of $W$ and $q\neq 0$ that

$Wq\neq 0.$ (49)

Notice that the matrix $G$ in (46) is nonsingular. By combining (48) and (49),
we have

$Wq=\gamma G^{-1}\begin{bmatrix}x_{*}\\\
-\tfrac{a}{2}\end{bmatrix}=:\begin{bmatrix}s_{*}\\\ t_{*}\end{bmatrix},$ (50)

where $s_{*}\in{\mathbb{R}}^{n},t_{*}\in{\mathbb{R}}$. Thus $\gamma\neq 0$.
Furthermore, we claim that $s_{*}\neq 0,t_{*}\neq 0$ and

$t_{*}=\frac{2}{a}x_{*}^{T}s_{*}.$ (51)

Actually, substituting the matrix $G$ defined in (46) into the second equality
of (50) yields $t_{*}=-\tfrac{\gamma a}{2f^{\prime\prime}_{0}(y)}\neq 0$.
Multiplying $q^{T}W^{T}$ from left to both sides of (48) gives

$0=q^{T}W^{T}GWq=\gamma(s_{*}^{T}x_{*}-\tfrac{at_{*}}{2}),$

where the first equality holds from (47). Now we obtain (51). Since $t_{*}\neq
0$, it follows from (51) that $s_{*}\neq 0$. Define

$y(\beta):=\tfrac{\|x_{*}+\beta s_{*}\|^{2}-b}{a},~{}h(\beta):=q(x_{*}+\beta
s_{*})+f_{0}(y(\beta)).$

One can verify that

$\begin{array}[]{ll}h^{\prime}(\beta)&=s_{*}^{T}\nabla q(x_{*}+\beta
s_{*})+f^{\prime}_{0}(y(\beta))y^{\prime}(\beta),\\\
h^{\prime\prime}(\beta)&=s_{*}^{T}\nabla^{2}q(x_{*}+\beta
s_{*})s_{*}+f^{\prime\prime}_{0}(y(\beta))[y^{\prime}(\beta)]^{2}+f^{\prime}_{0}(y(\beta))y^{\prime\prime}(\beta),\\\
h^{\prime\prime\prime}(\beta)&=f^{\prime\prime\prime}_{0}(y(\beta))[y^{\prime}(\beta)]^{3}+3f^{\prime\prime}_{0}(y(\beta))y^{\prime}(\beta)y^{\prime\prime}(\beta)+f^{\prime}_{0}(y(\beta))y^{\prime\prime\prime}(\beta),\end{array}$

and
$y(0)=y_{*},y^{\prime}(0)=t_{*},y^{\prime\prime}(0)=\tfrac{2s_{*}^{T}s_{*}}{a},y^{\prime\prime\prime}(0)=0$.
Let $\beta=0$,

$\begin{array}[]{ll}h^{\prime}(0)&=s_{*}^{T}(Hx_{*}+c)+f^{\prime}_{0}(y_{*})t_{*},\\\
h^{\prime\prime}(0)&=s_{*}^{T}Hs_{*}+f^{\prime\prime}_{0}(y_{*})t_{*}^{2}+f^{\prime}_{0}(y_{*})\tfrac{2s_{*}^{T}s_{*}}{a}=q^{T}W^{T}GWq,\\\
h^{\prime\prime\prime}(0)&=f^{\prime\prime\prime}_{0}(y_{*})t_{*}^{3}+3f^{\prime\prime}_{0}(y_{*})t_{*}\tfrac{2s_{*}^{T}s_{*}}{a},\end{array}$

where the second equality on $h^{\prime\prime}(0)$ follows from (44), (46) and
(50). The first-order necessary optimality condition (44) and (51) implies
$h^{\prime}(0)=0$. According to the definition of $q$ in (47), we have
$h^{\prime\prime}(0)=0$. Notice that $t_{*}\neq 0$. Substituting (51) and
$x_{*}^{T}x_{*}=ay_{*}+b$ into $h^{\prime\prime\prime}(0)$ yields that

$\frac{h^{\prime\prime\prime}(0)}{t_{*}^{3}}=f^{\prime\prime\prime}_{0}(y_{*})+6f^{\prime\prime}_{0}(y_{*})\frac{s_{*}^{T}s_{*}}{at_{*}^{2}}=f^{\prime\prime\prime}_{0}(y_{*})+\frac{3af^{\prime\prime}_{0}(y_{*})}{2(ay_{*}+b)}\frac{s_{*}^{T}s_{*}x_{*}^{T}x_{*}}{(x_{*}^{T}s_{*})^{2}}\geq
f^{\prime\prime\prime}_{0}(y_{*})+\frac{3af^{\prime\prime}_{0}(y_{*})}{2(ay_{*}+b)}>0,$

where the last two inequalities follow from Cauchy-Schwartz inequality, (45)
and $\tfrac{a}{ay(\mu)+b}f^{\prime\prime}_{0}(y(\mu))>0$. Note that the first
inequality also needs the fact $a>0$. We obtain $h^{\prime\prime\prime}(0)\neq
0$, which contradicts the facts that $(x_{*}+\beta s_{*},y(\beta))$ is
feasible for (40) for all $\beta\in{\mathbb{R}}$, and $(x_{*},y_{*})$ is a
local minimizer of (40). Therefore, $\phi^{\prime}(\mu^{*})>0$, the proof of
the necessary part is complete.

Figures (3a) and (3b) illustrate the functions $\ln\psi(\mu)$ and
$\ln\varphi(\mu)$ for Examples 5.1 and 5.2, respectively. One can observe that
in both cases $\ln\psi(\mu)$ is not concave, which implies the necessity of
the log-concavity assumption in Theorem 5.3.

(a) Example 5.1

(b) Example 5.2

Figure 3: Variants of $\ln\varphi(\mu)$ and $\ln\psi(\mu)$ in Examples 5.1 and
5.2.

Finally, we present some examples of $f_{0}(y)$ satisfying the assumptions in
Theorem 5.3.

###### Corollary 5.4

Problem (40) has at most one local non-global minimizer with necessary and
sufficient optimality condition for the local non-global minimizer, if one of
following conditions holds:

  1. (i)

$f_{0}(y)=\alpha y^{d},~{}\alpha>0,~{}d>1,~{}a=1,~{}b=0$, (which includes
Problem (1) as a special case).

  2. (ii)

$f_{0}(y)$ is a strongly convex quadratic function, $a>0,~{}b\geq 0$.

  3. (iii)

$f_{0}(y)$ is a strongly convex cubic polynomial function in $(0,+\infty)$,
$a=1,~{}b=0$.

_Proof._ According to Theorem 5.3, we only need to verify that (45) holds for
each case.

(i) $f_{0}(y)=\alpha y^{d},\ f^{\prime}_{0}(y)=\alpha dy^{d-1},\
f^{\prime\prime}_{0}(y)=\alpha d(d-1)y^{d-2},\
f^{\prime\prime\prime}_{0}(y)=\alpha d(d-1)(d-2)y^{d-3}.$

$f^{\prime\prime\prime}_{0}(y)+\frac{1}{y}f^{\prime\prime}_{0}(y)=\alpha
d{(d-1)}^{2}y^{d-3}>0,\ \forall y\in(0,+\infty),$

which implies that the assumption of Theorem 5.3 holds.

(ii) Without loss of generality, we assume $f_{0}(y)=\alpha y^{2}+\beta
y,~{}\alpha>0$. Then $f^{\prime}_{0}(y)=2\alpha
y+\beta,f^{\prime\prime}_{0}(y)=2\alpha,f^{\prime\prime\prime}_{0}(y)=0$.

$f^{\prime\prime\prime}_{0}(y)+\frac{a}{ay+b}f^{\prime\prime}_{0}(y)=\frac{2a\alpha}{ay+b}>0,~{}\forall
y\in(-\tfrac{b}{a},+\infty).$

(iii) Assume that $f_{0}(y)=\alpha y^{3}+\beta y^{2}+\gamma y$ is strongly
convex on $(0,+\infty)$. Notice that

$f^{\prime}_{0}(y)=3\alpha y^{2}+2\beta y+\gamma,\
f^{\prime\prime}_{0}(y)=6\alpha y+2\beta,\
f^{\prime\prime\prime}_{0}(y)=6\alpha.$

Since
$f^{\prime\prime}_{0}(y)=6\alpha\left(y+\frac{\beta}{3\alpha}\right)>0,~{}\forall
y\in(0,+\infty)$. It turns out that $\alpha>0$ and $\beta>0$.

$f^{\prime\prime\prime}_{0}(y)+\frac{1}{y}f^{\prime\prime}_{0}(y)>0+0=0,~{}\forall
y\in(0,+\infty).$

Note that we cannot extend the above cases presented in Corollary 5.4 to the
general quartic polynomial case, see Example 5.1 for a counterexample.

##  6 Conclusion

We raise a fundamental question (Question 1.1) whether local optimality can be
checked in polynomial time for hidden convex optimization. Then we focus on
the newly proposed optimization problem by jointing nonconvex trust-region
subproblem with convex optimization (TRS-C). We present a necessary and
sufficient optimality condition for global minimizer of (TRS-C), which reveals
its hidden convexity. However, it is difficult to establish a necessary and
sufficient optimality condition for local non-global minimizer, except for
some quadratic single-constraint cases. Moreover, different from trust region
subproblem (which has at most one local non-global minimizer) and convex
optimization (without local non-global minimizer), their joint problem could
have more than one local non-global minimizer. There is a quartic polynomial
case of (TRS-C) with two local non-global minimizers. We then present a
general approach to generate the instances with arbitrary number of local non-
global minimizers. Consequently, we conclude that the existence of many local
minimizers is NOT a (or at least not a unique) reason making global
optimization difficult.

While we have present some negative evidences, Question 1.1 remains open, even
on the joint problem problem (TRS-C).

## Acknowledgments.

This research was supported by the National Natural Science Foundation of
China under grants 11822103, 11571029, and 11771056, and by the Beijing
Natural Science Foundation, grant Z180005.

## References

  * Beck and Pan [2017] Beck A, Pan D (2017) A branch and bound algorithm for nonconvex quadratic optimization with ball and linear constraints. _J. Glob. Optim._ 69(2):309–342.
  * Boyd and Vandenberghe [2004] Boyd S, Vandenberghe L (2004) _Convex Optimization_ (Cambridge University Press).
  * Bubeck [2015] Bubeck S (2015) Convex optimization: Algorithms and complexity. _Foundations and Trends in Machine Learning_ 8(3-4):231–357, ISSN 1935-8237, URL http://dx.doi.org/10.1561/2200000050.
  * Cartis et al. [2011] Cartis C, Gould NIM, Toint PL (2011) Adaptive cubic regularisation methods for unconstrained optimization. part i: motivation, convergence and numerical results. _Mathematical Programming_ 127(2):245–295.
  * Conn et al. [2000] Conn AR, Gould NIM, Toint PL (2000) _Trust Region Methods_ (Society for Industrial and Applied Mathematics), URL http://dx.doi.org/10.1137/1.9780898719857.
  * Fang et al. [2017] Fang SC, Gao DY, Lin GX, Sheu RL, Xing WX (2017) Double well potential function and its optimization in the $n$-dimensional real space - part i. _Journal of Industrial and Management Optimization_ 13(3):1291–1305.
  * Fletcher [1984] Fletcher R (1984) _Linear and Nonlinear Programming, 2nd ed._ (Reading, MA: Addison-Wesley).
  * Fletcher [1987] Fletcher R (1987) _Practical Methods of Optimization, 2nd ed._ (New York: John Wiley).
  * Gay [1981] Gay DM (1981) Computing optimal locally constrained steps. _SIAM Journal on Scientific and Statistical Computing_ 2(2):186–197, URL http://dx.doi.org/10.1137/0902016.
  * Golub and Loan [1989] Golub GH, Loan CFV (1989) _Matrix Computations, 2nd ed._ (Baltimore: The Johns Hopkins University Press).
  * Gould et al. [2010] Gould NIM, Robinson DP, Thorne HS (2010) On solving trust-region and other regularised subproblems in optimization. _Mathematical Programming Computation_ 2(1):21–57.
  * Griewank [1981] Griewank A (1981) The modification of newton’s method for unconstrained optimization by bounding cubic terms. _Technical Report DAMTP/NA12_ .
  * Hsia et al. [2017] Hsia Y, Sheu RL, Yuan YX (2017) Theory and application of p-regularized subproblems for $p>2$. _Optimization Methods and Software_ 32(5):1059–1077, ISSN 1055-6788, URL http://dx.doi.org/10.1080/10556788.2016.1238917.
  * Lucidi et al. [1998] Lucidi S, Palagi L, Roma M (1998) On some properties of quadratic programs with a convex quadratic constraint. _SIAM Journal on Optimization_ 8(1):105–122, URL http://dx.doi.org/10.1137/S1052623494278049.
  * Martínez [1994] Martínez JM (1994) Local minimizers of quadratic functions on euclidean balls and spheres. _SIAM Journal on Optimization_ 4(1):159–176, URL http://dx.doi.org/10.1137/0804009.
  * Moré and Sorensen [1983] Moré JJ, Sorensen DC (1983) Computing a trust region step. _Siam Journal on Scientific and Statistical Computing_ 4(3):553–572.
  * Murty and Kabadi [1987] Murty KG, Kabadi SN (1987) Some np-complete problems in quadratic and nonlinear programming. _Math. Program._ 39(2):117–129.
  * Nesterov [2018] Nesterov Y (2018) _Lectures on Convex Optimization_ (Cham: Springer International Publishing), ISBN 1931-6836, URL http://dx.doi.org/https://doi.org/10.1007/978-3-319-91578-4.
  * Nesterov and Polyak [2006] Nesterov Y, Polyak BT (2006) Cubic regularization of newton method and its global performance. _Mathematical Programming_ 108(1):177–205.
  * Pardalos and Schnitger [1988] Pardalos PM, Schnitger G (1988) Checking local optimality in constrained quadratic programming is np-hard. _Oper. Res. Lett._ 7(2):33–45.
  * Sorensen [1982] Sorensen DC (1982) Newton’s method with a model trust region modification. _SIAM Journal on Numerical Analysis_ 19(2):409–426.
  * Tao and An [1998] Tao PD, An LTH (1998) A d.c. optimization algorithm for solving the trust-region subproblem. _SIAM Journal on Optimization_ 8(2):476–505, URL http://dx.doi.org/10.1137/S1052623494274313.
  * Wang and Xia [2020] Wang J, Xia Y (2020) Closing the gap between necessary and sufficient conditions for local nonglobal minimizer of trust region subproblem. _SIAM Journal on Optimization_ 30(3):1980–1995, URL http://dx.doi.org/10.1137/19M1294459.
  * Weiser et al. [2007] Weiser M, Deuflhard P, Erdmann B (2007) Affine conjugate adaptive newton methods for nonlinear elastomechanics. _Optimization Methods And Software_ 22(3):413–431.
  * Xia [2020] Xia Y (2020) A survey of hidden convex optimization. _J. Oper. Res. Soc. China._ 8(2):1–28.
  * Xia et al. [2017] Xia Y, Sheu RL, Fang SC, Xing W (2017) Double well potential function and its optimization in the $n$-dimensional real space - part ii. _Journal of Industrial and Management Optimization_ 13(3):1307–1328.
  * Ye [1992] Ye Y (1992) _A new complexity result on minimization of a quadratic function with a sphere constraint_ (Princeton University Press).
  * Yuan [2015] Yuan YX (2015) Recent advances in trust region algorithms. _Mathematical Programming_ 151(1):249–281.


# SigSegment: A Signal-Based Segmentation Algorithm for Identifying Anomalous
Driving Behaviours in Naturalistic Driving Videos

Kelvin Kwakye & Younho Seong
Department of Systems and Industrial Engineering
North Carolina A&T State University
Corresponding author and primary author Armstrong Aboah
Department of Radiology
Northwestern University
Sun Yi
Department of Systems and Industrial Engineering
North Carolina A&T State University

###### Abstract

In recent years, distracted driving has garnered considerable attention as it
continues to pose a significant threat to public safety on the roads. This has
increased the need for innovative solutions that can identify and eliminate
distracted driving behavior before it results in fatal accidents. In this
paper, we propose a Signal-Based anomaly detection algorithm that segments
videos into anomalies and non-anomalies using a deep CNN-LSTM classifier to
precisely estimate the start and end times of an anomalous driving event. In
the phase of anomaly detection and analysis, driver pose background
estimation, mask extraction, and signal activity spikes are utilized. A Deep
CNN-LSTM classifier was applied to candidate anomalies to detect and classify
final anomalies. The proposed method achieved an overlap score of 0.5424 and
ranked 9th on the public leader board in the AI City Challenge 2023, according
to experimental validation results.

##  1 Introduction

In the United States, distracted driving is a serious threat to public safety,
resulting in numerous fatalities each year[1]. Researchers have turned to
naturalistic driving studies and computer vision techniques in order to
identify and eliminate distracting driving behaviors[2],[3]. However, these
methods face obstacles such as inadequate data labeling, poor data quality,
and low resolution[4, 5].

Naturalistic driving studies or videos provide data on all aspects of the
driver’s actions, including drowsiness and distracted driving, making them a
valuable tool for understanding driver behavior in real-world scenarios[6].
Traditional machine learning approaches have been used in previous studies to
present various driver distraction activity analyses and feature extraction
methods[7],[8]. For example, Braunagel et al. proposed using a Support Vector
Machine (SVM) model to recognize driver activity using five contextual
features: saccades, fixations, blink, head position, and rotation[9, 10].
Similarly, Liang et al. used an SVM model and a logistic regression model to
identify driver cognitive distractions in real-time using driver eye movement
and vehicle dynamic data [11]. Also, in recent years, deep learning approaches
have also been used in recent years for activity analysis and feature
extraction in driver distraction detection. Vijayan., for example, proposed a
deep convolutional neural network (CNN) architecture for detecting driver
drowsiness based on features extracted from the driver’s face, such as eye,
mouth, and brow movements[12, 13, 14]. Similarly, Omerustaoglu et al.[15] used
a deep neural network (DNN) to detect driver distraction using features
extracted from the driver’s face, arms, and hands movements in detecting
distracted and non-distracted states. Although these Driver distraction
detection systems have shown promising results in identifying anomalous
driving events using traditional machine learning approaches and deep learning
such as activity analysis and feature extraction. However, due to the
complexity and dynamic nature of driving behavior, more research is required
to investigate the generalization and scalability of these approaches across a
wide range of driving conditions and environments.

Due to the complexity and dynamic nature of driving behavior, identifying
anomalous driving events in these videos is difficult. In response to this
difficulty, we present SigSegment, a signal-based segmentation algorithm that
employs pose estimation, signal generation, activity classification using deep
learning techniques to identify anomalous driving events in natural driving
videos. SigSegment uses a deep convolutional neural network (CNN) and long
short-term memory (LSTM) architecture to classify anomalous driving events
precisely by estimating the start and end times.

The remainder of the paper is structured as follows. The second section is a
review of relevant literature. Section three contains the data and proposed
methodology used for this study. The fourth section discusses the model
development’s results. Section five concludes with a summary of the findings,
and recommendations for future research.

###  1.1 Objective

The objective of this study is to develop a classification model that
accurately identifies distracted behavior activities executed by drivers
within a given time frame.

##  2 Related Works

Driver distraction is a major concern in transportation safety. In recent
years, researchers have used machine learning and deep learning techniques to
classify driver distraction activities. In the literature, two main methods
have been proposed: the single-frame-based method and the consecutive-
sequence-based method[16, 17]. The single-frame method analyzes a single frame
of a video feed or image and applies machine learning algorithms, such as
convolutional neural networks (CNNs), to classify the driver’s behavior. While
this method has shown high accuracy rates for certain types of distractions,
such as cell phone use, it has limitations when it comes to capturing the
temporal aspect of driver behavior. Several studies have been conducted to
investigate the efficacy of the single-frame-based method in detecting
different types of driver distraction using only a single image or video
frame. Lee et al.[18], for example, proposed a method for detecting aggressive
driving using CNN. Near-infrared (NIR) light and thermal camera sensors were
used to capture the driver’s face, and the CNN achieved a high accuracy rate
of 99.95%. Similarly, Guo et al. [19] proposed a single-frame hybrid of
convolutional neural network (CNN) and long short-term memory (LSTM)-based
driver drowsiness detection system. CNN was trained to recognize drowsy facial
features like drooping eyelids and yawning and achieved a high accuracy rate
in classifying drowsy and alert states using only a single frame of the
driver’s face. Liang et al. [20] proposed a real-time system for detecting
driver cognitive distraction based on a single-frame Bayesian network in
another study. The network was trained to model the relationship between the
driver’s eye movement and driving performance, and it detected cognitive
distraction with an overall accuracy rate of 80.1%. Qu et al. (2020) proposed
a system for detecting driver phone use that was based on a single-frame CNN
that analyzed the driver’s hand and arm positions and achieved a 93.3%
accuracy rate. Furthermore, Zhang et al. (2019) proposed a system for
detecting driver smoking based on a single-frame CNN that recognized the
distinctive motion of a smoking hand and achieved 92.3% accuracy[21]. Despite
the single-frame-based method’s demonstrated effectiveness in detecting
various types of driver distraction. It is critical to recognize its
limitations in capturing the temporal aspect of driver behavior, which the
consecutive-sequence-based method may address more effectively by extracting
temporal high-level features from sequential frames.

The consecutive-sequence-based method, on the other hand, entails analyzing a
continuous sequence of frames or video feed to identify patterns of behavior
over time. This method, which typically employs recurrent neural networks
(RNNs) and other time-series analysis techniques, has been demonstrated to be
effective in identifying more complex types of driver distraction activities,
such as touching the radio, eating or drinking while driving[22]. Sun et al.
[23] proposed a method for detecting driver cognitive distraction using an
RNN-based approach in one study. To detect cognitive distraction, the authors
used the RNN’s attention mechanism to focus on important regions of the
driver’s face, such as the eyes and mouth. The proposed method detected
cognitive distraction with an accuracy rate of 90.64%. Ed-Doughmi et al.[24]
proposed a system for detecting driver phone use based on a consecutive-
sequence-based approach in another study. To detect phone use, the system used
a two-stream RNN to analyze both the driver’s hand and face movements. The
proposed method detected phone use with an accuracy rate of 92.1%. Similarly,
Bai et al.[25] proposed a method for detecting driver drowsiness based on
consecutive frames of the driver’s face in their study. The authors achieved
an accuracy rate of 93.4% by using a two-stream Graph CNN to analyze the
temporal changes in facial features associated with drowsiness, such as eye
closure and head nodding[26]. Because of the rapid increase in the number of
researchers and techniques, the accuracy of human driver distraction activity
recognition has significantly improved. However, due to several issues such as
inadequate labeling, poor data quality, low resolution, large intra-class
variability, indistinct boundaries between classes, varying viewpoints,
occlusions, appearance variations, influence of environmental factors, and
recording settings, this task remains difficult[27, 28]. These difficulties
are exacerbated when dealing with naturalistic driving videos.

In this study, we propose we propose a Signal-Based anomaly detection
algorithm that segments videos into anomalies and non-anomalies using a deep
CNN-LSTM classifier to precisely estimate the start and end times of an
anomalous driving event.

##  3 Method

This section describes the dataset and algorithm framework used in this study.
Section 3.1, in particular, introduces the dataset used. The video pre-
processing and segmentation based on the algorithm, the CNN frameworks, as
well as the LSTM framework, are described in Section 3.2

###  3.1 Dataset

The dataset was provided by AI CITY CHALLENGE 2023. It includes 210 video
clips captured by 35 drivers for a total of approximately 34 hours. The
drivers performed 16 random tasks, such as talking on the phone, eating, and
reaching back, which were recorded simultaneously by three cameras mounted in
the car from various angles. Each driver performed the data collection tasks
twice: once without any appearance block such as a hat or sunglasses, and once
with such a block. This resulted in 6 videos per driver, with 3 synchronized
without an appearance block and 3 with an appearance block. The 34 hours of
video footage was divided into three datasets, labeled A1, A2, and B,
containing 25, 5, and 5 drivers, respectively. The A1 dataset contains
manually annotated ground truth labels for the start time, end time, and type
of distracted behavior. The dataset A2 contains no labels and Dataset B is for
testing.

###  3.2 The Proposed Framework

The proposed framework for the Naturalistic Driving Action Recognition
consists of several steps, beginning with video data input, pose estimation,
signal generation, activity classification and postprocessing as shown in
Figure 1.

Posture Estimation. Posture estimation is the process of determining the
position and orientation of the driver’s body. This information is important
for identifying unusual driving behaviors, as changes in posture may indicate
that the driver is becoming distracted or fatigued. To estimate the driver’s
posture from the video, we find the mean $\bar{X}$ of all frames in the video,
where $X_{i}$ denotes the posture of the driver in the $i$-th frame (see
Equation 1). The assumption is that the normal driving posture $\bar{X}$ is
the most frequent and probable driver activity in any driving section.

$\bar{X}=\frac{1}{n}\sum_{i=1}^{n}X_{i}$ (1)

where $n$ is the total number of frames in the video.

Signal Generation. The estimated posture is subtracted from each frame in the
video, yielding an image that is flattened and its pixel intensities summed as
shown in Algorithm 1. The resulting summation values serve as a quantitative
measure of how different each frame is from the expected normal posture.
Specifically, frames exhibiting close adherence to the expected posture will
have small summation values, while those deviating from the expected posture
will have large values. This usually results in a spike when plotted. Frames
corresponding to the spike are considered to potentially indicate an anomaly.

Algorithm 1 Anomaly Detection based on Posture Estimation

1:procedure DetectAnomalies($X_{1},X_{2},...,X_{n},\hat{X},k$)

2: $A\leftarrow\varnothing$

3: for $i\leftarrow 1$ to $n$ do

4: $Y_{i}\leftarrow X_{i}-\hat{X}$

5: $V_{i}\leftarrow\sum_{j=1}^{p}Y_{i,j}$ $\triangleright$ Flatten and sum
pixel intensities

6: end for

7: $m\leftarrow\mathrm{median}(V_{1},V_{2},...,V_{n})$ $\triangleright$
Compute median

8: $S\leftarrow\mathrm{std}(V_{1},V_{2},...,V_{n})$ $\triangleright$ Compute
standard deviation

9: $\textit{thresh}\leftarrow m+k\cdot S$ $\triangleright$ Set anomaly
detection threshold

10: for $i\leftarrow 1$ to $n$ do

11: if $V_{i}>\textit{thresh}$ then

12: $A\leftarrow A\cup{X_{i}}$ $\triangleright$ Add potential anomaly to set
$A$

13: end if

14: end for

15: return $A$

16:end procedure

Classification. The classification model consists of two components: a
convolutional neural network (CNN) to extract information from the image
sequence, and a long short-term memory (LSTM) component to learn the temporal
relationship between the frames in the input sequence. The results from the
LSTM is passed through a fully connected neural network for the
classification.

Figure 1: The Framework of the proposed Sigsegment CNN-LSTM model

Postprocessing. The postprocessing step involves preparing the classified
anomalies into the format required by the evaluation system.

##  4 Results and Discussions

The performance of our proposed model was assessed based on its ability to
detect anomalies in driver distraction videos. Track 3 was evaluated based on
the performance of model activity identification, as measured by the average
activity overlap score, which is defined as follows. Given a ground-truth
activity g with start time gs and end time ge, the closest predicted activity
match is that predicted activity p of the same class as g and highest overlap
score os, with the additional condition that start time ps and end time pe are
in the range [gs – 10s, gs + 10s] and [ge – 10s, ge + 10s], respectively. The
overlap between g and p is defined as the proportion of the time intersection
to the time union of the two activities.

$os(p,g)=\frac{\max(\min(ge,pe)-\max(gs,ps),0)}{\max(ge,pe)-\min(gs,ps)}$ (2)

With an overlap score of 0.5424, our proposed model was ranked ninth in the AI
City Challenge 2023. The top-performing teams from the challenge’s public
leaderboard are shown in Table 1. Our findings indicate that our proposed
model can effectively detect driver distraction videos with anomalies, as
evidenced by its F1score performance. Further enhancements can be made by
experimenting with different evaluation metrics and optimizing the model’s
architecture.

Rank | TeamID | Team Name | Score
---|---|---|---
1 | 209 | Meituan-loTCV | 0.7416
2 | 60 | JNU_boat | 0.7041
3 | 49 | ctc-AI | 0.6723
4 | 118 | RW | 0.6245
5 | 8 | Purdue Digital Twin Lab | 0.5921
6 | 48 | BUPT-MCPRL | 0.5907
7 | 83 | DiveDeeper | 0.5881
8 | 217 | INTELLI_LAB | 0.5426
9 | 152 | AILAB | 0.5424
10 | 11 | AIMIZ | 0.5409

##  5 Conclusion and Futureworks

In conclusion, this paper proposes a Signal-Based anomaly detection algorithm
designed to detect distracted driving behavior, which poses a significant
threat to road safety. In the phase of anomaly detection and analysis, the
proposed method employs driver pose background estimation, mask extraction,
and signal activity spikes, which increases the accuracy of identifying
anomalous driving events. Moreover, a Deep CNN-LSTM classifier was applied to
candidate anomalies for accurate detection and analysis of final anomalies.
The experimental validation of the proposed method in the AI City Challenge
2023 demonstrated its efficacy, with an overlap score of 0.5424 and a ranking
of ninth among other competitors. These results demonstrate the potential of
applying deep learning techniques, in particular CNN-LSTM, to effectively
detect and analyze anomalous driving behavior. Future research could
investigate the use of more sophisticated CNN-LSTM architectures or other deep
learning models to enhance the detection and analysis of driving anomalies. In
addition, the proposed method could be expanded to detect other types of
driver distraction or incorporated into existing advanced driver assistance
systems to further improve road safety.

## References

  * [1] National Center for Statistics and Analysis.  Traffic safety facts 2019: A compilation of motor vehicle crash data.  National Highway Traffic Safety Administration, 2021.
  * [2] Lex Fridman, Daniel E Brown, Michael Glazer, William Angell, Spencer Dodd, Benedikt Jenik, Jack Terwilliger, Aleksandr Patsekin, Julia Kindelsberger, Li Ding, et al.  Mit advanced vehicle technology study: Large-scale naturalistic driving study of driver behavior and interaction with automation.  IEEE Access, 7:102021–102038, 2019.
  * [3] Mohan Manubhai Trivedi, Tarak Gandhi, and Joel McCall.  Looking-in and looking-out of a vehicle: Computer-vision-based enhanced vehicle safety.  IEEE Transactions on Intelligent Transportation Systems, 8(1):108–120, 2007.
  * [4] Imen Jegham, Anouar Ben Khalifa, Ihsen Alouani, and Mohamed Ali Mahjoub.  Vision-based human action recognition: An overview and real world challenges.  Forensic Science International: Digital Investigation, 32:200901, 2020.
  * [5] Maged Shoman, Armstrong Aboah, Alex Morehead, Ye Duan, Abdulateef Daud, and Yaw Adu-Gyamfi.  A region-based deep learning approach to automated retail checkout.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 3210–3215, 2022.
  * [6] Thomas A Dingus, Feng Guo, Suzie Lee, Jonathan F Antin, Miguel Perez, Mindy Buchanan-King, and Jonathan Hankey.  Driver crash risk factors and prevalence evaluation using naturalistic driving data.  Proceedings of the National Academy of Sciences, 113(10):2636–2641, 2016.
  * [7] Björn Fröhlich, Markus Enzweiler, and Uwe Franke.  Will this car change the lane?-turn signal recognition in the frequency domain.  In 2014 IEEE Intelligent Vehicles Symposium Proceedings, pages 37–42. IEEE, 2014.
  * [8] Stephanie Lefevre Lefevre, Mathias Perrollaz Perrollaz, Christian Laugier Laugier, and Puneet Kumar Kumar.  Learning-based approach for online lane change intention prediction.  2013\.
  * [9] Christian Braunagel, Enkelejda Kasneci, Wolfgang Stolzmann, and Wolfgang Rosenstiel.  Driver-activity recognition in the context of conditionally autonomous driving.  In 2015 IEEE 18th International Conference on Intelligent Transportation Systems, pages 1652–1657. IEEE, 2015.
  * [10] Armstrong Aboah, Yaw Adu-Gyamfi, Senem Velipasalar Gursoy, Jennifer Merickel, Matt Rizzo, and Anuj Sharma.  Driver maneuver detection and analysis using time series segmentation and classification.  Journal of Transportation Engineering, Part A: Systems, 149(3):04022157, 2023.
  * [11] Yulan Liang, Michelle L Reyes, and John D Lee.  Real-time detection of driver cognitive distraction using support vector machines.  IEEE transactions on intelligent transportation systems, 8(2):340–350, 2007.
  * [12] Vineetha Vijayan and Elizabeth Sherly.  Real time detection system of driver drowsiness based on representation learning using deep neural networks.  Journal of Intelligent & Fuzzy Systems, 36(3):1977–1985, 2019\.
  * [13] Armstrong Aboah, Abdul Rashid Mussah, and Yaw Adu-Gyamfi.  Ai-based framework for understanding car following behaviors of drivers in a naturalistic driving environment.  arXiv preprint arXiv:2301.09315, 2023.
  * [14] Armstrong Aboah, Bin Wang, Bagci Ulas, and Yaw Adu-Gyamfi.  Real-time multi-class helmet violation detection using few-shot data sampling technique and yolov8.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR) Workshops, June 2023.
  * [15] Furkan Omerustaoglu, C Okan Sakar, and Gorkem Kar.  Distracted driver detection by combining in-vehicle and image data using deep learning.  Applied Soft Computing, 96:106657, 2020.
  * [16] Chaopeng Pan, Haotian Cao, Weiwei Zhang, Xiaolin Song, and Mingjun Li.  Driver activity recognition using spatial-temporal graph convolutional lstm networks with attention mechanism.  IET Intelligent Transport Systems, 15(2):297–307, 2021.
  * [17] Armstrong Aboah, Bagci Ulas, Rashid Mussah Abdul, Jakisa Owor Neema, and Yaw Adu-Gyamfi.  Deepsegmenter: Temporal action localization for detecting anomalies in untrimmed naturalistic driving videos.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR) Workshops, June 2023.
  * [18] Kwan Woo Lee, Hyo Sik Yoon, Jong Min Song, and Kang Ryoung Park.  Convolutional neural network-based classification of driver’s emotion during aggressive and smooth driving using multi-modal camera sensors.  Sensors, 18(4):957, 2018.
  * [19] Jing-Ming Guo and Herleeyandi Markoni.  Driver drowsiness detection using hybrid convolutional neural network and long short-term memory.  Multimedia tools and applications, 78:29059–29087, 2019.
  * [20] Siming Liang, Ya Wei, Zehong Wu, and Will Hansen.  Performance evaluation of concrete pavement slab considering creep effect by finite element analysis.  Transportation Research Record, 2672(27):65–77, 2018.
  * [21] Armstrong Aboah.  A vision-based system for traffic anomaly detection using deep learning and decision trees.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 4207–4212, 2021.
  * [22] Eduardo Carvalho, Bruno V Ferreira, Jair Ferreira, Cleidson De Souza, Hanna V Carvalho, Yoshihiko Suhara, Alex Sandy Pentland, and Gustavo Pessin.  Exploiting the use of recurrent neural networks for driver behavior profiling.  In 2017 International Joint Conference on Neural Networks (IJCNN), pages 3016–3021. IEEE, 2017.
  * [23] Qinyu Sun, Chang Wang, Yingshi Guo, Wei Yuan, and Rui Fu.  Research on a cognitive distraction recognition model for intelligent driving systems based on real vehicle experiments.  Sensors, 20(16):4426, 2020.
  * [24] Younes Ed-Doughmi, Najlae Idrissi, and Youssef Hbali.  Real-time system for driver fatigue detection based on a recurrent neuronal network.  Journal of imaging, 6(3):8, 2020.
  * [25] Jing Bai, Wentao Yu, Zhu Xiao, Vincent Havyarimana, Amelia C Regan, Hongbo Jiang, and Licheng Jiao.  Two-stream spatial–temporal graph convolutional networks for driver drowsiness detection.  IEEE Transactions on Cybernetics, 52(12):13821–13833, 2021.
  * [26] Armstrong Aboah, Michael Boeding, and Yaw Adu-Gyamfi.  Mobile sensing for multipurpose applications in transportation.  arXiv preprint arXiv:2106.10733, 2021.
  * [27] Manoj Ramanathan, Wei-Yun Yau, and Eam Khwang Teoh.  Human action recognition with video data: research and evaluation challenges.  IEEE Transactions on Human-Machine Systems, 44(5):650–663, 2014\.
  * [28] Armstrong Aboah and Yaw Adu-Gyamfi.  Smartphone-based pavement roughness estimation using deep learning with entity embedding.  Advances in Data Science and Adaptive Analysis, 12(03n04):2050007, 2020.