## Noname manuscript No.

(will be inserted by the editor)

## On the geometric analysis of a quartic-quadratic optimization problem under a spherical constraint

Haixiang Zhang · Andre Milzarek · Zaiwen Wen · Wotao Yin

Received: date / Accepted: date

Abstract This paper considers the problem of solving a special quartic-quadratic optimization problem with a single sphere constraint, namely, finding a global and local minimizer of 1 2 z ∗ A z + β 2 ∑ n k =1 | z k | 4 such that ‖ z ‖ 2 = 1 . This problem spans multiple domains including quantum mechanics and chemistry sciences and we investigate the geometric properties of this optimization problem. Fourth-order optimality conditions are derived for characterizing local and global minima. When the matrix in the quadratic term is diagonal, the problem has no spurious local minima and global solutions can be represented explicitly and calculated in O n ( log n ) operations. When A is a rank one matrix, the global minima of the problem are unique under certain phase shift schemes. The strict-saddle property, which can imply polynomial time convergence of second-order-type algorithms, is established when the coefficient β of the quartic term is either at least O n ( 3 / 2 ) or not larger than O (1) . Finally, the KurdykaŁojasiewicz exponent of quartic-quadratic problem is estimated and it is shown that the exponent is 1 / 4 for a broad class of stationary points.

H Zhang is partly supported by the elite undergraduate training program of School of Mathematical Sci-. ences in Peking University. Z . Wen is supported in part by the NSFC grants 11831002 and 11421101. A . Milzarek is partly supported by the Fundamental Research Fund - Shenzhen Research Institute for Big Data (SRIBD) Startup Fund jcyj-am20190601.

## Haixiang Zhang

School of Mathematical Sciences, Peking University, CHINA

E-mail: 1500010620@pku.edu.cn

## Andre Milzarek

Institute for Data and Decision Analytics, Chinese University of Hong Kong, Shenzhen, CHINA E-mail: andremilzarek@cuhk.edu.cn

## Zaiwen Wen

Beijing International Center for Mathematical Research, Peking University, CHINA E-mail: wenzw@pku.edu.cn

## Wotao Yin

Department of Mathematics, University of California, Los Angeles, CA E-mail: wotaoyin@math.ucla.edu

Keywords Constrained quartic-quadratic optimization · Geometric analysis · Strict-saddle property · Łojasiewicz inequality

Mathematics Subject Classification (2010) 15A45 · 47H60 · 58K30 · 58C40 · 90C26

## 1 Introduction

In this paper, we analyze the geometric properties of the following nonconvex quarticquadratic problem under a single spherical constraint,

$$( 1. 1 ) \quad \min _ { z \in \mathbb { C } ^ { n } } f ( z ) = \frac { 1 } { 2 } z ^ { * } A z + \frac { \beta } { 2 } \sum _ { k \in [ n ] } | z _ { k } | ^ { 4 } \text{ s.t.} \quad \| z \| _ { 2 } = 1,$$

where β &gt; 0 is a fixed interaction coefficient and A ∈ C n × n is a given Hermitian matrix. An important class of applications of this type is the so-called Bose-Einstein condensation (BEC) problem, which has attracted great interests in the atomic, molecule and optical physics community and in the condense matter community. Utilizing a proper non-dimensionalization and discretization, the BEC problem can be rewritten as a quartic-quadratic minimization problem of the form (1.1), where the matrix A corresponds to the sum of the discretized Laplace operator and a diagonal matrix. If a non-rotating BEC problem is considered, then the variable z can be restricted to the real space R n and problem (1.1) becomes a real optimization problem. For a more detailed setup of the BEC problem and its specific mathematical formulation, we refer to [38,11,66].

Our interest in problem (1.1) and its geometric properties is primarily triggered by related numerical results and observations with Bose-Einstein condensates and Kohn-Shamdensity functional calculations, see, e.g., [79,41,80,32], and is motivated by recent landscape results for matrix completion [36,77,35], phase retrieval [73,24], phase synchronization [10,17,54], and quadratic programs with spherical constraints [31,53]. Understanding the geometric landscape of the nonconvex optimization problem (1.1) is a fundamental step towards understanding and explaining the global and local behavior of the problem and the performance of associated algorithms. Despite recent progress on the geometric properties of nonconvex minimization problems and due to the complex interaction of the quadratic and quartic terms, the landscape of (1.1) is still elusive. We further note that in [40], Hu et al. have shown that the minimization problem (1.1) can be interpreted as a special instance of the partition problem and thus, it is generally NP-hard to solve (1.1).

## 1.1 Related Work and Geometric Concepts

Although nonconvex optimization problems are generally NP-hard, [61], direct and traditional minimization approaches, such as basic gradient and trust region schemes, can still be applied to solve certain and important classes of nonconvex problems with astonishing success - and they remain the methods of choice for the practitioner

- [17]. A recent and steadily growing area of research concentrates on the identification of such classes of problems and tries to close the discrepancy between theoretical results and numerical performances, see, e.g., [72,43,26] for an overview. Herein geometric observations and techniques play a major role in understanding the landscape and the global and local behavior of a nonconvex problem and of associated algorithms. Specifically, we are interested in the following geometric properties:
- ( P 1 ) All local minimizers are also global solutions, i.e., there are no spurious local minimizers.
- ( P 2 ) The objective function possesses negative curvature directions at all saddle points and local maximizers which allows to effectively escape those points.

Condition ( P 2 ) is the basis of the so-called strict-saddle property and was introduced in [34,73,35]. The strict-saddle and other related conditions can be used in the convergence analysis and in the design of algorithms to efficiently avoid saddle points. For instance, Sun, Qu, and Wright [76] established a polynomial-time convergence rate of a Riemannian trust region method that is tailored to solve phase retrieval problems which satisfy the strict-saddle property. Furthermore, in [49,64,48] it is shown that certain randomly initialized first-order methods can converge to local minimizers and escape saddle points almost surely if the strict-saddle property holds. In the following, we briefly review recent classes of nonconvex optimization problems for which the conditions ( P 1 ) , ( P 2 ) , or other desirable geometric properties are satisfied.

The generalized phase retrieval (GPR) problem is a popular nonconvex problem which has seen remarkable progress these years, see, e.g., [42,70] for an overview. Classical methods that transform the GPR problem into a convex program include convex relaxation techniques [19,21,25] and Wirtinger flow algorithms with carefullydesigned initialization [20]. Phase retrieval problems are typically formulated as a quartic and unconstrained least squares problem depending on m measurements y k = | a z ∗ k | , k = 1 , ..., m . Traditional GPR methods can recover the true signal z from the measurements as long as the sample size m satisfies m /greaterorapproxeql n or m /greaterorapproxeql n log n where n is the dimension of the signal. A provable convergence rate for a randomly initialized trust region-type algorithm is given in [73] as long as m /greaterorapproxeql n log 3 n via showing that all the local minima are global and the strict-saddle property holds. When the signal and observations are real, the convergence rate of the vanilla gradient descent method is established by Chen et al. [24] under the assumption m /greaterorapproxeql n log 13 n . Another interesting class of amenable nonconvex problems are low-rank matrix factorization problems. Classical methods for matrix factorization are based on nuclear norm minimization [22,68] and are usually memory intensive or require long running times. In [44,45], Keshavan, Montanari, and Oh showed that the well-initialized gradient descent method can recover the ground truth of those problems. A strong convexity-type property is proved to hold around the optimal solution by Sun and Luo in [77] and the objective function is shown to be sharp and weakly convex in nonsmooth settings by Li et al., [51]. Further, the strict-saddle property for the low-rank matrix factorization problem is established in [35,36], as well as for other low rank problems such as robust PCA and matrix sensing. Other classes of nonconvex optimization problems with provable convergence or geometric properties comprise orthogonal tensor decomposition [34,37], complete dictionary learning [5,74,75], phase synchroniza-

tion and community detection [10,17,54] and shallow neural networks [52]. There are also several numerical methods that work well in practice for solving the BEC problem (e.g., tools for numerical partial differential equation [3,29] or optimization methods [33,40,80]), but their geometric properties are not known.

So far the mentioned concepts allow to cover global structures and landscapes. Instead, local properties and the local behavior of (1.1) can be captured by the so-called Kurdyka-Łojasiewicz (KL), [47], or Łojasiewicz inequality, [55]. The Łojasiewicz inequality is a useful tool to estimate the convergence rate of first-order iterative methods in the nonconvex setting [1,59,69]. Moreover, the convergence rate of first-order methods satisfying a certain line-search criterion and descent condition can be derived via the KL inequality, [6,15,69], where the rate depends on the KL exponent θ . However, there is no general method to determine or estimate the KL exponent of specific optimization problems, though the existence of the KL exponent is guaranteed in many situations. For optimizing a real analytic function over a compact real analytic manifold (such as problem (1.1)), the existence of the KL exponent is established by Łojasiewicz in [55]. There are also several few works that derive explicit estimates of the KL exponent for certain structured problems, such as general polynomials [39,27,81], convex problems [50], non-convex quadratic optimization problems with simple convex constraints [30,50,56,57], and quadratic optimization problems with single spherical constraint [31,53]. Obviously, the above four cases do not cover our constrained quartic-quadratic optimization problem (1.1).

## 1.2 Contributions

In this work, we investigate different geometric concepts for the quadratic-quartic optimizations problem (1.1) and give theoretical explanations why first- and secondorder methods can perform well on it. In section 2, we first derive several new secondand fourth-order optimality conditions for problem (1.1) that can be utilized to characterize local and global solutions. These conditions capture fundamental geometric properties of stationary points and local minima and form the basis of our geometric analysis. We then investigate problem (1.1) in the special case where A is a diagonal matrix. In this situation, we show that a complete characterization of the landscape can be obtained and that problem (1.1) does not possess any spurious local minima. Furthermore, global solutions can be computed explicitly using a closed-form expression that involves the projection onto an n -simplex which requires O n ( log n ) operations. These results can be partially extended to the case where A is a rank-one matrix and we can prove uniqueness of global minima up to a certain phase shift. In general, the complex interplay between the quartic and quadratic terms impedes the derivation of explicit expressions for stationary points and local minima and complicates the landscape analysis of f significantly. However, if either the quartic or the quadratic term dominates the objective function, we can establish the strict-saddle property ( P 2 ) and identify and calculate the location and number of local minima. Our methodology is based on a careful discussion of the quartic and quadratic terms for large and small interaction coefficients that is applicable for general deterministic and arbitrary choices of A . We note that previous works and results

only cover fourth-order unconstrained optimization problems (e.g., phase retrieval), quadratic constrained optimization problems (e.g., matrix completion and phase synchronization), or fourth-order constrained optimization problems without quadratic terms (e.g., fourth-order tensor decomposition). In particular, there is no interaction between quartic and quadratic terms and between their Riemannian derivatives. Different from most nonconvex problems discussed in the literature, our problem does not have a natural probabilistic framework and thus, probabilistic techniques such as concentration inequalities can not be directly applied.

In addition, we estimate the KL exponent and establish a Riemannian Łojasiewicztype inequality for problem (1.1). Again, the presence of the quartic term considerably complicates the theoretical analysis. In order to deal with the high-order terms appearing in the Taylor expansion, we first separate the nonzero and zero components of a stationary point in order to facilitate the discussion of the leading terms. Then we divide the proof into several cases corresponding to different leading terms. The appearance of the quartic term requires the third-order and the fourth-order terms in the Taylor expansion to fully describe the local behavior, rather than merely the secondorder terms. Due to the additional terms, the number of possible leading terms is significantly increased and we carefully analyze the relationship between those different terms. If the matrix A is diagonal, we show that the Łojasiewicz inequality holds at every stationary point of (1.1) with exponent θ = 1 4 . Moreover, this result can be extended to more general choices of A , if the problem is restricted to the real space and positive semi-definiteness of the stationary certification matrix is assumed. The proof is based on the diagonal case and on estimates of the local behavior of the objective function and the Riemannian gradient in different subspaces. The positive semi-definiteness assumption is utilized throughout the proof to handle the non-isolated case and can not be easily removed. Although this additional condition represents a stronger notion of global optimality, a wide range of global minima in the real case satisfy this condition. To the best of the authors' knowledge, our work is the first to estimate and analyze these properties for quadratic-quartic optimization problems over a single sphere.

## 1.3 Organization and notations

This paper is organized as follows. In section 2, we present second- and fourth-order optimality conditions and characterize global minimizer of problem (1.1). Next, in section 3 and section 4, we consider two special cases and investigate geometric properties of problem (1.1) when A is either diagonal or has rank one. General landscape results for the real case are discussed in section 5. Finally, in section 6, we estimate the KL exponent of problem (1.1).

For n ∈ N , we define [ n ] := { 1 , ..., n } and for z ∈ C n , we set ‖ z ‖ = ‖ z ‖ 2 = √ z z ∗ . Let S n -1 and CS n -1 denote the n -dimensional real and complex sphere, respectively. In the following sections, we will use the notation M = S n -1 or M = CS n -1 depending on whether we consider the real or the complex case. The tangent space of CS n -1 at a point z ∈ CS n -1 is given by T M z := { v ∈ C n : /Rfractur ( v z ∗ ) = 0 } . For z ∈ C n , diag( z ) is a diagonal matrix with diagonal entries z , ..., z 1 n and we use

| z | 2 to denote the component-wise absolute value, | z | 2 = z /circledot ¯ z , of z . We use I to denote the ( n × n ) identity matrix. The Euclidean and corresponding Riemannian gradient of f at z on M are denoted by ∇ f ( z ) and grad f ( z ) . Similarly, ∇ 2 f ( z ) and Hess f ( z ) represent the Euclidean and Riemannian Hessian, respectively.

Throughout this paper and without loss of generality we will assume that the matrix A is positive definite. Furthermore, A = PΛP ∗ is an associated eigenvalue decomposition of the Hermitian matrix A with λ 1 ≥ λ 2 ≥ ... ≥ λ n &gt; 0 , Λ = diag( λ , ..., λ 1 n ) , P = ( p 1 , ..., p n ) ∈ C n × n , and P P ∗ = I .

## 2 Wirtinger Calculus and Optimality Conditions

Since the real-valued objective function f is nonanalytic in z , we utilize the Wirtinger calculus [46,71] to express the complex derivatives of f . Specifically, the Wirtinger gradient and Hessian of f are defined as

$$\dots \dots \dots \dots \dots \dots \dots \dots \dots \\ \nabla f ( z ) \coloneqq \begin{bmatrix} \nabla _ { z } f \\ \nabla _ { \bar { z } } f \end{bmatrix}, \quad \nabla ^ { 2 } f ( z ) \coloneqq \begin{bmatrix} \frac { \partial } { \partial \bar { z } } ( \frac { \partial f } { \partial \bar { z } } ) ^ { * } & \frac { \partial } { \partial \bar { z } } ( \frac { \partial f } { \partial \bar { z } } ) ^ { * } \\ \frac { \partial } { \partial \bar { z } } ( \frac { \partial f } { \partial \bar { z } } ) ^ { * } & \frac { \partial } { \partial \bar { z } } ( \frac { \partial f } { \partial \bar { z } } ) ^ { * } \end{bmatrix}, \\ \text{re} \, \nabla _ { z } f ( z ) \coloneqq ( \partial f / \partial \bar { z } ) ^ { * }, \nabla _ { \bar { z } } f ( \bar { z } ) \coloneqq ( \frac { \partial f / \partial \bar { z } ) ^ { * } } { \frac { \partial } { \partial \bar { z } } } ( \frac { \partial f } { \partial \bar { z } } ) ^ { * } \end{bmatrix},$$

$$\nabla ^ { 2 } f ( \mathbf z ) = \begin{bmatrix} \frac { 1 } { 2 } A + 2 \beta \text{diag} ( | \mathbf z | ^ { 2 } ) & \beta \text{diag} ( z _ { 1 } ^ { 2 }, \dots, z _ { n } ^ { 2 } ) \\ \beta \text{diag} ( \bar { z } _ { 1 } ^ { 2 }, \dots, \bar { z } _ { n } ^ { 2 } ) & \frac { 1 } { 2 } \bar { A } + 2 \beta \text{diag} ( | \mathbf z | ^ { 2 } ) \end{bmatrix}. \\ \mathbb { m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m
 \mathcal { T M M } = \mathcal { T M } = \mathcal { T M } n \dots + \mathcal { = } T = \mathcal { \partial } n$$

where ∇ z f ( z ) := ( ∂f/∂ z ) ∗ , ∇ ¯ z f (¯) := ( z ∂f/∂ ¯) z ∗ and following [80], we obtain ∇ f z ( z ) = 1 2 A z + β diag( | z | 2 ) z , ∇ ¯ z f (¯) = z ∇ f z ( z ) , and

Furthermore, using the identification T M ≡ { z v v , ¯ ∈ C n : z v ∗ + ¯ z T ¯ = 0 v } , the Riemannian gradient and Hessian of f are given by

$$( 2. 1 ) \quad & \quad \text{grad} f ( z ) = \nabla f ( z ) - \lambda \left [ \bar { z } \right ] \quad \text{and} \quad \text{Hess} f ( z ) = \nabla ^ { 2 } f ( z ) - \lambda I _ { 2 n }, \\ \dots \dots \vee \quad \_ * \vee \ \varepsilon / \vee \ \ 1 \_ * \ v \_ + \ \partial \| _ { - 1 } \| 4 \_ = \ \mathfrak { m } _ { 1 } \dots \dots \varepsilon \ \varepsilon \dots \varepsilon \ \varepsilon \ \varepsilon \ \varepsilon \ \varepsilon \ \varepsilon \ \varepsilon \ \varepsilon \ \varepsilon \ \varepsilon \ \varepsilon \ \varepsilon \ \varepsilon \ \varepsilon \ \varepsilon \ \varepsilon \ \varepsilon \ \varepsilon \ \varepsilon \ \varepsilon \ \varepsilon \ \varepsilon \ \varepsilon \ \varepsilon \ \varepsilon \ \varepsilon \ \varepsilon \ \varepsilon \ \varepsilon \ \varepsilon \ \varepsilon \ \varepsilon \ \varepsilon \ \varepsilon \ \nolimits$$

where λ = z ∗ ∇ z f ( z ) = 1 2 z ∗ A z + β ‖ z ‖ 4 4 ∈ R , see, e.g., [2, Section 3.6 and 5.5]. Let us notice that grad f and Hess f coincide with the standard gradient and Hessian of the Lagrangian L ( z , µ ) = f ( z z , ¯) -µ 2 (¯ z T z -1) when choosing µ = λ . Exploiting the symmetry in grad f , the associated first-order optimality conditions for (1.1) now take the form:

$$( 2. 2 ) \quad \text{grad} f ( z ) & = 0 \quad \Longleftrightarrow \quad [ A + 2 \beta \text{diag} ( | z | ^ { 2 } ) ] z = 2 \lambda z. \\ \ell \quad \cdot \cdot \cdot \quad - \varepsilon \quad \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \colon$$

$$\text{problem} \, ( I. I ). \, & \text{We define the curvature of $f$ at $z$ along a direction $v\in \mathbb{U}^{\prime}$ via} \\ H _ { f } ( z ) [ v ] \coloneqq [ v ^ { * } \, v ^ { T } ] \, \text{Hess} \, f ( z ) \left [ \bar { v } \right ] \\ & = v ^ { * } [ A + 4 \beta \, \text{diag} ( | z | ^ { 2 } ) ] \tilde { v } + 2 \beta \cdot \sum _ { k = 1 } ^ { n } \Re ( v _ { k } ^ { 2 } \bar { z } _ { k } ^ { 2 } ) - 2 \lambda \| v \| ^ { 2 } \\ & = v ^ { * } [ A + 2 \beta \, \text{diag} ( | z | ^ { 2 } ) - 2 \lambda I ] \tilde { v } + 4 \beta \cdot \sum _ { k = 1 } ^ { n } \Re ( v _ { k } \bar { z } _ { k } ) ^ { 2 } \\ & \text{In the real case, the latter formulae reduce to grad} \, f ( z ) = [ A + 2 \beta \, \text{diag} ( | z | ^ { 2 } ) ] \tilde { z } - 2 \lambda \tilde { z }, \\ \text{Hess} \, f ( z ) = A + 6 \beta \, \text{diag} ( | z | ^ { 2 } ) - 2 \lambda I _ { n }, \, \text{and} \, H _ { f } ( z ) [ v ] \coloneqq v ^ { T } \text{Hess} \, f ( z ) \tilde { v }.$$

A point z ∈ C n satisfying the conditions (2.2) will be called stationary point of problem (1.1). We define the curvature of f at z along a direction v ∈ C n via

In the real case, the latter formulae reduce to grad f ( z ) = [ A +2 β diag( | z | 2 )] z -2 λ z , Hess f ( z ) = A +6 β diag( | z | 2 ) -2 λI n , and H f ( z )[ v ] := v T Hess f ( z v ) .

## 2.1 Second-Order Optimality Conditions

Due to the analogy of the Riemannian expressions and the Lagrangian formalism, we can apply classical optimality results to describe the second-order optimality conditions of problem (1.1). In particular, by [62, Theorem 12.5 and 12.6] we have:

Lemma 2.1 (Second-Order Necessary and Sufficient Conditions) Suppose that z is a local solution of problem (1.1) . Then, it holds that grad f ( z ) = 0 and we have H f ( z )[ v ] ≥ 0 for all v ∈ T M z . Conversely, if z is a stationary point satisfying grad f ( z ) = 0 and H f ( z )[ v ] &gt; 0 for all v ∈ T M\{ } z 0 , then z is an isolated local minimum of problem (1.1) .

Next, for some z ∈ C n we define the equivalence class

$$[ z ] \coloneqq \{ \mathbf y \in \mathbb { C } ^ { n } \, \colon | y _ { k } | = | z _ { k } |, \ \forall \, k \in [ n ] \}.$$

The following theorem gives a general sufficient condition for a stationary point to be a global minimum of problem (1.1).

Theorem 2.1 Let z ∈ C n be a stationary point of problem (1.1) with corresponding multiplier λ and suppose that the matrix

$$H \coloneqq A + 2 \beta \text{diag} ( | \mathbf z | ^ { 2 } ) - 2 \lambda I \succeq 0$$

is positive semidefinite. Then z is a global minimum and all global minima of problem (1.1) belong to the equivalence class /llbracket z /rrbracket .

Proof Let y ∈ C n be an arbitrary point with ‖ y ‖ = 1 and let us introduce the polar coordinates z i = r e i iθ i , y i = t e i iφ i for r , t i i ≥ 0 , θ , φ i i ∈ [0 , 2 π ] and all i ∈ [ n ] . Using the stationarity condition grad f ( z ) = 0 and ‖ z ‖ = ‖ y ‖ = 1 , it holds that

$$\text{using use staounary common graq } f ( z ) = \upsilon \, \text{and} \, \| z \| = \| y \| = 1, \, \text{noious una} \\ f ( y ) - f ( z ) & = \frac { 1 } { 2 } y ^ { * } A y - \frac { 1 } { 2 } z ^ { * } [ 2 \lambda z - 2 \beta \, \text{diag} ( | z | ^ { 2 } ) z ] + \frac { \beta } { 2 } ( \| y \| _ { 4 } ^ { 4 } - \| z \| _ { 4 } ^ { 4 } ) \\ & = \frac { 1 } { 2 } y ^ { * } H y - \beta y ^ { * } \, \text{diag} ( | z | ^ { 2 } ) y + \frac { \beta } { 2 } ( \| y \| _ { 4 } ^ { 4 } + \| z \| _ { 4 } ^ { 4 } ) \\ ( 2. 5 ) & = \frac { 1 } { 2 } y ^ { * } H y + \frac { \beta } { 2 } \sum _ { k = 1 } ^ { n } [ t _ { k } ^ { 2 } - r _ { k } ^ { 2 } ] ^ { 2 }. \\ \text{Consequently, the positive semidefinieness of } H \, \text{ yields } f ( y ) - f ( z ) \, \geq \, 0 \, \text{ for all} \\ \upsilon \, \in \mathbb { C } ^ { n } \, \text{ with } \| \nu \| = 1. \, \text{Sunpose now that } \upsilon \, \text{ is a global minimum with } \upsilon \, \text{ } \, \| z \|. \, \text{ In}$$

Consequently, the positive semidefiniteness of H yields f ( y ) -f ( z ) ≥ 0 for all y ∈ C n with ‖ y ‖ = 1 . Suppose now that y is a global minimum with y / ∈ /llbracket z /rrbracket . In this case the last sum in the above expression is strictly positive which, together with the positive semi-definiteness of H yields a contradiction.

If problem (1.1) has two different global minimizers y and z with /llbracket y /rrbracket ∩ /llbracket z /rrbracket = ∅ , Theorem 2.1 implies that H can not be positive semidefinite. Moreover, if condition (2.4) holds at a stationary point z , it automatically has to hold at all global minimizers in /llbracket z /rrbracket .

The definiteness condition in Theorem 2.1 can be equivalently rephrased as follows: The multiplier λ associated with z is the minimum eigenvalue of the matrix A + 2 β diag( | z | 2 ) and z is the corresponding eigenvector. Characterizations of

this type are also known for (quadratic) trust-region subproblems and for general quadratic programs with quadratic constraints, see [60,78]. Furthermore, utilizing [18, Theorem 3.1], it can be shown that such an eigenvector z with the stated properties exists under the assumption 0 &lt; β ≤ ( λ n -1 -λ n ) / 8 . In this case, the condition (2.4) is necessary and sufficient for global optimality.

## 2.2 Fourth-order optimality conditions

In the following section, we derive several fourth-order optimality conditions based on a special and finer expansion of the objective function f . In contrast to the sufficient conditions in Theorem 2.1, this allows us to fully characterize global optima. Let z ∈ CS n -1 be an arbitrary stationary point. For v ∈ T M ∩ z CS n -1 and θ ∈ R , we consider the point y = cos( θ ) z +sin( ) θ v ∈ CS n -1 . Using this decomposition in (2.5), we obtain

$$f ( y ) - f ( z ) = \frac { 1 } { 2 } y ^ { * } H y + \frac { \beta } { 2 } \sum _ { k \in [ n ] } \left [ | y _ { k } | ^ { 2 } - | z _ { k } | ^ { 2 } \right ] ^ { 2 }$$

$$& = \frac { \sin ^ { 2 } ( \theta ) } { 2 } \left [ H _ { f } ( \mathbf z ) [ \mathbf v ] + 2 \beta \sin ( 2 \theta ) \cdot \sum _ { k \in [ n ] } ( | v _ { k } | ^ { 2 } - | z _ { k } | ^ { 2 } ) \Re ( \bar { z } _ { k } v _ { k } ) \right ] \\ & \quad + \frac { \beta \sin ^ { 4 } ( \theta ) } { 2 } \left [ \sum _ { k \in [ n ] } [ ( | v _ { k } | ^ { 2 } - | z _ { k } | ^ { 2 } ) ^ { 2 } - 4 \Re ( \bar { z } _ { k } v _ { k } ) ^ { 2 } ] \right ]. \\ & \quad \sim \cdot \quad \pi \nu \cdot \quad \nu \cdot \quad \nu \cdot \quad \nu \nu \cdot \quad \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \prime \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nolimits$$

Defining H 3 ( v ) := β ∑ k ∈ [ n ] ( | v k | 2 - | z k | 2 ) /Rfractur (¯ z k v k ) , H 4 ( v ) := β ∑ k ∈ [ n ] [( | v k | 2 -| z k | 2 ) 2 - /Rfractur 4 (¯ z k v k ) 2 ] and dividing the latter equation by sin 4 ( θ ) , this yields

$$\mathfrak { m } & \mathfrak { m } \tan \\ ( \mathbf z ) = \frac { 1 } { 2 } \mathbf y ^ { * } H \mathbf y + \frac { \beta } { 2 } \sum _ { k \in [ n ] } \left [ | y _ { k } | ^ { 2 } - | z _ { k } | ^ { 2 } \right ] ^ { 2 } \\ & = \frac { \sin ^ { 2 } ( \theta ) } { 2 } \left [ H _ { f } ( \mathbf z ) [ \mathbf v ] + 2 \beta \sin ( 2 \theta ) \cdot \sum _ { k \in [ n ] } ( | v _ { k } | ^ { 2 } - | z _ { k } | ^ { 2 } ) \Re ( \bar { z } _ { k } v _ { k } ) \\ & \quad + \frac { \beta \sin ^ { 4 } ( \theta ) } { 2 } \left [ \sum _ { k \in [ n ] } [ ( | v _ { k } | ^ { 2 } - | z _ { k } | ^ { 2 } ) ^ { 2 } - 4 \Re ( \bar { z } _ { k } v _ { k } ) ^ { 2 } ] \right ]. \\ H _ { 3 } ( \mathbf v ) \, \coloneqq \, \beta \sum _ { k \in [ n ] } ( | v _ { k } | ^ { 2 } - | z _ { k } | ^ { 2 } ) \Re ( \bar { z } _ { k } v _ { k } ), \, H _ { 4 } ( \mathbf v ) \, \coloneqq \, \beta \sum _ { k \in [ n ] } [ ( | v _ { k } | ^ { 2 } \,. \\ \mathcal { D } ( \bar { z } _ { k } v _ { k } ) \, \coloneqq \, \bar { 1 } ) \, \text{and} \, \text{divide the latter equation} \, \mathbf h v \, \sin ^ { 4 } ( \theta ) \, \text{ this yields}$$

$$G ( \mathbf v, \cot ( \theta ) ) = \frac { 2 [ f ( \mathbf y ) - f ( \mathbf z ) ] } { \sin ^ { 4 } ( \theta ) }$$

$$= H _ { f } ( \mathbf z ) [ \mathbf v ] \cdot \cot ^ { 2 } ( \theta ) + 4 H _ { 3 } ( \mathbf v ) \cdot \cot ( \theta ) + 2 [ f ( \mathbf v ) - f ( \mathbf z ) ], \\ \mathbf v \quad, \quad \pi \ \mathbf v \,, \, c \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \end{cases}$$

/negationslash for θ = kπ , k ∈ Z . We first propose necessary and sufficient optimality conditions for z being a local minimum.

Theorem 2.2 (Characterization of Local Optimality) Let z be a stationary point of problem (1.1) . Then z is locally optimal if and only if there exists a constant M &gt; z 0 such that G ( v , t ) ≥ 0 for all v ∈ T M ∩ z CS n -1 and all t such that | t | ≥ M z .

Proof By definition, z is a local minimum if and only if there exists a constant δ z &gt; 0 such that f ( y ) ≥ f ( z ) for all y ∈ B ( z , δ z ) ∩ CS n -1 . Due to ‖ y - ‖ z 2 = 2 -2 cos( θ ) , the condition y ∈ B ( z , δ z ) ∩ CS n -1 is equivalent to y = cos( θ ) z + sin( θ ) v with v ∈ T M ∩ z CS n -1 and cos( θ ) ≥ 1 -δ 2 z / 2 . Moreover, cos( θ ) ≥ 1 -δ 2 z / 2 implies

Consequently, it holds that y ∈ B ( z , δ z ) ∩ CS n -1 if and only if v ∈ T M ∩ z CS n -1 and | cot( θ ) | ≥ M z . Further, by definition of G , the necessary and sufficient conditions for z being a local minima are equivalent to: there exists a constant M &gt; z 0 such that G ( v , t ) ≥ 0 for all v ∈ T M ∩ z CS n -1 and all t such that | t | ≥ M z .

$$- \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \colon \\ | \sin ( \theta ) | \leq \delta _ { z } \sqrt { 1 - \delta _ { z } ^ { 2 } / 4 }, \quad | \cot ( \theta ) | \geq \frac { 1 - \delta _ { z } ^ { 2 } } { \delta _ { z } \sqrt { 1 - \delta _ { z } ^ { 2 } / 4 } } = \colon M _ { z }. \\ \text{Consequently, it holds that $y\in B(z,\delta_{z})\cap \mathbb{CS}^{n-1}$ if and only if $v\in \mathcal{T}_{z}\mathcal{M}\cap \mathbb{CS}^{n-1}$} \\ \text{and} \, | \cot ( \theta \llcorner > M \text{                                                                                                                                                                                                        
                                                                                                                                                                                                        }                                                                                                                                                                                                        \end{$$

Similarly, we can derive the fourth-order global optimality conditions.

Theorem 2.3 (Characterization of Global Optimality) Let z be a stationary point of problem (1.1) . Then z is a global solution if and only if

$$H _ { f } ( \mathbf z ) [ \mathbf v ] & \geq 0, \, 2 H _ { 3 } ( \mathbf v ) ^ { 2 } \leq H _ { f } ( \mathbf z ) [ \mathbf v ] \cdot [ f ( \mathbf v ) - f ( \mathbf z ) ], \quad \forall \, \mathbf v \in \mathcal { T } _ { \mathbf z } \mathcal { M } \cap \mathbb { C } \mathbb { S } ^ { n - 1 }, \\ H _ { 3 } ( \mathbf v ) & = 0, \, H _ { 4 } ( \mathbf v ) \geq 0, \quad \forall \, \mathbf v \in \mathcal { T } _ { \mathbf z } \mathcal { M } \cap \mathbb { C } \mathbb { S } ^ { n - 1 } \, \text{with} \, H _ { f } ( \mathbf z ) [ \mathbf v ] = 0. \\ \div \quad \lambda \, \cdot \, \dots \quad \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \end{array}$$

↦

Proof A stationary point z is a global minimum if and only if f ( y ) ≥ f ( z ) for all y ∈ CS n -1 , which is equivalent to G ( v , t ) ≥ 0 for all t ∈ R and all v ∈ T M∩ z CS n -1 . However, nonnegativity of the (degenerated) quadratic function t → G ( v , t ) = H f ( z )[ v ] t 2 +4 H 3 ( v ) +2[ t f ( v ) -f ( z )] on R is equivalent to the conditions stated in Theorem 2.3.

Finally, we establish fourth-order necessary conditions for local optimality.

Theorem 2.4 (Fourth-Order Necessary Optimality Conditions) Let z be a local minima of problem (1.1) . Then it holds that

```
\begin{cases} H _ { f } ( z ) [ \mathbf v ] \geq 0, \quad \forall \mathbf v \in \mathcal { T } _ { \mathbf z } \mathcal { M } \cap \mathbb { C } \mathbb { S } ^ { n - 1 }, \\ H _ { 3 } ( \mathbf v ) = 0, \ H _ { 4 } ( \mathbf v ) \geq 0, \quad \forall \mathbf v \in \mathcal { T } _ { \mathbf z } \mathcal { M } \cap \mathbb { C } \mathbb { S } ^ { n - 1 } \text{ with } H _ { f } ( \mathbf z ) [ \mathbf v ] = 0, \\ 4 H _ { 3 } ^ { 2 } ( \mathbf v, \mathbf w ) \leq H _ { f } ( \mathbf z ) [ \mathbf w ] H _ { 4 } ( \mathbf v ), \\ \quad \forall \mathbf v, \mathbf w \in \mathcal { T } _ { \mathbf z } \mathcal { M } \cap \mathbb { C } \mathbb { S } ^ { n - 1 } \text{ with } H _ { f } ( \mathbf z ) [ \mathbf v ] = 0, \ H _ { f } ( \mathbf z ) [ \mathbf w ] > 0, \ \mathbf v ^ { * } \mathbf w = 0, \\ \text{where } H _ { 3 } ( \mathbf v, \mathbf w ) = H _ { 3 } ( \mathbf v ) + 2 \beta \sum _ { k \in [ n ] } \Re ( \bar { \mathbf v } _ { k } w _ { k } ) \Re ( \bar { \mathbf v } _ { k } z _ { k } ). \end{cases}
```

Proof Theorem 2.2 implies that there is M &gt; z 0 such that G ( v , t ) ≥ 0 for all v ∈ T M∩ z CS n -1 and | t | ≥ M z . Hence, for fixed v , we have G ( v , t ) = H f ( z )[ v ] t 2 + 4 H 3 ( v ) t +2[ f ( v ) -f ( z )] ≥ 0 for t →±∞ . Thus, it follows H f ( z )[ v ] ≥ 0 and if H f ( z )[ v ] = 0 , it must hold H 3 ( v ) = 0 and 2[ f ( v ) -f ( z )] = H f ( z )[ v ] + H 4 ( v ) = H 4 ( v ) ≥ 0 . Now we prove the last condition. Suppose v and w are two vectors in T M ∩ z CS n -1 satisfying H f ( z )[ v ] = 0 , H f ( z )[ w ] &gt; 0 and v w ∗ = 0 . Let y = cos( θ ) v +sin( ) θ w ∈ T M∩ z CS n -1 , where θ ∈ -[ π, π ] \{ 0 } . We consider the limiting process θ → 0 . Then, due to H f ( z )[ v ] ≥ 0 for all v ∈ T M z , it follows that H f ( z )[ y ] = H f ( z )[ w ] · sin 2 ( θ ) and

$$& \text{where } H _ { 3 } ( \mathbf v, \mathbf w ) = H _ { 3 } ( \mathbf v ) + 2 \beta \sum _ { k \in [ n ] } \Re ( \bar { v } _ { k } w _ { k } ) \Re ( \bar { v } _ { k } z _ { k } ). \\ & \text{proof } \text{Theorem } 2. 2 \text{ implies that there is } M _ { \mathbf z } > 0 \text{ such that } G ( \mathbf v, t ) \, \geq$$

$$( 2. 6 ) \ H _ { 3 } ( \mathbf y ) = H _ { 3 } ( \mathbf v, \mathbf w ) \cdot \sin ( \theta ) + O ( \sin ^ { 2 } ( \theta ) ), \ \ H _ { 4 } ( \mathbf y ) = H _ { 4 } ( \mathbf v ) + O ( \sin ( \theta ) ).$$

We first discuss the case H 4 ( v ) = 0 . The discriminant of G ( y , t ) - as a quadratic function of t - is given by

16 H 2 3 ( y ) -4 H f ( z )[ y ]( H f ( z )[ y ] + H 4 ( y )) = 16 H 2 3 ( v w , ) sin 2 ( θ ) + O (sin 3 ( θ )) .

/negationslash

If H 3 ( v w , ) = 0 , this term is positive for all sufficiently small θ and hence, G ( y , t ) has two real roots. The absolute value of the larger root is

$$\frac { 4 | H _ { 3 } ( \boldsymbol y ) | + \sqrt { 1 6 H _ { 3 } ^ { 2 } ( \boldsymbol y ) - 4 H _ { f } ( \boldsymbol z ) | \boldsymbol y | ( H _ { f } ( \boldsymbol z ) | \boldsymbol y | + H _ { 4 } ( \boldsymbol y ) ) } } { 2 H _ { f } ( \boldsymbol z ) | \boldsymbol y | } = \Theta \left ( | \sin ( \theta ) | ^ { - 1 } \right ),$$

which implies that there does not exist a constant M &gt; z 0 such that G ( y , t ) ≥ 0 for all y and t such that y ∈ T M∩ z CS n -1 and | t | ≥ M z . Thus, we have H 3 ( v w , ) = 0 in this case. Next, we consider the case H 4 ( v ) &gt; 0 and let us suppose 4 H 2 3 ( v w , ) &gt; H f ( z )[ y ] H 4 ( v ) = Θ (sin 2 ( θ )) . The discriminant of G ( y , t ) now satisfies

$$1 6.$$

$$\begin{array} { c } \quad = 4 \left [ 4 H _ { 3 } ^ { 2 } ( \mathbf v, \mathbf w ) \sin ^ { \cdot } ( \theta ) - H _ { f } ( \mathbf z ) [ \mathbf w ] H _ { 4 } ( \mathbf v ) \right ] \sin ^ { 2 } ( \theta ) \\ \text{sufficiently small } \theta \neq 0. \, As \, \text{in the last case, the absol} \quad \neq \cdot \cdot \cdot \cdot \cdot \end{array}$$

$$1 6 H _ { 3 } ^ { 2 } ( & \mathbf y ) - 4 H _ { f } ( \mathbf z ) [ \mathbf y ] ( H _ { f } ( \mathbf z ) [ \mathbf y ] + H _ { 4 } ( \mathbf y ) ) \\ & = 4 \left [ 4 H _ { 3 } ^ { 2 } ( \mathbf v, \mathbf w ) \sin ^ { 2 } ( \theta ) - H _ { f } ( \mathbf z ) [ \mathbf w ] H _ { 4 } ( \mathbf v ) \right ] \sin ^ { 2 } ( \theta ) + O ( \sin ^ { 3 } ( \theta ) ) > 0,$$

↦

for all sufficiently small θ = 0 . As in the last case, the absolute value of the larger root of t → G ( y , t ) converges to + ∞ as θ → 0 which yields the same contradiction. Consequently, we have 4 H 2 3 ( v w , ) ≤ H f ( z )[ w ] H 4 ( v ) by combining the two cases.

/negationslash

The fourth-order optimality conditions in Theorem 2.3 and 2.4 resemble other known fourth order conditions, see, e.g., [28,65,23], and might be hard to verify in practice. However, in the real case, the inequality H 4 ( v ) ≥ 0 is equivalent to checking ‖| v | 2 -| |‖ ≥ z 2 √ 2 ‖ z ‖ 2 4 . In this situation, the framework presented in [4] can be used to verify the first two conditions in Theorem 2.4 in polynomial time.

Theorem 2.5 (Fourth-Order Sufficient Optimality Conditions) Suppose that the point z ∈ CS n -1 satisfies the conditions

```
\Gamma \dots \Delta \sim \sum _ { k \in [ n ] } \Phi ( \bar { v } _ { k } w _ { k } ) \Re ( \bar { v } _ { k } z _ { k } ) \text{ and equality in the last}
```

where H 3 ( v w , ) = H 3 ( v ) + 2 β ∑ k ∈ [ n ] /Rfractur (¯ v k w k ) /Rfractur (¯ v k z k ) and equality in the last inequality holds if and only if H 4 ( v ) = 0 . Then z is a local minimum of (1.1) .

Proof We prove that there exists a constant M &gt; z 0 such that G ( v , t ) ≥ 0 for all v ∈ T M ∩ z CS n -1 and t with | t | ≥ M z . If this condition holds, then by Theorem 2.2, we know that z is a local minima of problem (1.1). If H f ( z )[ v ] = 0 , then it follows G ( v , t ) = H 4 ( v ) ≥ 0 for all t ∈ R .

↦

Next, let /epsilon1 &gt; 0 be a small constant. If H f ( z )[ v ] &gt; /epsilon1 , then the roots of the quadratic function t → G ( v , t ) are bounded by

$$& \frac { 4 | H _ { 3 } ( \mathbf v ) | + \sqrt { | 1 6 H _ { 3 } ^ { 2 } ( \mathbf v ) - 4 H _ { f } ( \mathbf z ) [ \mathbf v ] ( H _ { f } ( \mathbf z ) [ \mathbf v ] + H _ { 4 } ( \mathbf v ) ) | } } { 2 H _ { f } ( \mathbf z ) [ \mathbf v ] } \leq \frac { ( 4 + 2 \sqrt { 6 } ) M } { 2 \epsilon }, \\ &. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad.$$

where M := max v ∈T M∩ z CS n -1 max { H f ( z )[ v ] , | H 3 ( v ) | , | H 4 ( v ) |} . The continuity of the functions H f ( z )[ ] · , | H 3 ( ) · | , and | H 4 ( ) · | implies M &lt; + ∞ . Hence, we have G ( v , t ) ≥ 0 for all t ∈ R such that | t | ≥ (2 + √ 6) M/epsilon1 -1 . We now consider the case H f ( z )[ v ] ∈ (0 , /epsilon1 ] . Let us define the decomposition

$$\mathbf v = \cos ( \theta ) \cdot \mathbf u + \sin ( \theta ) \cdot \mathbf w, \, H _ { f } ( \mathbf z ) [ \mathbf u ] = 0, \, H _ { f } ( \mathbf z ) [ \mathbf w ] > 0, \, \mathbf u ^ { * } \mathbf w = 0,$$

where θ ∈ [ -π, π ] and u w , ∈ T M ∩ z CS n -1 . Specifically, introducing the sets N := { v ∈ C n : H f ( z )[ v ] = 0 } and W := T M∩ z CS n -1 ∩N ⊥ , there exists ¯ σ &gt; 0

↦

such that H f ( z )[ w ] ≥ ¯ σ for all w ∈ W . As before, we have H f ( z )[ v ] = H f ( z )[ w ] · sin 2 ( θ ) and in the case H 4 ( u ) = 0 , the condition 4 H 2 3 ( u w , ) ≤ H f ( z )[ w ] H 4 ( u ) implies H 3 ( u w , ) = 0 . Utilizing (2.6), this yields | H 3 ( v ) | ≤ η sin 2 ( θ ) for some universal constant η &gt; 0 and H 4 ( v ) = O (sin( θ )) . If the discriminant of the quadratic function t → G ( v , t ) is negative, it follows G ( v , t ) ≥ 0 for all t ∈ R . Otherwise, if the discriminant is non-negative, then the absolute values of the roots are bounded by

$$& \frac { 4 | H _ { 3 } ( \mathbf v ) | + \sqrt { 1 6 H _ { 3 } ^ { 2 } ( \mathbf v ) - 4 H _ { f } ( \mathbf z ) [ \mathbf v ] ( H _ { f } ( \mathbf z ) [ \mathbf v ] + H _ { 4 } ( \mathbf v ) ) } } { 2 H _ { f } ( \mathbf z ) [ \mathbf w ] \cdot \sin ^ { 2 } ( \theta ) } \\ & \quad \leq \frac { 4 \eta \sin ^ { 2 } ( \theta ) + \sqrt { 1 6 \eta ^ { 2 } - 4 H _ { f } ^ { 2 } ( \mathbf z ) [ \mathbf w ] + O ( \sin ( \theta ) ) } \sin ^ { 2 } ( \theta ) } { 2 H _ { f } ( \mathbf z ) [ \mathbf w ] \cdot \sin ^ { 2 } ( \theta ) } \\ & \quad \leq \frac { 4 \eta + \sqrt { 1 6 \eta ^ { 2 } + 1 } } { 2 H _ { f } ( \mathbf z ) [ \mathbf w ] } \leq \frac { 4 \eta + 1 } { \bar { \sigma } }. \\ & \text{ consequently, it holds } G ( \mathbf v, t ) \geq 0 \text{ for all } t \in \mathbb { R } \text{ such that } | t | \geq ( 4 \eta + 1 ) \bar { \sigma } ^ { - 1 }. \text{ Only}$$

Consequently, it holds G ( v , t ) ≥ 0 for all t ∈ R such that | t | ≥ (4 η +1)¯ σ -1 . Otherwise, if H 4 ( u ) &gt; 0 , then the last condition of this theorem implies 4 H 2 3 ( u w , ) &lt; H f ( z )[ w ] H 4 ( u ) . In this case, the discriminant of G ( v , · ) satisfies

$$1 6 H _ { 3 } ^ { 2 } ( \mathbf v ) & - 4 H _ { f } ( \mathbf z ) [ \mathbf v ] ( H _ { f } ( \mathbf z ) [ \mathbf v ] + H _ { 4 } ( \mathbf v ) ) \\ & = 4 [ 4 H _ { 3 } ^ { 2 } ( \mathbf u, \mathbf w ) - H _ { f } ( \mathbf z ) [ \mathbf w ] H _ { 4 } ( \mathbf u ) ] \cdot \sin ^ { 2 } ( \theta ) + O ( \sin ^ { 3 } ( \theta ) ) < 0, \\ \int \, \frac { 1 } { 2 } \, \text{thecan conflict, emit, and then, was about in } C ( \mathbf v, \, \mathbf v ) > \, \theta \, \text{for all} \, \leq \, \mathbb { D } \, \text{or all}$$

if θ is chosen sufficiently small and thus, we obtain G ( v , t ) ≥ 0 for all t ∈ R . Overall, we can set M z := max (2 + { √ 6) M/epsilon1 -1 , (4 η + 1)¯ σ -1 } and z is a local minima of problem (1.1).

## 3 Geometric Analysis of the Diagonal Case

In this section, we investigate the geometric properties of problem (1.1) under the assumption that A is a diagonal matrix, i.e., A = diag( a ) = diag( a , a 1 2 , ..., a n ) . 2

$$\min _ { \substack { u \in \mathbb { R } ^ { n } } } \frac { 1 } { 2 } a ^ { T } u + \frac { \beta } { 2 } \| u \| ^ { 2 } \text{ s.t. } u \in \Delta _ { n }. \\ \cdot \quad \cdot \quad \cdot \quad \cdot \quad - \min _ { \substack { u \in \mathbb { R } ^ { n } } } \quad - \tau \sim \tau - \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau - \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau - \tau - \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau } + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tvar + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \ttau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau +\tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau + \tau +$$

By setting u k = | z k | , we can reformulate problem (1.1) as a convex problem where ∆ n = { u ∈ R n : u k ∈ [0 , 1] , k ∈ [ n , ] ∑ k ∈ [ n ] u k = 1 } is the n -simplex. We will use this connection later to show that there are no spurious local minima in the diagonal case and that the global solutions can be characterized via the unique solution of the strongly convex problem (3.1).

We first derive an explicit representation of critical points of problem (1.1).

Lemma 3.1 (Characterizing Stationary Points) Suppose that A is a diagonal and let z ∈ CS n -1 be given. Let us set I := { k ∈ [ n ] : z k = 0 } and

/negationslash

$$u _ { k } \coloneqq 0, \quad \forall \, k \in \mathcal { I } ^ { C }, \quad u _ { k } \coloneqq \frac { 1 } { | \mathcal { I } | } + \frac { 1 } { 2 \beta } \left [ \frac { 1 } { | \mathcal { I } | } \sum _ { i \in \mathcal { I } } a _ { i } - a _ { k } \right ], \quad \forall \, k \in \mathcal { I }. \\ \text{Then,} \, \mathbf z \text{ is a stationary point if and only if there exist } \theta _ { k } \in [ 0, 2 \pi ), \, k \in [ n ], \, \text{such that}$$

Then, z is a stationary point if and only if there exist θ k ∈ [0 , 2 π ) , k ∈ [ n ] , such that u k ∈ (0 , 1] for all k ∈ I and z k = √ u e k iθ k for all k .

Proof In the diagonal case, introducing the polar form z = ( r 1 e iθ 1 , . . . , r n e iθ n ) T , the first-order optimality conditions reduce to

$$( a _ { k } + 2 \beta r _ { k } ^ { 2 } - 2 \lambda ) r _ { k } e ^ { i \theta _ { k } } = 0, \ \forall \, k \in [ n ]$$

where λ is the associated Lagrange multiplier. Specifically, for all k ∈ I , we have a k +2 βr 2 k = 2 λ and summing these equations, we obtain

$$\lambda = \frac { 2 \beta + \sum _ { k \in \mathcal { I } } a _ { k } } { 2 | \mathcal { I } | }, \quad r _ { k } ^ { 2 } = \frac { 2 \lambda - a _ { k } } { 2 \beta }, \\ \omega \circ \omega \circ \dots \dots \dots \dots \dots \omega \dots \omega.$$

and 2 λ -a k ∈ (0 , 2 β ] for all k ∈ I . The claimed result in Lemma 3.1 now follows immediately by setting u k = r 2 k , k ∈ [ n ] .

Next, we discuss the local minimizer of problem (1.1). By combining Theorems 2.1 and 3.1, we see that there are no spurious local minimizer in the diagonal case, i.e., all local solutions are automatically global solutions of problem (1.1).

Theorem 3.1 (Characterization of Local Minimizer) Let A be a diagonal matrix. A point z C n is a local minimizer of problem (1.1) if and only if

∈

$$( 3. 2 ) \quad \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
 \quad \quad \quad$$

where λ ∈ R is the associated Lagrange multiplier. In addition, every local solution z can be represented explicitly and has to satisfy

$$z _ { k } = \sqrt { u _ { k } } e ^ { i \theta _ { k } }, \quad \theta _ { k } \in [ 0, 2 \pi ), \quad \mathbf u = \mathcal { P } _ { \Delta _ { n } } ( - \mathbf a / 2 \beta ), \quad \forall \, k \in [ n ],$$

where P ∆ n denotes the Euclidean projection onto the n -simplex ∆ n .

Proof According to Theorem 2.1, a point satisfying the conditions (3.2) is a global minimum of problem (1.1) and hence, it also a local minimum. Let z ∈ CS n -1 now be an arbitrary local minimum. Then, the first- and second-order necessary optimality conditions hold at z , i.e., we have grad f ( z ) = 0 and

$$& ( 3. 3 ) & & H _ { f } ( \mathbf z ) [ \mathbf v ] = \mathbf v ^ { * } H \mathbf v + 4 \beta \cdot \sum \nolimits _ { k = 1 } ^ { n } r _ { k } ^ { 2 } t _ { k } ^ { 2 } \cos ^ { 2 } ( \theta _ { k } - \phi _ { k } ) \geq 0 \\ & \text{for all } \mathbf v \, \in \, \mathcal { T } _ { \mathbf z } \mathcal { M }, \, \text{where } ( r _ { 1 } e ^ { i \theta _ { 1 } }, \dots, r _ { n } e ^ { i \theta _ { n } } ) ^ { T } \text{ and } ( t _ { 1 } e ^ { i \phi _ {$$

for all v ∈ T M z , where ( r 1 e iθ 1 , . . . , r n e iθ n ) T and ( t 1 e iφ 1 , . . . , t n e iφ n ) T are the corresponding polar coordinates of z and v , respectively.

/negationslash

In order to verify the explicit characterization of local minimizers, we notice that u = P ∆ n ( -a / 2 β ) is the unique solution of the strongly convex problem (3.1). Moreover, using the identity u k ≡ | z k | 2 , k ∈ [ n ] , every global solution of (1.1) corresponds to a global minimizer of the problem (3.1) and vice versa. Since problem (1.1) does not possess spurious local minimizers, this finishes the proof of Theorem 3.1.

As shown in Lemma 3.1 and using the stationarity condition grad f ( z ) = 0 , it follows H kk = a k + 2 β z | k | 2 -2 λ = 0 for all k ∈ I = { k : z k = 0 } . Next, for k ∈ I C , we define v := e k , where e k denotes the k -th unit vector. This choice of v obviously fulfills /Rfractur ( v z ∗ ) = 0 and thus, the optimality condition (3.3) implies H kk = H f ( z )[ v ] ≥ 0 . Since H is diagonal, this yields H /followsequal 0 .

The latter theorem shows that we can identify and explicitly compute the unique equivalence class /llbracket z /rrbracket of global minimizer by a projection onto the n -simplex. This can be realized numerically in O n ( log n ) operations, see [67].

Inspired by the analysis of phase synchronization problems in [9], we now study the behavior of global minimizer when the diagonal matrix A is perturbed by a random noise matrix W .

Theorem 3.2 Let A be a given diagonal matrix and let W ∈ C n × n be a Hermitian noise matrix with noise level σ &gt; 0 . Suppose that z 0 is a global minimizer of (1.1) and that the point y ∈ CS n -1 satisfies f σ ( y ) ≤ min z ∈ /llbracket z 0 /rrbracket f σ ( z ) , where f σ ( z ) := f ( z ) + σ 2 z ∗ W z . Then, it holds that

$$\min _ { \mathbf z \in [ \mathbf z _ { 0 } ] } \| \mathbf y - \mathbf z \| _ { 4 } \leq \overset { 3 } { \sqrt { 2 \sigma \beta ^ { - 1 } \| W \| _ { 2 } n ^ { 1 / 4 } } }. \\. \quad \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \colon$$

Proof As usual, we introduce the polar coordinates z 0 = ( r 1 e iθ 1 , ..., r n e iθ n ) T and y = ( t 1 e iφ 1 , ..., t n e iφ n ) T . Due to Theorem 3.1, we can assume θ k = φ k and we have a k +2 βr 2 k -2 λ ≥ 0 for all k ∈ [ n ] , where a k = A kk and λ is the associated multiplier of z 0 . Thus, using f σ ( y ) ≤ f σ ( z 0 ) , this implies

$$\| \text{multiplier} \, \int _ { 0 } ^ { - } \tilde { \ }. \, \text{ Thus}, \, \int using \, f _ { \sigma } ( y ) \leq \| f _ { \sigma } ( z _ { 0 } ), \, \text{this implies} \, \rightarrow \, \dots \\ \frac { \sigma } { 2 } ( z _ { 0 } ^ { * } W z _ { 0 } - y ^ { * } W y ) & \geq \frac { 1 } { 2 } ( y ^ { * } A y - z _ { 0 } ^ { * } A z _ { 0 } ) + \frac { \beta } { 2 } \cdot \sum _ { k \in [ n ] } ( t _ { k } ^ { 4 } - r _ { k } ^ { 4 } ) \\ & = \frac { 1 } { 2 } \sum _ { k \in [ n ] } ( a _ { k } + \beta ( t _ { k } ^ { 2 } + r _ { k } ^ { 2 } ) ) ( t _ { k } ^ { 2 } - r _ { k } ^ { 2 } ) \\ & \geq \frac { 1 } { 2 } \sum _ { k \in [ n ] } ( 2 \lambda + \beta ( t _ { k } ^ { 2 } - r _ { k } ^ { 2 } ) ) ( t _ { k } ^ { 2 } - r _ { k } ^ { 2 } ) \\ & = \frac { \beta } { 2 } \sum _ { k \in [ n ] } ( t _ { k } ^ { 2 } - r _ { k } ^ { 2 } ) ^ { 2 } \geq \frac { \beta } { 2 } \sum _ { k \in [ n ] } ( t _ { k } - r _ { k } ) ^ { 4 } = \frac { \beta } { 2 } \| y - z _ { 0 } \| _ { 4 } ^ { 4 }. \\ \text{Note that the last inequality follows from} \, ( t _ { k } + r _ { k } ) ^ { 2 } \geq ( t _ { k } - r _ { k } ) ^ { 2 }. \, \text{ Furthermore, by} \, \| \text{$k$} \| \cdots \, \tilde { \ }. \, \text{$1/4/1/\|\|$} \, \text{$two$} \, \text{how}$}$$

Note that the last inequality follows from ( t k + r k ) 2 ≥ ( t k -r k ) 2 . Furthermore, by H¨ older's inequality and by ‖ x ‖ 4 / 3 ≤ n 1 / 4 ‖ x ‖ , we have

$$z _ { 0 } ^ { * } W z _ { 0 } - y ^ { * } W y & = \Re ( ( z _ { 0 } - y ) ^ { * } W ( z _ { 0 } + y ) ) \leq \| z _ { 0 } - y \| _ { 4 } \| W ( z _ { 0 } + y ) \| _ { 4 / 3 } \\ & \leq n ^ { 1 / 4 } \| z _ { 0 } - y \| _ { 4 } \| W ( z _ { 0 } + y ) \| \leq 2 n ^ { 1 / 4 } \| W \| _ { 2 } \| z _ { 0 } - y \| _ { 4 }. \\ \varkappa \dots \dots \lambda \dots \lambda \dots \dots \lambda \dots \dots \lambda \dots \dots \lambda.$$

Combining the above two inequalities, concludes the proof.

Remark 1 If W ∈ C n × n is a Hermitian random matrix with i.i.d. off-diagonal entries following a standard complex normal distribution and with zero diagonal entries, then Bandeira, Boumal, and Singer, [9], have shown that the bound ‖ W ‖ 2 ≤ 3 √ n holds with probability at least 1 -2 n -5 / 4 -e -n/ 2 . Combing this observation with Theorem 3.2, we can obtain

$$\min _ { z \in [ z _ { 0 } ] } \| \mathbf y - \mathbf z _ { 0 } \| _ { 4 } \leq \sqrt { 6 \sigma \beta ^ { - 1 } } \cdot n ^ { 1 / 4 } \\ \intertext { t la a c t } 1 \, \text{$\mathfrak n - 5 / 4 } \, \varepsilon ^ { - n / 2 }$$

with probability at least 1 -2 n -5 / 4 -e -n/ 2 .

## 4 Geometric Analysis of the Rank-One Case

In this section, we investigate the case when A is rank-one and positive semidefinite, i.e., we can write A = aa ∗ for some a ∈ C n and the quartic-quadratic problem (1.1) reduces to

$$& ( 4. 1 ) \quad \min _ { z \in \mathbb { C } ^ { n } } \, f ( z ) = \frac { 1 } { 2 } | \mathbf a ^ { * } z | ^ { 2 } + \frac { \beta } { 2 } \| z \| _ { 4 } ^ { 4 } \ \text{ s.t. } \ \| z \| _ { 2 } = 1. \\ & \quad \cdots \cdots \cdots \cdots \cdots \cdots \cdots.$$

The associated first- and second-order necessary optimality conditions are given by

$$\mathfrak { a } ^ { * } z \cdot \mathfrak { a } + 2 \beta \text{diag} ( | z | ^ { 2 } ) z = 2 \lambda z, \quad 2 \lambda = | \mathfrak { a } ^ { * } z | ^ { 2 } + 2 \beta \| z \| _ { 4 } ^ { 4 } \\ \dots \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \colon$$

and H f ( z )[ v ] = v ∗ [ aa ∗ +2 β diag( | z | 2 ) -2 λI ] v +4 β ∑ n k =1 /Rfractur ( v k ¯ ) z k 2 ≥ 0 for all v ∈ C n with /Rfractur ( v z ∗ ) = 0 . We now present a first structural and preparatory property of local and global minima.

Lemma 4.1 Suppose that z is a local minimizer of (4.1) . Then, for all k ∈ [ n ] with a k = 0 it holds that | z k | 2 = λ β .

/negationslash

Proof If a k = 0 , the first-order optimality conditions imply β z | k | 2 z k = λz k . Let us assume z k = 0 and let us choose v ∈ C n with v k = 1 and v j = 0 for all j = k . Due to λ ≥ β ‖ z ‖ 4 4 ≥ β n &gt; 0 , we obtain

$$H _ { f } ( \mathbf z ) [ \mathbf v ] = - 2 \lambda < 0,$$

which contradicts the second-order necessary optimality conditions. Hence, we have | z k | 2 = λ β .

In the following sections, we discuss two different classes of local minima, which are characterized by the orthogonality to the vector a .

## 4.1 Orthogonal local minima

We first analyze the case where the local minimizer z satisfies a z ∗ = 0 .

Theorem 4.1 Suppose that z is a local minimizer satisfying a z ∗ = 0 . Then, z has at most one zero component and all of its nonzero components must have the same modulus.

Proof By the first-order optimality conditions, it follows z k = 0 or | z k | 2 = λ β for all k . Hence, all nonzero components of z have the same modulus.

/negationslash

Without loss of generality we now assume that | z k | 2 = λ β for 1 ≤ k ≤ τ and z k = 0 for τ +1 ≤ k ≤ n . Due to Lemma 4.1, we have a n -1 , a n = 0 if τ ≤ n -2 . Let us set

$$v _ { k } = 0, \ \ k \in [ n - 2 ], \ \ v _ { n - 1 } = \frac { a _ { n } } { \sqrt { | a _ { n - 1 } | ^ { 2 } + | a _ { n } | ^ { 2 } } }, \ \ v _ { n } = \frac { - a _ { n - 1 } } { \sqrt { | a _ { n - 1 } | ^ { 2 } + | a _ { n } | ^ { 2 } } }. \\ \text{Then, it holds that } H _ { f } ( z ) [ v ] = - 2 \lambda < 0, \text{which is a contradiction. Thus, we have} \\ \tau - \tau - 1 \, \text{or} - \tau \, - \tau \, \text{which means that all commonante} \, \tau. \, \text{or} \, \text{nonzero} \, \tau.$$

Then, it holds that H f ( z )[ v ] = -2 λ &lt; 0 , which is a contradiction. Thus, we have τ = n -1 or τ = n (which means that all components z k are nonzero).

Next, we derive conditions under which the existence of such local minima can be ensured. Before we present the formal statement and proof of the main theorem, we discuss a result that is used later in Theorem 4.2.

Lemma 4.2 If ‖ a ‖ ∞ ≤ 1 2 ‖ a ‖ 1 , there exist phases { θ k } k ∈ [ n ] , θ k ∈ [0 , 2 π ] , such that ∑ k ∈ [ n ] e iθ k a k = 0 .

/negationslash

Otherwise assume n ≥ 3 and | a 1 | = ‖ a ‖ ∞ . Let b 1 = ∑ k ≥ 3 | a k | , b 2 = | a 2 | and b 3 = | a 1 | . It holds that b 1 + b 2 = ‖ a ‖ 1 -| a 1 | ≥ b 3 , which means that the numbers b 1 , b 2 , b 3 can be interpreted as sides of a (degenerated) triangle. Let ABC be such a triangle embedded into the complex space, where A,B,C ∈ C denote the nodes of ABC with | B -C | = b 1 , | C -A | = b 2 , | A -B | = b 3 . Consequently, there exist φ , φ 1 2 , φ 3 ∈ [0 , 2 π ) such that B -C = e iφ 1 b 1 , C -A = e iφ 2 b 2 , A -B = e iφ 3 b 3 . But then we have ∑ 3 k =1 e iφ k b k = 0 , which completes the proof of the lemma.

Proof Let us assume a k = 0 for all k . If n = 1 , the condition ‖ a ‖ ∞ ≤ 1 2 ‖ a ‖ 1 is never satisfied and hence, the statement in Lemma 4.2 holds automatically. In the case n = 2 , we have 2 max {| a 1 | , | a 2 |} ≤ | a 1 | + | a 2 | . This implies | a 1 | = | a 2 | and thus, we can choose θ 1 and θ 2 such that e iθ 1 a 1 = | a 1 | and e iθ 2 a 2 = -| a 1 | .

Theorem 4.2 (Existence of Orthogonal Local Minima) There exists a local minimizer z of (4.1) such that a z ∗ = 0 if and only if ‖ a ‖ ∞ ≤ 1 2 ‖ a ‖ 1 , or a has only one nonzero component and we have ‖ a ‖ 2 ≥ 2 β/ n ( -1) . Further, if a satisfies such conditions, all local minima with a z ∗ = 0 are the only global minima of (4.1) .

Proof Let z = ( r 1 e iθ 1 , . . . , r n e iθ n ) T be a local minimizer of problem (4.1) such that a z ∗ = 0 . By Theorem 4.1, we only need to consider the cases when the local minimizer has no zero component or exactly one zero component.

Case 1. If z does not have any zero component, then it follows | z k | 2 = 1 n for all k and we have

$$\mathbf a ^ { * } \mathbf z = \frac { 1 } { \sqrt { n } } \sum _ { k \in [ n ] } e ^ { i \theta _ { k } } a _ { k } = 0, \\..$$

/negationslash which implies | a j | = | ∑ k = j e iθ k a k | ≤ ∑ k = j | a k | = ‖ a ‖ 1 - | a j | for all j ∈ [ n ] . Choosing a j to be the element with maximal modulus, we get ‖ a ‖ ∞ ≤ 1 2 ‖ a ‖ 1 .

/negationslash

/negationslash

Case 2. Let us suppose z n = 0 . Then, due to Lemma 4.1, we obtain a n = 0 . Let us assume that there exists another component a k = 0 for some k ∈ [ n -1] . Setting

/negationslash

/negationslash

$$v _ { j } = i z _ { j }, \ \ j \neq k, n, \ \ v _ { k } = ( 1 - | a _ { n } | ) i z _ { k }, \ \ v _ { n } = \frac { a _ { n } } { | a _ { n } | } \bar { a } _ { k } \cdot i z _ { k }, \\ \cdot \quad \dots \quad \cdot \quad \ast \quad \infty / \ast \ \infty \quad \dots \quad \cdot \quad \cdot \quad \cdot$$

and normalizing v , we have a v ∗ = /Rfractur ( z v ∗ ) = 0 and the curvature is given by

$$H _ { f } ( \mathbf z ) [ \mathbf v ] = 2 \beta \sum _ { k \in [ n - 1 ] } | z _ { k } | ^ { 2 } | v _ { k } | ^ { 2 } - 2 \lambda = - 2 \lambda | v _ { n } | ^ { 2 } < 0,$$

which contradicts with the second-order optimality conditions. Hence, we can infer a k = 0 for all k ∈ [ n -1] , which implies that a has only one nonzero component. By

Theorem 4.1, we have | z k | 2 = 1 n -1 for all k ∈ [ n -1] . The second-order necessary optimality conditions yields

$$H _ { f } ( \mathbf z ) [ \mathbf v ] & = | a _ { n } v _ { n } | ^ { 2 } + \frac { 2 \beta } { n - 1 } ( 1 - | v _ { n } | ^ { 2 } ) - \frac { 2 \beta } { n - 1 } = \left ( | a _ { n } | ^ { 2 } - \frac { 2 \beta } { n - 1 } \right ) | v _ { n } | ^ { 2 } \geq 0, \\ \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \colon$$

for | v n | ∈ [0 , 1] and it follows ‖ a ‖ 2 = | a n | 2 ≥ 2 β n 1 .

-We continue with the proof of the second direction. In particular, suppose that a satisfies the conditions stated in Theorem 4.2. We again discuss two cases.

Case 1. By Lemma 4.2, if ‖ a ‖ ∞ ≤ 1 2 ‖ a ‖ 1 , we can choose phases { θ k } k ∈ [ n ] such that ∑ k ∈ [ n ] e iθ k a k = 0 . Let us set z k = e iθ k / √ n for all k ∈ [ n ] . Then, we have a z ∗ = 0 and f ( z ) = β/ (2 n ) , which is the lower bound of the objective function f . Thus, in this case z is a global minimizer of (4.1). Moreover, the objective function attains its optimal value if and only if a z ∗ = 0 and ‖ z ‖ 4 4 = 1 /n .

Case 2. If a has only one nonzero component a n with ‖ a ‖ 2 ≥ 2 β n -1 , the matrix A is diagonal and we can apply the results derived in section 3. Specifically, by Theorem 3.1, it can be shown that all local minimizer are global minimizer and satisfy

$$| z _ { k } | = \frac { 1 } { \sqrt { n - 1 } }, \quad \forall \, k \in [ n - 1 ], \quad \text{and} \quad z _ { n } = 0. \\ \intertext { show the new $c_{\alpha}$} \, \alpha \, \varphi \, \intertext { \text{throwsing $a$} \, \varphi$}$$

This finishes the proof of Theorem 4.2.

## 4.2 Non-orthogonal local minima

We discuss the case when there is no local minimizer z such that a z ∗ = 0 , or, equivalently, a does not satisfy the conditions in Theorem 4.1. By the first-order optimality conditions, all z k with a k = 0 satisfy

/negationslash

$$\arg ( z _ { k } ) - \arg ( a _ { k } ) = \arg ( \mathbf a ^ { * } \mathbf z ) = \text{const},$$

where arg( z ) is the principal angle of the complex number z modulo π . Since a global shift of the phase will not change the objective function value and the firstorder optimality conditions, we can shift z by a global phase such that the principal angles of the nonzero components are the same as a k . In the case a k = 0 , the phase of z k does not influence the objective function value and the first-order optimality conditions and we can adjust z to be a real number. Consequently, for every stationary point of problem (4.1), we can find a corresponding stationary point which has the same objective function value and satisfies the following 'consistency' property.

Definition 4.1 Astationary point z of problem (4.1) is called consistent, if it satisfies

$$\bar { a } _ { k } z _ { k } \in \mathbb { R }, \ \forall \, k \, \text{with} \, a _ { k } \neq 0 \ \text{ and} \ \, z _ { k } \in \mathbb { R }, \ \forall \, k \, \text{with} \, a _ { k } = 0.$$

/negationslash

Note that the corresponding consistent stationary point of a local minimizer of problem (4.1) does not need to be a local minimizer. On the other hand, shifted consistent stationary points of global minimizer remain global minimizer. In this subsection, we focus on structural properties of consistent stationary points of (4.1).

/negationslash

/negationslash

Remark 2 Suppose a does not satisfy the conditions in Theorem 4.1 and there exists a local minimizer z such that a z ∗ = 0 . If we have z k = 0 for some k ∈ [ n ] , then the first-order optimality conditions imply a k = 0 which contradicts Lemma 4.1. Hence, for any local minima z with a z ∗ = 0 , we have z k = 0 for all k ∈ [ n ] .

/negationslash

In the following result, we show that consistent local minima must belong to the same equivalence class defined in (2.3).

Theorem 4.3 Suppose that z y , ∈ CS n -1 are two consistent local minima of problem (4.1) with a z ∗ = 0 and a y ∗ = 0 . Then, we have y ∈ /llbracket z /rrbracket .

/negationslash

/negationslash

Proof The consistency of the stationary points y and z implies y z ∗ ∈ R and thus, it holds that i y ∈ T M ∩ z CS n -1 and i z ∈ T M ∩ y CS n -1 . By the second-order necessary optimality conditions, we have

$$H _ { f } ( \mathbf z ) [ i \mathbf y ] & = | \mathbf a ^ { * } \mathbf y | ^ { 2 } + 2 \beta \sum _ { k \in [ n ] } | z _ { k } y _ { k } | ^ { 2 } - 2 \lambda _ { \mathbf z } \geq 0, \\ ( 4. 2 ) & H _ { f } ( \mathbf y ) [ i \mathbf z ] & = | \mathbf a ^ { * } \mathbf z | ^ { 2 } + 2 \beta \sum _ { k \in [ n ] } | z _ { k } y _ { k } | ^ { 2 } - 2 \lambda _ { \mathbf y } \geq 0, \\ \dots \circ \circ \dots \circ \dots \circ \dots \dots \dots.$$

where 2 λ z = | a z ∗ | 2 + 2 β ‖ z ‖ 4 4 and 2 λ y = | a y ∗ | 2 + 2 β ‖ y ‖ 4 4 . Summing those two inequalities yields

$$0 \leq - 2 \beta \left [ \| z \| _ { 4 } ^ { 4 } - 2 \sum _ { k \in [ n ] } | z _ { k } y _ { k } | ^ { 2 } + \| y \| _ { 4 } ^ { 4 } \right ] = - 2 \beta \sum _ { k \in [ n ] } [ | z _ { k } | ^ { 2 } - | y _ { k } | ^ { 2 } ] ^ { 2 }. \\ \text{Hence, we have } | z _ { k } | = | y _ { k } | \text{ for all } k \in [ n ].$$

Hence, we have | z k | = | y k | for all k ∈ [ n ] .

Remark 3 Similarly, if z y , ∈ CS n -1 are two local minima of problem (4.1) such that z k and y k have the same phases for all k ∈ [ n ] , then y ∈ /llbracket z /rrbracket .

We now prove that there are no spurious consistent local minima.

Theorem 4.4 If a does not satisfy the conditions in Theorem 4.1, then all the consistent local minima of problem (4.1) are global minima.

/negationslash

Proof Suppose z y , ∈ CS n -1 are two consistent local minima. Using the inequalities in (4.2) and | z k | = | y k | , we obtain | a z ∗ | 2 = | a y ∗ | 2 . Hence, all consistent local minima have the same objective function value. Since a does not satisfy the conditions in Theorem 4 1 . , there exists a consistent global minimizer satisfying a z ∗ = 0 . This shows that all consistent local minima are global minima.

Remark 4 Combining the results of the last two subsections, we see that global minima of problem (4.1) are unique up to certain shifts in the phase. In particular, we can shift the phases of components with ( a z ∗ ) a k = 0 arbitrarily and shift all the other components by the same angle.

## 5 Analyzing the Geometric Landscape - the Real Case

We now investigate a variant of the so-called strict-saddle property introduced by Ge, Jin, and Zheng in [35, Definition 2]. More specifically, as in [73, Theorem 2.2], we strengthen the first condition in [35, Definition 2] to uniform positive definiteness of the Riemannian Hessian.

Definition 5.1 Let ξ, /epsilon1, ζ &gt; 0 be given constants. A function f is called ( ξ, /epsilon1, ζ ) -strict-saddle if for all z ∈ M one of the following conditions holds:

- 2. (Large gradient). It holds that ‖ grad f ( z ) ‖ ≥ /epsilon1 .
- 1. (Strong convexity). For all v ∈ T M ∩ z S n -1 we have H f ( z )[ v ] ≥ ξ .
- 3. (Negative curvature). There exists v ∈ T M ∩ z S n -1 with H f ( z )[ v ] ≤ -ζ .

The strict-saddle property can be utilized to establish polynomial time convergence rates of second-order optimization algorithms, such as the Riemannian trust region method [73], and almost sure convergence to local minimizer of Riemannian gradient descent methods with random initialization, see, e.g., [49,48].

In the following sections, we analyze the geometric landscape of problem (1.1) and show that the strict-saddle property is satisfied in the real case when the interaction coefficient β is sufficiently small or large. In general, due to the intricate relation between the quadratic and quartic terms, we can not expect that the conditions in Definition 5.1 do hold for all choices of β and A .

For instance, let us consider the example A := α 11 T , α ≥ 0 , and z := 1 / √ n ∈ S n -1 . Then, the associated multiplier λ is given by 2 λ = αn + 2 β/n and it can be shown that z is a stationary point of (1.1) for all α . Furthermore, for all v ∈ T M z , it follows

$$H _ { f } ( \mathbf z ) [ \mathbf v ] = \mathbf v ^ { T } [ A + 6 \beta \text{diag} ( | \mathbf z | ^ { 2 } ) - 2 \lambda I ] \mathbf v = [ 4 \beta n ^ { - 1 } - \alpha n ] \| \mathbf v \| ^ { 2 }.$$

Hence, in the case α = 4 β/n 2 , the strict-saddle property can not hold. Let us further note that the strong convexity condition in Definition 5.1 is never satisfied at stationary points in the complex case. In particular, if z ∈ CS n -1 is a critical point, then we have i z ∈ T M ∩ z CS n -1 and H f ( z )[ i z ] = 0 which contradicts condition 1.

In Figure 1, we illustrate different landscapes of the mapping f when the problem is real and three-dimensional and the parameter β changes. We consider the setup

$$( 5. 1 ) \quad \ A = \begin{pmatrix} 1 \, 0 \, 1 \\ 0 \, 1 \, 0 \\ 1 \, 0 \, 1 \end{pmatrix}, \quad \beta \in \{ 0. 2 5, 0. 7 5, 1. 2 5, 3. 2 5 \}, \\ \text{and the eigenvalues of $A$ are given by $2$, $1$, and $0$, respectively. Moreover, $v$}$$

↦

Figure 1 demonstrates that the landscape of the objective function varies a lot when the interaction coefficient β changes. Specifically, it shows that the number of stationary points and local minima increases from 6 to 26 and from 2 to 8 as β increases from 0 25 . to 3 25 . . In section 5.1 and section 5.2, we investigate basic geometric features and the strict-saddle property for large and small choices of β while and the eigenvalues of A are given by 2 , 1 , and 0 , respectively. Moreover, we use spherical coordinates ( φ, θ ) → (cos( φ , ) sin( φ ) cos( θ , ) sin( φ ) sin( θ )) T , φ ∈ [0 , 2 π ] , θ ∈ [0 , π ] , to plot the objective function f on the sphere.

Fig. 1: Plot of the landscape of the objective function for fixed A and different values of β . The red point marker depicts the location of saddle points. Local and global minima are indicated by non-filled and filled diamond markers. The location of local and global maxima is marked by non-filled and filled squares.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00745v1-figure-150ee69e-1b83-413d-b651-0c43cb5fed4b.jpg)

keeping the matrix A fixed. In particular, our results will allow us to characterize and describe the geometric landscape of f in the sub-figures (a) and (d) of Figure 1. In the following, we assume n ≥ 2 since the landscape of f is trivial in the case n = 1 .

## 5.1 Large interaction coefficient

In this section, we prove that the objective function possesses the strict-saddle property if the coefficient β is chosen sufficiently large and satisfies β ≈ Cρn 3 / 2 for some constant C &gt; 0 . Here, ρ := λ 1 -λ n denotes the difference between the largest and the smallest eigenvalue of A . We analyze the geometric properties and behavior of f on the following sets:

- 1. (Strong convexity) R 1 := { z ∈ S n -1 : ‖| z | 2 -1 /n ‖ ∞ ≤ 1 / 2 n } ,
- 3. (Negative curvature) R 3 := { z ∈ S n -1 : min k ∈ [ n ] z 2 k ≤ ( n -1) / 4 n 2 } .
- 2. (Large gradient) R 2 := { z ∈ S n -1 : ‖| z | 2 -1 /n ‖ ∞ ≥ 1 / 2 n, min k ∈ [ n ] z 2 k ≥ ( n -1) / 4 n 2 } ,

Obviously, these three regions cover the sphere S n -1 . An illustration of the regions R 1 -R 3 is given later in Figure 2.

We first present a preparatory result that is used later to estimate of the spectrum of the Riemannian Hessian.

Lemma 5.1 The following estimate holds for all z ∈ S n -1 :

$$\int _ { 0 } \int _ { \tau _ { 2 } \mathcal { M } \cap \mathbb { S } ^ { n - 1 } } z _ { 0 } ^ { 2 } & \leq \min _ { \nu \in \mathcal { T } _ { 2 } \mathcal { M } \cap \mathbb { S } ^ { n - 1 } } \sum _ { k \in [ n ] } v _ { k } ^ { 2 } z _ { k } ^ { 2 } & \leq \frac { n } { n - 1 } ( 1 - z _ { 0 } ^ { 2 } ) z _ { 0 } ^ { 2 }, \\ \int _ { \tau } \int _ { \tau } \int _ { \tau } \int _ { \tau } \int _ { \tau } \int _ { \tau } \int _ { \tau } \int _ { \tau } \int _ { \tau } \int _ { \tau } \int _ { \tau } \int _ { \tau } \int _ { \tau } \int _ { \tau } \int _ { \tau } \int _ { \tau } \int _ { \tau } \int _ { \tau } \int _ { \tau } \int _ { \tau } \int _ { \tau } \int _ { \tau } \int _ { \tau } \int _ { \tau } \int _ { \tau } \int _ { \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \ tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau \tau }$$

where z 2 0 := min k ∈ [ n ] z 2 k .

Proof If there exists k ∈ [ n ] with z k = 0 , then the optimal value of the latter optimization problem is 0 and it is attained for v = e k . Next, let us assume z 2 0 &gt; 0 and let i ∈ [ n ] be given with z 2 i = z 2 0 . We define v ∈ T M ∩ z S n -1 via

/negationslash

$$v _ { i } = - \frac { ( n - 1 ) c } { z _ { 1 } }, \ \ v _ { k } = \frac { c } { z _ { k } }, \ \ c = \left [ \frac { ( n - 1 ) ^ { 2 } } { z _ { i } ^ { 2 } } + \sum _ { k \neq i } \frac { 1 } { z _ { k } ^ { 2 } } \right ] ^ { - 1 / 2 }, \ \ k \neq i. \\ \intertext { I \text{inc the average H\&\text{and}$ in\null with we have $\mathcal{ }\mathcal{ }\mathcal{ }\nu^{-2} > (n - 1 \mathbb { \lambda } ^ { 2 } / \mathcal{ }\mathcal{ }\nu^{-1}$} }$$

/negationslash

/negationslash

Using the reverse H¨ older inequality, we have ∑ k = i z -2 k ≥ ( n -1) ( 2 ∑ k = i z 2 k ) -1 and thus, we obtain

/negationslash

$$\sum _ { k \in [ n ] } z _ { k } ^ { 2 } v _ { k } ^ { 2 } = n ( n - 1 ) c ^ { 2 } \leq \frac { n ( n - 1 ) } { \frac { ( n - 1 ) ^ { 2 } } { z _ { 0 } ^ { 2 } } + \frac { ( n - 1 ) ^ { 2 } } { 1 - z _ { 0 } ^ { 2 } } } \leq \frac { n } { n - 1 } ( 1 - z _ { 0 } ^ { 2 } ) z _ { 0 } ^ { 2 }. \\ \quad \ \ \ \ \.. \.$$

This establishes the upper bound in (5.2). The lower bound follows from ‖ v ‖ = 1 and z 2 k ≥ z 2 0 for all k ∈ [ n ] .

In the following lemma, we verify that the objective function has the strong convexity property on the region R 1 .

Lemma 5.2 Let γ &gt; 0 be given and suppose that β ≥ 2(1 + γ ρn ) . Then, for all z ∈ R 1 and all v ∈ T M ∩ z S n -1 it holds that H f ( z )[ v ] ≥ γρ .

Proof Let us define w k := z 2 k -1 n . Hence, due to ∑ k ∈ [ n ] w k = 0 , we obtain:

$$\sum _ { k \in [ n ] } z _ { k } ^ { 4 } & = \sum _ { k \in [ n ] } \left [ w _ { k } + \frac { 1 } { n } \right ] ^ { 2 } = \frac { 1 } { n } + \sum _ { k \in [ n ] } w _ { k } ^ { 2 } \leq \frac { 5 } { 4 n }. \\. & \quad \dots \quad \widehat { \Phi } \quad.$$

Next, by Lemma 5.1 and z ∈ R 1 , we have

$$\min _ { \mathbf v \in \mathcal { T } _ { \mathbf z } \mathcal { M } \cap \mathbb { S } ^ { n - 1 } } \sum _ { k \in [ n ] } z _ { k } ^ { 2 } v _ { k } ^ { 2 } \geq \min _ { k \in [ n ] } z _ { k } ^ { 2 } \geq \frac { 1 } { 2 n }. \\ - \quad -$$

Combining the last results and using v T A v -z T A z ≥ -ρ , it follows

$$\min _ { \mathfrak { v } \in \mathcal { T } _ { \mathfrak { z } } \mathcal { M } \cap \mathbb { S } ^ { n - 1 } } H _ { f } ( \mathbf z ) [ \mathbf v ] \geq - \rho + \frac { 2 \beta } { n } \left [ \frac { 3 } { 2 } - \frac { 5 } { 4 } \right ] \geq \gamma \rho$$

for all z ∈ R 1 .

The next lemma shows that the norm of the Riemannian gradient is strictly larger than zero - uniformly - on the region R 2 .

Lemma 5.3 Let β ≥ 8(1 + 1 n -1 )(1 + γ ρn ) 3 / 2 be given for some γ &gt; 0 . Then, for all z ∈ R 2 , it holds that ‖ grad f ( z ) ‖ ≥ γ √ 2 ρ .

Proof First, we split the norm of the Riemannian gradient grad f ( z ) as follows

$$\cdots \nolimits _ { \lambda } \cdots \nolimits _ { r } \cdots \nolimits _ { \lambda } \cdots \nolimits _ { r } \cdots \nolimits _ { \lambda } \cdots \nolimits _ { \lambda } \cdots \nolimits _ { \lambda } \cdots \nolimits _ { \lambda } \cdots \nolimits _ { \lambda } \cdots \nolimits _ { \lambda } \cdots \nolimits _ { \lambda } \cdots \nolimits _ { \lambda } \cdots \nolimits _ { \lambda } \cdots \nolimits _ { \lambda } \cdots \nolimits _ { \lambda } \cdots \nolimits _ { \lambda } \cdots \nolimits _ { \lambda } \cdots \nolimits _ { \lambda } \cdots \nolimits _ { \lambda } \cdots \nolimits _ { \lambda } \cdots.$$

$$\text{ we now estimate the minuena and supranena in the latter expression separately. Let} \\ \text{ us set $z=\sum_{k}^{\alpha_{k}p_{k},where}\{p_{k}\}_{k}$ is the set of orthogonal eigenvectors of the matrix} \\ A with corresponding eigenvalues \lambda _ { 1 }, \,.., \lambda _ { n }. \, \text{ Then, it holds that $\sum_{k}^{\alpha_{k}^{2}=1$ and} \\ \| A z - ( z ^ { T } A z ) \cdot z \| ^ { 2 } & = z ^ { T } A ^ { 2 } z - ( z ^ { T } A z ) ^ { 2 } = \sum _ { k \in [ n ] } \alpha _ { k } ^ { 2 } \lambda _ { k } ^ { 2 } - \left [ \sum _ { k \in [ n ] } \alpha _ { k } ^ { 2 } \lambda _ { k } \right ] ^ { 2 } \\ & = \sum _ { k \in [ n ] } \alpha _ { k } ^ { 2 } \lambda _ { k } ^ { 2 } - \sum _ { k, \ell \in [ n ] } \alpha _ { k } ^ { 2 } \alpha _ { \ell } ^ { 2 } \lambda _ { k } \lambda _ { \ell } \\ & = \frac { 1 } { 2 } \sum _ { k, \ell \in [ n ] } \alpha _ { k } ^ { 2 } \alpha _ { \ell } ^ { 2 } ( \lambda _ { k } - \lambda _ { \ell } ) ^ { 2 } \leq \frac { 1 } { 2 } \rho ^ { 2 } \sum _ { k, \ell \in [ n ] } \alpha _ { k } ^ { 2 } \alpha _ { \ell } ^ { 2 } = \frac { 1 } { 2 } \rho ^ { 2 }. \\ \text{ We continue with bounding the term } \| z \| _ { 1 } ^ { 6 } - \| z \| _ { 2 } ^ { 4 }. \, \text{ As before using the spherical} \\ \text{ constraint $\sum_{k},z^{2}=1$. we obtain:}$$

We now estimate the minuend and subtrahend in the latter expression separately. Let us set z = ∑ k α k p k , where { p k } k is the set of orthogonal eigenvectors of the matrix A with corresponding eigenvalues λ , ..., λ 1 n . Then, it holds that k α 2 k = 1 and

We continue with bounding the term ‖ z ‖ 6 6 - ‖ ‖ z 8 4 . As before using the spherical constraint k z 2 k = 1 , we obtain:

$$\text{We continue with bounding the term } \| z \| _ { 6 } ^ { \bullet } - \| z \| _ { 4 } ^ { \bullet }. \text{ As before using the spherical} \\ \text{constraint $\sum_{k} z_{k}^{2}=1$, we obtain} \colon \\ \| z \| _ { 6 } ^ { 6 } - \| z \| _ { 4 } ^ { 8 } = \sum _ { k \in [ n ] } z _ { k } ^ { 6 } - \left [ \sum _ { k \in [ n ] } z _ { k } ^ { 4 } \right ] ^ { 2 } = \frac { 1 } { 2 } \sum _ { k, \ell \in [ n ] } z _ { k } ^ { 2 } z _ { \ell } ^ { 2 } ( z _ { k } ^ { 2 } - z _ { \ell } ^ { 2 } ) ^ { 2 }. \\ \text{In the following and without loss of generality, we assume that the components of z}$$

/negationslash

$$1 & = \sum _ { k = 1 } ^ { t } z _ { k } ^ { 2 } + \sum _ { k = t + 1 } ^ { n } z _ { k } ^ { 2 } \geq t z _ { 1 } ^ { 2 } + \frac { n - t - 1 } { 2 } ( z _ { 1 } ^ { 2 } + z _ { n } ^ { 2 } ) + z _ { n } ^ { 2 },$$

In the following and without loss of generality, we assume that the components of z are ordered and satisfy z 2 1 ≤ z 2 2 ≤ ... ≤ z 2 n . Notice that z ∈ R 2 implies z 2 1 = z 2 n and let us choose t ∈ [ n -1] such that z 2 t ≤ 1 2 ( z 2 1 + z 2 n ) ≤ z 2 t +1 . Then, we have which yields

$$t & \geq \frac { ( n - 1 ) ( z _ { n } ^ { 2 } + z _ { 1 } ^ { 2 } ) + 2 z _ { n } ^ { 2 } - 2 } { z _ { n } ^ { 2 } - z _ { 1 } ^ { 2 } } \geq \frac { ( n - 1 ) z _ { 1 } ^ { 2 } + z _ { n } ^ { 2 } - 1 } { z _ { n } ^ { 2 } - z _ { 1 } ^ { 2 } }. \\ \text{nsequentially, we set}$$

Consequently, we get

$$\text{Consequently, we get} \\ \sum _ { k, \ell \in [ n ] } z _ { k } ^ { 2 } z _ { \ell } ^ { 2 } ( z _ { k } ^ { 2 } - z _ { \ell } ^ { 2 } ) ^ { 2 } & \geq z _ { 1 } ^ { 2 } \sum _ { k \in [ n ] } z _ { k } ^ { 2 } ( z _ { k } ^ { 2 } - z _ { 1 } ^ { 2 } ) ^ { 2 } + z _ { n } ^ { 2 } \sum _ { k \in [ n ] } z _ { k } ^ { 2 } ( z _ { k } ^ { 2 } - z _ { n } ^ { 2 } ) ^ { 2 } \\ & \geq \frac { 1 } { 4 } ( z _ { n } ^ { 2 } - z _ { 1 } ^ { 2 } ) ^ { 2 } \left [ z _ { 1 } ^ { 2 } \sum _ { k = t + 1 } ^ { n } z _ { k } ^ { 2 } + z _ { n } ^ { 2 } \sum _ { k = 1 } ^ { t } z _ { k } ^ { 2 } \right ] \\ & = \frac { 1 } { 4 } ( z _ { n } ^ { 2 } - z _ { 1 } ^ { 2 } ) ^ { 2 } \left [ z _ { 1 } ^ { 2 } + ( z _ { n } ^ { 2 } - z _ { 1 } ^ { 2 } ) \sum _ { k = 1 } ^ { t } z _ { k } ^ { 2 } \right ] \\ & \geq \frac { 1 } { 4 } ( z _ { n } ^ { 2 } - z _ { 1 } ^ { 2 } ) ^ { 2 } [ z _ { 1 } ^ { 2 } + ( z _ { n } ^ { 2 } - z _ { 1 } ^ { 2 } ) t z _ { 1 } ^ { 2 } ] \geq \frac { n } { 4 } ( z _ { n } ^ { 2 } - z _ { 1 } ^ { 2 } ) ^ { 2 } z _ { 1 } ^ { 4 }.$$

Using z 2 1 ≥ n -1 4 n 2 and max k | z 2 k -1 n | = max {| z 2 1 -1 n | , | z 2 n -1 n |} ≥ 1 2 n , it follows

$$2 [ \| z \| _ { 6 } ^ { 6 } - \| z \| _ { 4 } ^ { 8 } ] & \geq \frac { n } { 4 } ( z _ { n } ^ { 2 } - z _ { 1 } ^ { 2 } ) ^ { 2 } z _ { 1 } ^ { 4 } \geq \frac { n } { 4 } \left ( \frac { 1 } { 2 n } \right ) ^ { 2 } \left ( \frac { n - 1 } { 4 n ^ { 2 } } \right ) ^ { 2 } = \left ( \frac { n - 1 } { 1 6 n ^ { 5 / 2 } } \right ) ^ { 2 } \\ \dots \dots \dots \dots \dots \dots \dots \dots$$

and finally, combining the last results, we obtain

$$\| \text{grad} \, f ( \mathbf z ) \| \geq \frac { 1 } { \sqrt { 2 } } \left [ 2 \beta \cdot \frac { n - 1 } { 1 6 n ^ { 5 / 2 } } - \rho \right ] \geq \frac { \gamma } { \sqrt { 2 } } \rho,$$

as desired.

Finally, we show that we can always find a negative curvature direction if z belongs to the set R 3 .

Lemma 5.4 Let γ &gt; 0 be arbitrary and let β ≥ 2(1 + γ ρn ) be given. Then, for all z ∈ R 3 , there exists v ∈ T M ∩ z S n -1 such that H f ( z )[ v ] ≤ -γρ .

Proof Using the bound v T A v -z T A z ≤ ρ for z v , ∈ S n -1 and Lemma 5.1, it follows

$$\min _ { \mathbf v \in \mathcal { T } _ { \mathbf z } \mathcal { M } \cap \mathbb { S } ^ { n - 1 } } H _ { f } ( \mathbf z ) [ \mathbf v ] & \leq \rho + 2 \beta \left [ \frac { 3 n } { n - 1 } ( 1 - z _ { 0 } ^ { 2 } ) z _ { 0 } ^ { 2 } - \| \mathbf z \| _ { 4 } ^ { 4 } \right ], \\. \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigpm \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigcirc \quad \bigod { \cdot } }$$

where z 2 0 := min k ∈ [ n ] z 2 k . Moreover, due to ‖ z ‖ 4 4 ≥ 1 n ‖ z ‖ 4 = 1 n and z ∈ R 3 , we can infer

$$\min _ { \mathfrak { v } \in \mathcal { T } _ { \mathfrak { z } } \mathcal { M } \cap \mathbb { S } ^ { n - 1 } } H _ { f } ( \mathbf z ) [ \mathbf v ] & \leq \rho + 2 \beta \left [ \frac { 3 n } { n - 1 } z _ { 0 } ^ { 2 } - \frac { 1 } { n } \right ] \leq \rho - \frac { \beta } { 2 n } \leq - \gamma \rho, \\ \dots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots$$

which finishes the proof of Lemma 5.4.

Combining the last lemmata, we can derive the following strict-saddle property.

Theorem 5.1 Suppose that the coefficient β satisfies β ≥ 8 n n -1 (1+ γ ρn ) 3 / 2 for some given γ &gt; 0 . Then, the function f has the ( C ρ, γ γ √ 2 ρ, C γ ρ ) -strict-saddle property with C γ := 4 n -1 (1 + γ n ) 3 / 2 -1 .

As a consequence of the strict-saddle property, we can prove that each component of R 1 contains exactly one local minimizer when β is sufficiently large. In the next lemma, we first discuss uniqueness of local minimizer if the Riemannian Hessian is positive definite on a certain subset of the sphere.

Lemma 5.5 Let ν ∈ (0 , 1] and z 0 ∈ S n -1 be given and let us define R ν := { z ∈ S n -1 : ‖ z -z 0 ‖ 2 ≤ ν } . If the Riemannian Hessian Hess f of f is positive definite on R ν , i.e., if we have

$$\mathbf v ^ { T } \text{Hess} f ( \mathbf z ) \mathbf v = H _ { f } ( \mathbf z ) [ \mathbf v ] > 0, \quad \forall \, \mathbf v \in \mathcal { T } _ { \mathbf z } \mathcal { M } \langle 0 \}, \quad \forall \, \mathbf z \in \mathcal { R } _ { \nu },$$

then the problem min z ∈R ν f ( z ) has at most one local minimizer.

Proof Suppose that there exist two different local minima z 1 , z 2 of f in the set R ν . Let us consider the geodesic curve /lscript : R → S n -1 on the sphere connecting z 1 and z 2 . As shown in [2, Example 5.4.1], the curve /lscript can be represented as follows

$$\ell ( t ) & \coloneqq z _ { 1 } \cos ( t ) + \mathbf v \sin ( t ), \quad \mathbf v \coloneqq \frac { z _ { 2 } - ( z _ { 2 } ^ { T } z _ { 1 } ) z _ { 1 } } { \| z _ { 2 } - ( z _ { 2 } ^ { T } z _ { 1 } ) z _ { 1 } \| } \in \mathcal { T } _ { z _ { 1 } } \mathcal { M } \cap \mathbb { S } ^ { n - 1 }, \\ \intertext { show a T } \Psi ( 0 - \infty ) \colon \det \text{when a sub that } \theta ( t ) ( T \vee - \infty ) \, \mathbf M \, \mathbf m \, \mathbf i \, \mathbf i \, \mathbf i \, \mathbf i \, \mathbf i \, \mathbf i \, \mathbf i \, \mathbf i \, \mathbf i \, \mathbf i \, \mathbf i \, \mathbf i \, \mathbf i \, \mathbf i \, \mathbf i \, \mathbf i \, \mathbf i \, \mathbf i \, \mathbf i \, \mathbf i \, \mathbf i \, \mathbf i \, \mathbf i \, \mathbf i \, \mathbf i \, \mathbf i \, \mathbf i \, \mathbf i \, \mathbf i \, \mathbf i \, \mathbf i \, \mathbf i \, \mathbf i \, \mathbf i \} }.$$

$$\| \ell ( t ) - z _ { 0 } \| ^ { 2 } = 2 - 2 \left ( z _ { 0 } ^ { T } z _ { 1 } \cdot \cos ( t ) + z _ { 0 } ^ { T } \nu \cdot \sin ( t ) \right ) = 2 - 2 M \cos ( t + \theta ), \\ \text{where} \, M \, = \, \sqrt { ( z _ { 0 } ^ { T } z _ { 1 } ) ^ { 2 } + ( z _ { 0 } ^ { T } \nu ) ^ { 2 } } \, \text{and} \, \theta \, = \, \arccos ( z _ { 0 } ^ { T } z _ { 1 } ). \, \text{Since} \, \ell ( 0 ) \, \text{and} \, \ell ( T ) \, \text{ are}$$

where T ∈ (0 , 2 π ) is chosen such that /lscript ( T ) = z 2 . Multiplying /lscript ( T ) = z 2 with v T from the left yields sin( T ) = v T z 2 ≥ 0 and hence, we have T ∈ (0 , π ] . Then, for all t ∈ (0 , T ) , it follows /lscript ( ) t T /lscript ′ ( ) = 0 t , ‖ /lscript ′ ( ) t ‖ = 1 , and where M = √ ( z T 0 z 1 ) 2 +( z T 0 v ) 2 and θ = arccos( z T 0 z 1 ) . Since /lscript (0) and /lscript ( T ) are both elements of R ν , we know that

$$\| \mathbf z _ { 0 } - \ell ( 0 ) \| ^ { 2 } \leq \nu \leq 1, \quad \| \mathbf z _ { 0 } - \ell ( T ) \| ^ { 2 } \leq \nu \leq 1, \\ \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \, \end{matrix}$$

which lead to cos( θ , ) cos( θ + T ) &gt; 0 . Due to T ∈ (0 , π ] , we have θ, θ + T ∈ ( -π 2 +2 kπ, π 2 +2 kπ ) for some k ∈ Z . The landscape of cos( ) t in this range shows that the maximal value of ‖ z 0 -/lscript ( ) t ‖ 2 is achieved by the endpoints t = 0 or t = T . Hence, it holds that ‖ z 0 -/lscript ( ) t ‖ 2 ≤ ν and /lscript ( ) t ∈ R ν for all t ∈ [0 , T ] .

The special form of the curve /lscript yields /lscript ′′ ( ) = t -/lscript ( ) t for all t ∈ R and thus, the second-order derivative of the continuous function g t ( ) := f ( /lscript ( )) t is given by

$$\kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kaga \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \cdot \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \ kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa\colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colot \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon\kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kagger \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \codeot \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon \kappa \colon$$

for all t ∈ (0 , T ) , which implies that g is strictly convex on [0 , T ] . Per assumption the points z 1 and z 2 are local minima of the problem min z ∈R ν f ( z ) and thus, also of the problem min t ∈ [0 ,T ] g t ( ) . However, this contradicts the strict convexity of g .

Corollary 5.1 If β &gt; ρn 2 , the problem (1.1) has at least 2 n local minima. Furthermore, if β &gt; 18 n 3 n -1 ρ , then the problem (1.1) has exactly 2 n local minima.

/negationslash

Proof Without loss of generality, we can assume λ n ( A ) = λ n = 0 . We first prove that there exists at least one local minimizer in each component of the region R 1 if β ≥ ρn 2 . Notice that we have z ∈ R 1 if and only if z 2 k ∈ [ 1 2 n , 3 2 n ] for all k ∈ [ n ] . Let σ ∈ {-1 +1 , } n be a given binary vector and let us define the sets B := { z ∈ S n -1 : ‖| z | 2 -1 n 1 ‖ ≤ 1 n } and P σ := ∏ k ∈ [ n ] σ k R + . We now show that for each possible choice of σ the set B ∩ P σ contains a local minimizer of f . Let us note that, for all z ∈ S n -1 , the condition ‖| z | 2 -1 n 1 ‖ ≤ 1 n is equivalent to ‖ z ‖ 4 4 ≤ 1 n + 1 n 2 . This observation can be used to establish z k = 0 for all z ∈ B ∩ P σ and consequently, the sets B ∩ P σ and B ∩ P ν do not intersect for different binary vectors σ = ν . Now, for all z ∈ D := { z ∈ S n -1 : ‖ z ‖ 4 4 = 1 n + 1 n 2 } , we have f ( z ) ≥ β 2 ( n -1 + n -2 ) and setting z σ = σ/ √ n ∈ B ∩ P σ , we obtain

/negationslash

$$f ( z _ { \sigma } ) = \frac { 1 } { 2 } z _ { \sigma } ^ { T } A z _ { \sigma } + \frac { \beta } { 2 n } \leq \frac { \rho } { 2 } + \frac { \beta } { 2 n } < \frac { \beta } { 2 } \left [ \frac { 1 } { n } + \frac { 1 } { n ^ { 2 } } \right ].$$

Hence, the global minimizer y of the problem min z ∈B∩P σ f ( z ) satisfies ‖ y ‖ 4 4 &lt; 1 n + 1 n 2 . This implies that the Lagrange multiplier associated with the constraint ‖ z ‖ 4 4 ≤ 1 n + 1 n 2 is zero, and the KKT conditions for y reduce to grad f ( y ) = 0 . Due to B ∩ P σ ⊂ R 1 ∩ P σ , the Riemannian Hessian Hess f ( y ) is positive definite on the tangent space T M\{ } y 0 and thus, by Lemma 2.1, the points y is one of at least 2 n isolated local minimum of problem (1.1).

Next, we consider the case when β &gt; 18 n 3 n -1 ρ . We introduce the following refined versions of the R 1 and R 2 :

$$\bar { \mathcal { R } } _ { 1 } & = \bigcup _ { \sigma \in \{ \pm 1 \} ^ { n } } \left \{ z \in \mathbb { S } ^ { n - 1 } \, \colon \| z - \frac { 1 } { \sqrt { n } } \sigma \| \leq \frac { 2 } { 9 \sqrt { n } } \right \}, \\ \bar { \mathcal { R } } _ { 2 } & = \bigcap _ { \sigma \in \{ \pm 1 \} ^ { n } } \left \{ z \in \mathbb { S } ^ { n - 1 } \, \colon \| z - \frac { 1 } { \sqrt { n } } \sigma \| \geq \frac { 2 } { 9 \sqrt { n } }, \min _ { k \in [ n ] } z _ { k } ^ { 2 } \geq \frac { n - 1 } { 4 n ^ { 2 } } \right \}. \\. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &.$$

It can be easily seen that the set ¯ R 1 consists of 2 n non-intersecting components and that the three regions ¯ R 1 , ¯ R 2 , and R 3 cover the sphere S n -1 . Now, let z ∈ R ¯ 1 be arbitrary. Then, there exists σ ∈ {± } 1 n such that

$$\left | z _ { k } - \frac { \sigma _ { k } } { \sqrt { n } } \right | \leq \frac { 2 } { 9 \sqrt { n } } \ \text{ and } \ \left | z _ { k } + \frac { \sigma _ { k } } { \sqrt { n } } \right | \leq \frac { 2 0 } { 9 \sqrt { n } }, \ \forall \, k \in [ n ]. \\ \text{Hence, it follows $\|z|^{2}-\frac{1}{n}1\|_{\infty} \leq \frac{4 0}{81n} < \frac{1}{2n}$, which implies $\bar{R}_{1} \subset\mathcal{R}_{1}$. Thus, the}$$

∣ ∣ ∣ ∣ Hence, it follows ‖| z | 2 -1 n 1 ‖ ∞ ≤ 40 81 n &lt; 1 2 n , which implies ¯ R ⊂ R 1 1 . Thus, the strong convexity property also holds on ¯ R 1 . We now prove the Riemannian gradient is lower bounded on ¯ R 2 . For every z ∈ R ¯ 2 , there exists σ ∈ {± } 1 n such that σ z k k = | z k | for all k ∈ [ n ] . Consequently, we obtain

$$\| | z | ^ { 2 } - n ^ { - 1 } 1 \| _ { \infty } = \max _ { k \in [ n ] } \left | z _ { k } - \frac { \sigma _ { k } } { \sqrt { n } } \right | \left | z _ { k } \right | + \frac { 1 } { \sqrt { n } } \right | \geq \frac { \| z - \frac { \sigma } { \sqrt { n } } \| _ { \infty } } { \sqrt { n } } \geq \frac { 2 } { 9 n \sqrt { n } } \\ \text{and by mimicking the steps and estimates in the proof Lemma 5.3, we get}$$

∣ ∣ ∣ ∣ and by mimicking the steps and estimates in the proof Lemma 5.3, we get

$$2 [ \| \mathbf z \| _ { 6 } ^ { 6 } - \| \mathbf z \| _ { 4 } ^ { 8 } ] \geq \frac { n } { 4 } \left ( \frac { 2 } { 9 n \sqrt { n } } \right ) ^ { 2 } \left ( \frac { n - 1 } { 4 n ^ { 2 } } \right ) ^ { 2 } = \left ( \frac { n - 1 } { 3 6 n ^ { 3 } } \right ) ^ { 2 }.$$

Thus, the norm of the Riemannian gradient is lower bounded by

$$\| \text{grad} \, f ( \mathbf z ) \| \geq \frac { 1 } { \sqrt { 2 } } \left [ 2 \beta \sqrt { 2 [ \| \mathbf z \| _ { 6 } ^ { 6 } - \| \mathbf z \| _ { 4 } ^ { 8 } ] } - \rho \right ] \geq \frac { 1 } { \sqrt { 2 } } \left ( \beta \cdot \frac { n - 1 } { 1 8 n ^ { 3 } } - \rho \right ) > 0$$

and all local minima should need to be located in the set ¯ R 1 . Applying Lemma 5.5, each connected component of ¯ R 1 contains at most one local minimizer and hence, problem (1.1) has exactly 2 n local minima.

Although the local minima of problem (1.1) are not unique, all the local minima have similar objective function values.

Theorem 5.2 Suppose that β &gt; 18 n 3 n -1 ρ . Then, it follows

$$f ( y ) & - \min _ { z \in \mathbb { S } ^ { n - 1 } } f ( z ) \leq \frac { 1 } { 1 8 n } \cdot \min _ { z \in \mathbb { S } ^ { n - 1 } } f ( z ), \\ \cdot \quad \dots \cdot \cdot \cdot \cdot \quad \dots \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot$$

for all local minimizer y ∈ S n -1 of problem (1.1) .

Proof Without loss of generality, we can assume that the smallest eigenvalue of the matrix A is zero. Then, for all z ∈ S n -1 , we have f ( z ) ≥ β 2 ‖ z ‖ 4 4 ≥ β 2 n . According to the analysis in Corollary 5.1, each component B ∩ P σ , σ ∈ {± } 1 n , contains exactly one local minimizer y of problem (1.1) which is also the unique global minimizer of the restricted problem min z ∈B∩P σ f ( z ) . Together with (5.3), this yields

$$f ( y ) \leq f ( z _ { \sigma } ) \leq \frac { \rho } { 2 } + \frac { \beta } { 2 n } \leq \left [ 1 + \frac { n \rho } { \beta } \right ] f ( z ), \quad \forall \, z \in \mathbb { S } ^ { n - 1 }. \\ \intertext { a n d } \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \, \colon \end{array}$$

Finally, the estimate (5.4) can be established via minimizing the latter expression with respect to z and using the bound on β .

In the remainder of this section, we present an example demonstrating that the bound β ≈ Cρn 3 / 2 and the dependence on n 3 / 2 can not be further improved and that the strict-saddle property is violated whenever a smaller coefficient is chosen.

Example 1 Let C &gt; 0 and /epsilon1 &gt; 0 be given constants and suppose β = Cn 3 / 2 -/epsilon1 . In the following, we construct a specific matrix A ∈ R n × n and a point z ∈ S n -1 such that the three conditions of the strict-saddle property do not hold at z . We set

$$z _ { 1 } = \left [ \frac { 1 } { 3 n - 2 } \right ] ^ { \frac { 1 } { 2 } }, \quad z _ { k } = \left [ \frac { 3 } { 3 n - 2 } \right ] ^ { \frac { 1 } { 2 } }, \quad k \geq 2, \\ \vdash \vdash \vdash 4 \quad \theta \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \partial \, \colon$$

u = 2 β ‖ z ‖ 4 4 · z -2 β diag( | z | 2 ) z , and A = α ww T + zu T + uz T , where

$$w _ { 1 } = - \left [ \frac { 3 n - 3 } { 3 n - 2 } \right ] ^ { \frac { 1 } { 2 } }, \ \ w _ { k } = \left [ \frac { 1 } { ( 3 n - 2 ) ( n - 1 ) } \right ] ^ { \frac { 1 } { 2 } }, \, k \geq 2, \quad \alpha = - \frac { 1 6 \beta } { ( 3 n - 2 ) ^ { 2 } }. \\ \intertext { T h a n d a k a l l } \intertext { t h a n d a l l l } = 1 \left \| w \right \| = 1 \right \| \left \| w \right \| = 1 \right \| \partial \right \| 4 \left ( w \right ) \quad \partial / 2 \quad \partial \partial \right ) / 2 \quad \partial \partial \partial \right ) }$$

Then, we have ‖ z ‖ = ‖ w ‖ = 1 , ‖ z ‖ 4 4 = (9 n -8) / (3 n -2) 2 , and

$$\| \mathfrak { u } \| ^ { 2 } = 4 \beta ^ { 2 } [ \| z \| _ { 6 } ^ { 6 } - \| z \| _ { 4 } ^ { 8 } ] = 4 \beta ^ { 2 } \left [ \frac { 1 + 2 7 ( n - 1 ) } { ( 3 n - 2 ) ^ { 3 } } - \| z \| _ { 4 } ^ { 8 } \right ] = \frac { 4 8 ( n - 1 ) } { ( 3 n - 2 ) ^ { 4 } } \cdot \beta ^ { 2 }. \\ \prod \dots \alpha \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \dots \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \sigma \dots \ sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma \dots \sigma$$

Furthermore, it holds that u z T = w z T = 0 which implies A z = u and grad f ( z ) = 0 . The eigenvalues of the matrices α ww T and zu T + uz T are 0 , ..., 0 , α and ‖ u ‖ , 0 , ..., 0 , -‖ u ‖ , respectively. Thus, by Weyl's inequality, it follows for some constant ¯ C . Let us now consider an arbitrary vector v ∈ T M ∩ z S n -1 . We have ∑ n k =2 v 2 k = 1 -v 2 1 , v 1 + √ 3 ∑ n k =2 v k = 0 , and

$$\dots, \mathcal { U }, - \| \mathcal { U } \|, \text{espacutely. } \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{ $1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \text{$1$} \\ \rho & = \lambda _ { 1 } ( A ) - \lambda _ { n } ( A ) \leq 2 \| \| \mathcal { U } \| \| - \alpha = 8 \beta \cdot \frac { 2 + \sqrt { 3 n - 3 } } { ( 3 n - 2 ) ^ { 2 } } \leq \bar { C } n ^ { - \epsilon } = O ( n ^ { - \epsilon } ), \\ \text{for some constant $\bar{C}$} \ I \text{ at one now consider an arbitrary vector } \mathcal { V } \subset \mathcal { T } \ M \cap \mathbb { N } ^ { - 1 } \ \mathcal { W }$$

$$\mathbf v ^ { T } \mathbf w = v _ { 1 } w _ { 1 } - \frac { 1 } { \sqrt { 3 } } \left [ \frac { 1 } { ( 3 n - 2 ) ( n - 1 ) } \right ] ^ { \frac { 1 } { 2 } } v _ { 1 } = - \left [ \frac { 3 n - 2 } { 3 n - 3 } \right ] ^ { \frac { 1 } { 2 } } \cdot v _ { 1 }.$$

Fig. 2: Plot of the sets R 1 -R 3 for the problem (5.1). Figure (a) depicts the regions introduced in section 5.2 for a small interaction coefficient β = 0 2 . . The overlap of the sets R 1 -R 2 and R 2 -R 3 is shown in green. The set R 1 is the union of the yellow and the two surrounding green areas, while R 2 is the union of all green and light blue areas. The region R 3 coincides with the union of the dark blue sets and the enclosing green area. Figure (b) shows the regions introduced in section 5.1 for large β . Here, the (disjoint) yellow, turquoise, and dark blue areas directly correspond to the sets R 1 , R 2 , and R 3 , respectively. The red point marker again depicts the location of saddle points. Non-filled and filled diamond markers are used for local and global minima. Local and global maxima are marked by non-filled and filled squares.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00745v1-figure-906d099f-5352-488a-ad20-87148d6abdf5.jpg)

## Hence, we obtain

$$H _ { f } ( \mathbf z ) [ \mathbf v ] & = \alpha ( \mathbf v ^ { T } \mathbf w ) ^ { 2 } + 6 \beta \mathbf v ^ { T } \, \text{diag} ( | \mathbf z | ^ { 2 } ) \mathbf v - 2 \beta \| \mathbf z \| _ { 4 } ^ { 4 } \\ & = \frac { 3 n - 2 } { 3 n - 3 } \alpha v _ { 1 } ^ { 2 } - \frac { 1 2 \beta } { 3 n - 2 } v _ { 1 } ^ { 2 } + \frac { 1 8 \beta } { 3 n - 2 } - 2 \beta \| \mathbf z \| _ { 4 } ^ { 4 }. \\. \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \,.$$

Since H f ( z )[ v ] is linear in v 2 1 , its maximum and minimum value are attained at the boundary of the range interval [ ν, ν ] of v 2 1 . Notice that we have ν = 0 and ν can be found by discussing the optimization problem

$$\min _ { \mathbf v } - v _ { 1 } \ s. t. \ v _ { 1 } + \sqrt { 3 } \sum _ { k = 2 } ^ { n } v _ { k } = 0, \ \| \mathbf v \| = 1$$

and its associated KKT conditions. In particular, it can be shown that ν = (3 n -3) / (3 n -2) . In the case v 2 1 = 0 , we obtain H f ( z )[ v ] &gt; 0 and for v 2 1 = ν , we have

$$H _ { f } ( z ) [ v ] = \alpha - \frac { 3 6 \beta ( n - 1 ) } { ( 3 n - 2 ) ^ { 2 } } + \frac { 1 8 \beta } { 3 n - 2 } - \frac { 2 \beta ( 9 n - 8 ) } { ( 3 n - 2 ) ^ { 2 } } = \alpha + \frac { 1 6 \beta } { ( 3 n - 2 ) ^ { 2 } } = 0.$$

Consequently, we can infer min v ∈T M∩ z S n -1 H f ( z )[ v ] = 0 and H f ( z )[ v ] ≥ 0 for all v ∈ T M ∩ z S n -1 , which shows that none of the conditions of the strict-saddle property hold at z . Thus, the order n 3 / 2 can not be improved in the deterministic case.

## 5.2 Small interaction coefficient

In the following, we discuss the geometric landscape of problem (1.1) for small interaction coefficients. We additionally assume that there is a positive spectral gap δ = λ n -1 -λ n &gt; 0 between the two smallest eigenvalues of the matrix A . As shown by Marvcenko [58], this condition holds with probability 1 when A is a Gaussian random matrix.

Let us recall that the eigenvalue decomposition of A is given by A = PΛP T , where Λ = diag( λ , λ 1 2 , ..., λ n ) and P = ( p 1 , p 2 , ..., p n ) is an orthogonal matrix. Similar to the method used in section 5.1, we now divide S n -1 into three sub-regions:

- 1. (Strong convexity) R 1 := { z ∈ S n -1 : z = ∑ n k =1 α k p k , α 2 n ≥ (2+ γ β ) + ρ δ + ρ } . 2. (Large gradient) R 2 := { z ∈ S n -1 : ‖ A z ‖ 2 -( z T A z ) 2 ≥ ( 2 3 + γ ) 2 β 2 } .

An exemplary illustration of the sets R 1 -R 3 is given in Figure 2. We first show that the Riemannian Hessian is uniformly positive definite on R 1 .

- 3. (Negative curvature) R 3 := { z ∈ S n -1 : z = ∑ n k =1 α k p k , α 2 n ≤ δ -(4+ γ β ) δ + ρ }

Lemma 5.6 Suppose that the gap between the two smallest eigenvalues of the matrix A satisfies δ := λ n -1 -λ n &gt; 0 and let β, γ &gt; 0 be given. Then, for all z ∈ R 1 and all v ∈ T M ∩ z S n -1 , it follows H f ( z )[ v ] ≥ γβ .

Proof Let v ∈ T M ∩ z S n -1 be arbitrary with v = ∑ k ∈ [ n ] ν k p k . Then, we have ∑ k ∈ [ n ] α ν k k = 0 and ∑ k ∈ [ n ] ν 2 k = 1 and the Cauchy inequality implies

∣ ∣ Thus, it follows ν 2 n α 2 n ≤ (1 -ν 2 n )(1 -α 2 n ) and α 2 n ≤ 1 -ν 2 n and, due to ‖ z ‖ 4 4 ≤ 1 , we obtain

$$| \nu _ { n } \alpha _ { n } | = \left | \sum _ { k = 1 } ^ { n - 1 } \nu _ { k } \alpha _ { k } \right | \leq \left [ \sum _ { k = 1 } ^ { n - 1 } \nu _ { k } ^ { 2 } \right ] ^ { \frac { 1 } { 2 } } \left [ \sum _ { k = 1 } ^ { n - 1 } \alpha _ { k } ^ { 2 } \right ] ^ { \frac { 1 } { 2 } } = \sqrt { ( 1 - \nu _ { n } ^ { 2 } ) ( 1 - \alpha _ { n } ^ { 2 } ) }. \\ \text{ Thus, it follows } \nu _ { n } ^ { 2 } \alpha _ { n } ^ { 2 } \leq ( 1 - \nu _ { n } ^ { 2 } ) ( 1 - \alpha _ { n } ^ { 2 } ) \text{ and } \alpha _ { n } ^ { 2 } \leq 1 - \nu _ { n } ^ { 2 } \text{ and, due to } \| z \| _ { 4 } ^ { 4 } \leq 1,$$

$$\text{we obtain} \\ H _ { f } ( z ) [ \text{v} ] & = \text{v} ^ { T } A \text{v} - z ^ { T } A \text{z} + 6 \beta \sum _ { k = 1 } ^ { n } z _ { k } ^ { 2 } v _ { k } ^ { 2 } - 2 \beta \| z \| _ { 4 } ^ { 4 } \\ & \geq \sum _ { k = 1 } ^ { n } \lambda _ { k } ( \nu _ { k } ^ { 2 } - \alpha _ { k } ^ { 2 } ) - 2 \beta \\ & \geq \sum _ { k = 1 } ^ { n - 1 } ( \lambda _ { n } + \delta ) \nu _ { k } ^ { 2 } + \lambda _ { n } \nu _ { n } ^ { 2 } - \sum _ { k = 1 } ^ { n - 1 } ( \lambda _ { n } + \rho ) \alpha _ { k } ^ { 2 } - \lambda _ { n } \alpha _ { n } ^ { 2 } - 2 \beta \\ & = ( 1 - \nu _ { n } ^ { 2 } ) \delta - ( 1 - \alpha _ { n } ^ { 2 } ) \rho - 2 \beta \\ & \geq \alpha _ { n } ^ { 2 } \delta - ( 1 - \alpha _ { n } ^ { 2 } ) \rho - 2 \beta = \alpha _ { n } ^ { 2 } ( \delta + \rho ) - \rho - 2 \beta \geq \gamma \beta, \\ \text{as desired.}$$

as desired.

Next, we prove that the norm of the Riemannian gradient is strictly larger than zero on the set R 2 .

Lemma 5.7 For all z ∈ R 2 , it holds that ‖ grad f ( z ) ‖ 2 ≥ γβ .

.

Proof As in the proof of Lemma 5.3, we have

$$\| \left ( \text{diag} ( | z | ^ { 2 } ) - \| z \| _ { 4 } ^ { 4 } \cdot I _ { n } \right ) z \| ^ { 2 } = \| z \| _ { 6 } ^ { 6 } - \| z \| _ { 4 } ^ { 8 } \leq \| z \| _ { 4 } ^ { 6 } ( 1 - \| z \| _ { 4 } ^ { 2 } ) \leq \frac { 1 } { 4 } \left [ \frac { 3 } { 4 } \right ] ^ { 3 }, \\ \text{where the last estimate follows from the fact that the mapping $x\mapsto x^{6}-x^{8}$ atains} \\ \dots \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cd.$$

where the last estimate follows from the fact that the mapping x → x 6 -x 8 attains its global maximum at x = ± √ 3 2 . Hence, we obtain

↦

$$\Lambda & \quad z \quad \cdot \\ \| \text{grad} f ( z ) \| _ { 2 } & = \left \| ( A - z ^ { T } A z \cdot I _ { n } ) z + 2 \beta \left ( \text{diag} ( | z | ^ { 2 } ) - \| z \| _ { 4 } ^ { 4 } \cdot I _ { n } \right ) \cdot z \right \| \\ & \geq \| ( A - z ^ { T } A z \cdot I _ { n } ) z \| - 2 \beta \left \| ( \text{diag} ( | z | ^ { 2 } ) - \| z \| _ { 4 } ^ { 4 } \cdot I _ { n } ) \, z \right \| \\ & \geq \| ( A - z ^ { T } A z \cdot I _ { n } ) z \| - \frac { 3 \sqrt { 3 } } { 8 } \beta = \left [ \frac { 2 } { 3 } - \frac { 3 \sqrt { 3 } } { 8 } \right ] \beta + \gamma \beta \geq \gamma \beta. \\ \vdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots.$$

Finally, for points in the region R 3 , we construct directions along which the curvature of the objective function is strictly negative.

Lemma 5.8 Suppose that the gap between the two smallest eigenvalues of the matrix A satisfies δ := λ n -1 -λ n &gt; 0 and let γ &gt; 0 be given. If β ≤ (4 + γ ) -1 δ , then for all z ∈ R 3 there exists v ∈ T M ∩ z S n -1 such that H f ( z )[ v ] ≤ -γβ .

Proof By the Cauchy's inequality and using the estimate | 3 x -x 2 | ≤ 2 , x ∈ [0 , 1] , we have

$$\sum _ { k \in [ n ] } 3 z _ { k } ^ { 2 } v _ { k } ^ { 2 } - z _ { k } ^ { 4 } & \leq 3 \| z \| _ { 4 } ^ { 2 } \| \nu \| _ { 4 } ^ { 2 } - \| z \| _ { 4 } ^ { 4 } \leq 3 \| z \| _ { 4 } ^ { 2 } - \| z \| _ { 4 } ^ { 4 } \leq 2. \\.. \quad.. \quad.. \quad.. \quad.. \quad.. \quad.. \quad.. \quad..$$

Next, we choose a specific direction v = ∑ k ∈ [ n ] ν k p k that satisfies H f ( z )[ v ] ≤ -γβ , z T v = k ∈ [ n ] α ν k k = 0 and ‖ v ‖ 2 = k ∈ [ n ] ν 2 k = 1 .

∑ ∑ Case 1. α n = 0 . Let us set ν n = 1 and ν k = 0 for all k ∈ [ n -1] . Then, we obtain

$$\text{ obtain} \\ H _ { f } ( \mathbf z ) [ v ] & = \mathbf v ^ { T } A \mathbf v - \mathbf z ^ { T } A \mathbf z + 2 \beta \sum _ { k = 1 } ^ { n } ( 3 \mathbf z _ { k } ^ { 2 } v _ { k } ^ { 2 } - \mathbf z _ { k } ^ { 4 } ) \\ & \leq \sum _ { k = 1 } ^ { n } \lambda _ { k } ( \nu _ { k } ^ { 2 } - \alpha _ { k } ^ { 2 } ) + 4 \beta = \lambda _ { n } - \sum _ { k = 1 } ^ { n - 1 } \lambda _ { k } \alpha _ { k } ^ { 2 } + 4 \beta \\ & \leq \lambda _ { n } - ( \lambda _ { n } + \delta ) \sum _ { k = 1 } ^ { n - 1 } \alpha _ { k } ^ { 2 } + 4 \beta = - \delta + 4 \beta \leq - \gamma \beta, \\ \text{where the last inequality immediately follows from } \beta \leq \frac { \delta } { 4 + \gamma }. \\ \sim \quad \hat { \lambda } \hat { \lambda } \hat { \lambda } - \hat { \lambda } - \delta - ( 4 + \sum \beta \hat { \lambda } \hat { \lambda } \hat { \lambda } \hat { \lambda } \hat { \lambda } \hat { \lambda } \hat { \lambda } \hat { \lambda } \hat { \lambda } \hat { \lambda } \hat { \lambda } \hat { \lambda } \hat { \lambda } \hat { \lambda } \hat { \lambda } \hat { \lambda } \hat { \lambda } \hat { \lambda } \hat { \lambda } \hat { \lambda } \hat { \lambda } \hat { \lambda } \hat { \lambda } \hat { \lambda } \hat { \lambda } \hat { \lambda } \hat { \lambda } \hat { \lambda } \hat { \lambda } \hat { \lambda } \hat { \lambda } \hat { \lambda } \hat { \lambda } \hat { \lambda } \tau.$$

$$C a s e \, 2. \, 0 < \alpha _ { n } ^ { 2 } \leq \frac { \delta - ( 4 + \gamma ) \beta } { \delta + \rho }. \, \text{ In this situation, we set } ^ { \cdot \cdot \cdot \cdot \cdot }$$

where the last inequality immediately follows from β ≤ δ 4+ γ .

$$\lambda \cdot r \\ \nu _ { k } = \eta \alpha _ { k }, \quad \forall \, k \in [ n - 1 ], \quad \nu _ { n } = - \sqrt { 1 - \alpha _ { n } ^ { 2 } }, \quad \eta = \frac { \alpha _ { n } } { \sqrt { 1 - \alpha _ { n } ^ { 2 } } }. \\ \text{With this choice, we have $z^{T}$} \nu = \eta ( 1 - \alpha _ { n } ^ { 2 } ) - \alpha _ { n } \sqrt { 1 - \alpha _ { n } ^ { 2 } } \, = \, 0 \text{ and } \| \mathbf v \| ^ { 2 } \, =$$

With this choice, we have z T v = η (1 -α 2 n ) -α n √ 1 -α 2 n = 0 and ‖ v ‖ 2 = ( η 2 +1)(1 -α 2 n ) = 1 , i.e., it holds that v ∈ T M∩ z S n -1 . Similar to the calculations in the proof of Lemma 5.6, we now get

$$H _ { f } ( z ) [ \mathbf v ] = \mathbf v ^ { T } A \mathbf v - z ^ { T } A \mathbf z + 2 \beta \sum \nolimits _ { k = 1 } ^ { n } ( 3 z _ { k } ^ { 2 } v _ { k } ^ { 2 } - z _ { k } ^ { 4 } )$$

$$\frac { \text{enumerate} \ a x y s i o \ a q u a c o p o m i z a n p o w e n } { \leq \sum _ { k = 1 } ^ { n } \lambda _ { k } ( \nu _ { k } ^ { 2 } - \alpha _ { k } ^ { 2 } ) + 4 \beta } \\ \leq \sum _ { k = 1 } ^ { n - 1 } ( ( \lambda _ { n } + \rho ) \nu _ { k } ^ { 2 } - ( \lambda _ { n } + \delta ) \alpha _ { k } ^ { 2 } ) + \lambda _ { n } ( \nu _ { n } ^ { 2 } - \alpha _ { n } ^ { 2 } ) + 4 \beta } \\ = \rho \cdot \sum _ { k = 1 } ^ { n - 1 } \nu _ { k } ^ { 2 } - \delta \cdot \sum _ { k = 1 } ^ { n - 1 } \alpha _ { k } ^ { 2 } + 4 \beta = \rho ( 1 - \nu _ { n } ^ { 2 } ) - \delta ( 1 - \alpha _ { n } ^ { 2 } ) + 4 \beta \\ = \rho \eta ^ { 2 } ( 1 - \alpha _ { n } ^ { 2 } ) + \delta \alpha _ { n } ^ { 2 } - \delta + 4 \beta = ( \delta + \rho ) \alpha _ { n } ^ { 2 } - \delta + 4 \beta \leq - \gamma \beta. \\ \text{Combining the latter two cases, we can conclude the proof of Lemma $5.8$}.$$

Combining the latter two cases, we can conclude the proof of Lemma 5.8.

We now verify that f has the strict-saddle property whenever β is chosen sufficiently small.

Theorem 5.3 Suppose that the gap between the two smallest eigenvalues of the matrix A satisfies δ := λ n -1 -λ n &gt; 0 and let γ &gt; 0 be given. If β ≤ [2( 7 3 + )+( γ 2 3 + γ ) ρ δ ] -1 δ =: b γ , then f has the ( γβ, γβ, γβ ) -strict-saddle property.

Proof By Lemmata 5.6-5.8, we know that the function f satisfies the strong convexity, large gradient, and negative curvature property on the three different set R 1 , R 2 , and R 3 , respectively. To finish the proof, we need to show that those regions actually cover the whole sphere S n -1 . Combining these observations, we can then conclude that f has the ( γβ, γβ, γβ ) -strict-saddle property.

In order to prove R ∪ R 1 2 ∪ R 3 = S n -1 , we only need to verify that for all z = ∑ k ∈ [ n ] α k p k ∈ S n -1 with

$$\frac { \delta - ( 4 + \gamma ) \beta } { \delta + \rho } \leq \alpha _ { n } ^ { 2 } \leq \frac { ( 2 + \gamma ) \beta + \rho } { \delta + \rho },$$

we have ‖ A z ‖ 2 -( z T A z ) 2 ≥ ( 2 3 + γ ) 2 β 2 . Using the bounds (5.5), it follows

$$\Psi \ u v { - | | | \ u \lambda | | } \quad \lambda \ u v { - | | \ v \ v { - | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
 \| A z \| ^ { 2 } - ( z ^ { T } A z ) ^ { 2 } & = \frac { 1 } { 2 } \sum _ { k, j \in [ n - 1 ] } \alpha _ { k } ^ { 2 } \alpha _ { j } ^ { 2 } ( \lambda _ { k } - \lambda _ { j } ) ^ { 2 } \geq \sum _ { k \in [ n - 1 ] } \alpha _ { k } ^ { 2 } \alpha _ { n } ^ { 2 } \delta ^ { 2 } \\ & = ( 1 - \alpha _ { n } ^ { 2 } ) \alpha _ { n } ^ { 2 } \delta ^ { 2 } \geq \frac { ( \delta - ( 4 + \gamma ) \beta ) ( \delta - ( 2 + \gamma ) \beta ) } { ( \delta + \rho ) ^ { 2 } } \delta ^ { 2 }. \\ \text{where the first identity was established in the nroof of } I \ e m a 5 3 \text{ Rearranino} \text{ the}$$

where the first identity was established in the proof of Lemma 5.3. Rearranging the terms in the latter estimate, we see that our claim is satisfied if

$$\ell ( \beta ) & \coloneqq \left [ ( \frac { 2 } { 3 } + \gamma ) ^ { 2 } ( \delta + \rho ) ^ { 2 } - ( 4 + \gamma ) ( 2 + \gamma ) \right ] \beta ^ { 2 } + 2 ( 3 + \gamma ) \delta ^ { 3 } \beta - \delta ^ { 4 } \leq 0 \\ \text{for all } \beta & \leq b _ { \gamma }. \, \text{Since the unique nonnegative zero of the quadratic polynomial } \ell \text{ is}$$

for all β ≤ b γ . Since the unique nonnegative zero of the quadratic polynomial /lscript is given by

$$\bar { \beta } & = \left [ 3 + \gamma + \sqrt { 1 + ( \frac { 2 } { 3 } + \gamma ) ^ { 2 } ( 1 + \frac { \varrho } { \delta } ) ^ { 2 } } \right ] ^ { - 1 } \delta, \\ \text{sh the nroof} \, \text{hv noticino} \, \bar { \beta } > h.$$

we can finish the proof by noticing ¯ β ≥ b γ .

Finally, as a counterpart of Corollary 5.1, we can establish the uniqueness of local minima as a consequence of the strict-saddle property.

Corollary 5.2 Under the conditions of Theorem 5.3, the problem (1.1) has exactly two local minima which are also global minima.

Proof Note that all local minima locate in R 1 and that R 1 consists of two symmetrical non-intersecting subsets. We now consider one of the subsets ¯ R 1 := { z ∈ S n -1 : z = ∑ k ∈ [ n ] α k p k , α n ≥ √ ν } where ν := ( δ + ) ρ -1 [(2 + γ β ) + ] ρ . Using ‖ z -p n ‖ 2 = 2 -2 α n , for z ∈ R ¯ 1 , an equivalent definition of this subset is given by

In order to apply Lemma 5.5, we need to verify 2 -2 √ ν ≤ 1 or, equivalently, ν ≥ 1 4 . However, due to γ, β &gt; 0 and ρ ≥ δ &gt; 0 , we have ν ≥ ρ δ + ρ ≥ 1 2 &gt; 1 4 . Similary, the second subset can be represented by ¯ R 2 := { z ∈ S n -1 : ‖ z + p n ‖ 2 ≤ 2 -2 √ ν } . Then, by Lemma 5.5, there exist exactly two equivalent local minima which are also global minima of problem (1.1).

$$- \lambda _ { 1 } \quad \omega _ { n }, \, \alpha \, \alpha \, \lambda \, \colon \, \nu _ { 1 }, \, \alpha \, \alpha \, \colon \, \nu _ { 2 } \, \omega _ { 3 } \, \omega _ { 4 } \, \omega _ { 5 } \, \omega _ { 6 } \, \omega _ { 7 } \, \omega _ { 8 } \, \omega _ { 9 } \, \omega _ { 9 } \, \omega _ { 9 } \, \omega _ { 9 } \, \omega _ { 9 } \, \omega _ { 9 } \, \omega _ { 9 } \, \omega _ { 9 } \, \omega _ { 9 } \, \omega _ { 9 } \, \omega _ { 9 } \, \omega _ { 9 } \, \omega _ { 9 } \, \omega _ { 9 } \, \omega _ { 9 } \, \omega _ { 9 } \, \omega _ { 9 } \, \omega _ { 9 } \, \omega _ { 9 } \, \omega _ { 9 } \, \omega _ { 9 } \, \omega _ { 9 } \, \omega _ { 9 } \\ \bar { \mathcal { R } } _ { 1 } = \left \{ z \in \mathbb { S } ^ { n - 1 } \, \colon \left \| z - \mathbf p _ { n } \right \| ^ { 2 } \leq 2 - 2 \sqrt { \nu } \right \}. \\ \text{apply Lemma $5.5$, we need to verify $2-2$} \sqrt { \nu } \leq 1 \, \text{or, equivale} \, \binom { 1 } { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ {\alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha \, \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \alpha } \, \cos _ { \beta } \, \cos _ { \beta } \, \cos _ { \beta } \, \cos _ { \beta } \, \cos _ { \beta } \, \cos _ { \beta } \, \cos _ { \beta } \, \cos _ { \beta } \, \cos _ { \beta } \, \cos _ { \beta } \, \cos _ { \beta } \, \cos _ { \beta } \, \cos _ { \beta } \, \cos _ { \beta } \, \cos _ { \beta } \, \cos _ { \beta } \, \cos _ { \beta } \, \cos _ { \beta } \, \cos _ { \beta } \, \cos _ { \beta } \, \cos _ { \beta } \, \cos _ { \beta } \, \cos _ { \beta }$$

## 6 Estimation of the Kurdyka-Łojasiewicz Exponent

In this section, we estimate the Kurdyka-Łojasiewicz (KL) exponent of problem (1.1). Specifically, we want to find the largest θ ∈ (0 , 1 2 ] such that for all stationary points z of problem (1.1), the Łojasiewicz inequality,

$$( 6. 1 ) \quad \ \ | f ( \mathbf y ) - f ( \mathbf z ) | ^ { 1 - \theta } \leq \eta _ { \mathbf z } \| \text{grad} f ( \mathbf y ) \|, \ \forall \, \mathbf y \in B ( \mathbf z, \delta _ { \mathbf z } ) \cap \mathbb { C S } ^ { n - 1 },$$

holds with some constants δ z , η z &gt; 0 . The largest possible θ is called the KL exponent of problem (1.1).

As already mentioned, the Łojasiewicz inequality (6.1) plays a fundamental role in nonconvex optimization and is frequently utilized to analyze the local convergence properties of nonconvex optimization methods, [6,7,8,15,63,16,53,50]. In [6], Attouch and Bolte derived an abstract KL-framework based on the Łojasiewicz inequality that allows to establish global convergence and local convergence rates for general optimization approaches satisfying certain function reduction and asymptotic step size safe-guard conditions. In particular, if θ ≥ 1 2 , then the corresponding iterates can be shown to converge linearly. Otherwise, if θ ∈ (0 , 1 2 ) , the iterates converge at a θ 1 -2 θ

sublinear rate O t ( -) . By introducing the auxiliary problem

$$& ( 6. 2 ) \quad \min _ { z \in \mathbb { C } ^ { n } } \, \hat { f } ( z ), \quad \hat { f } ( z ) \coloneqq \begin{cases} f ( z ) & \text{if} \, z \in \mathbb { C S } ^ { n - 1 }, \\ + \infty & \text{otherwise}, \end{cases} \\ \cdot \quad \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \end{cases}.$$

the original problem (1.1) can be treated as the minimization of an extended realvalued, proper, and lower semicontinuous function which allows to apply existing results and the rich KL theory for nonsmooth problems, see, e.g., [55,47,13,12,14].

In the nonsmooth setting, the Riemannian gradient, appearing in (6.1), is typically substituted by the nonsmooth slope of ˆ f which is based on the Fr´ echet and limiting

subdifferential of ˆ f . In our case, if problem (6.2) is restricted to the real space R n , the limiting subdifferential and nonsmooth slope of ˆ f at z ∈ S n -1 can be expressed as ∂f ˆ ( z ) = {∇ f ( z ) + µ z : µ ∈ R } and

$$\underset { g \in \partial \hat { f } ( z ) } { \arg \min } \| g \| = ( I - z z ^ { T } ) \nabla f ( z ) = \text{grad} \, f ( z ).$$

Hence, the Riemannian-type Łojasiewicz inequality (6.1) coincides with the standard notion and KL framework used in nonsmooth optimization. Our goal is now to show that the KL exponent of (1.1) is at least 1 4 under suitable conditions.

Throughout this section, we assume that z ∈ CS n -1 is a stationary point of problem (1.1). Furthermore, y ∈ CS n -1 denotes a neighboring point of z and we set ∆ = y -z . We now collect and present some preparatory notations and computational results that will be used in the following derivations. Since z is a stationary point of problem (1.1), we have

$$( 6. 3 ) \quad \ H z = A z + 2 \beta \text{diag} ( | z | ^ { 2 } ) z - 2 \lambda z = 0, \ \ 2 \lambda = z ^ { * } A z + 2 \beta \| z \| _ { 4 } ^ { 4 }$$

and as proved in (2.5), it holds that

$$( 6. 4 ) \quad f ( y ) - f ( \mathbf z ) = \frac { 1 } { 2 } \mathbf y ^ { * } H \mathbf y + \frac { \beta } { 2 } \| \tau \| ^ { 2 }, \ \tau _ { k } \coloneqq | y _ { k } | ^ { 2 } - | z _ { k } | ^ { 2 }, \ \ k \in [ n ].$$

The norm of the Riemannian gradient can be expressed as follows

$$\text{$movomon and moum cannot can occur as novoids} \\ \| \text{grad} f ( \mathbf y ) \| ^ { 2 } & = \frac { 1 } { 2 } \| P _ { \mathbf y } ^ { \perp } [ H + 2 \beta \text{diag} ( \tau ) ] \mathbf y \| ^ { 2 } \\ & = \frac { 1 } { 2 } \| [ H + 2 \beta \text{diag} ( \tau ) ] \mathbf y \| ^ { 2 } - \frac { 1 } { 2 } ( \mathbf y ^ { * } [ H + 2 \beta \text{diag} ( \tau ) ] \mathbf y ) ^ { 2 } \\ & = \frac { 1 } { 2 } \mathbf y ^ { * } H ^ { 2 } \mathbf y - \frac { 1 } { 2 } ( \mathbf y ^ { * } H \mathbf y ) ^ { 2 } + 2 \beta ^ { 2 } \mathbf y ^ { * } \text{diag} ( | \tau | ^ { 2 } ) \mathbf y - 2 \beta ^ { 2 } ( \mathbf y ^ { * } \text{diag} ( \tau ) \mathbf y ) ^ { 2 } \\ ( 6. 5 ) & \quad \ \ + 2 \beta \mathbf y ^ { * } H \text{diag} ( \tau ) \mathbf y - 2 \beta ( \mathbf y ^ { * } H \mathbf y ) ( \mathbf y ^ { * } \text{diag} ( \tau ) \mathbf y ), \\ \text{where} \ P _ { \nu } ^ { \perp } \ = \ I _ { n } - \mathbf y \mathbf y ^ { * } \text{ is the orthogonal projection onto the space } [ \text{span} \{ \mathbf y \} | ^ { \perp }$$

where P ⊥ y = I n -yy ∗ is the orthogonal projection onto the space [span { y } ] ⊥ Finally, let us define the index sets

$$\mathcal { A } = \{ k \colon z _ { k } = 0 \}, \ \mathcal { I } = \{ k \colon z _ { k } \neq 0 \}$$

/negationslash and r + = min k ∈I r k &gt; 0 . Notice that we have τ k = t 2 k ≥ 0 for all k ∈ A .

We first show that the Łojasiewicz inequality holds with θ = 1 4 at those stationary points where H = 0 (we also refer to the remark after this lemma).

Lemma 6.1 Suppose z is an arbitrary point on CS n -1 . Then, the inequality

$$( 6. 6 ) \quad \ \| \tau \| ^ { \frac { 3 } { 2 } } \leq \eta _ { \mathbf z } \| P _ { y } ^ { \perp } \text{diag} ( \tau ) \mathbf y \|, \quad \forall \, \mathbf y \in B ( \mathbf z, \delta _ { \mathbf z } ) \cap \mathbb { C S } ^ { n - 1 }$$

holds for some constants η , δ z z &gt; 0 .

Proof In the case τ = 0 , we have ‖ τ ‖ = ‖ P ⊥ y diag( τ ) y ‖ = 0 and consequently, the inequality (6.6) holds trivially with θ = 1 2 . Next, let us assume A /negationslash = ∅ and let us introduce the polar coordinates z k = r k e iθ k , y k = t k e iφ k for r k , t k ≥ 0 , θ k , φ k ∈ [0 , 2 π ] , and all k ∈ [ n ] . A straightforward calculation yields | ∆ k | 2 = t 2 k -2 r k t k cos( θ k -φ k ) + r 2 k ≥ ( t k -r k ) 2 and hence, it follows

$$| \tau _ { k } | = ( t _ { k } + r _ { k } ) | t _ { k } - r _ { k } | \leq ( 2 r _ { k } + | \Delta _ { k } | ) | \Delta _ { k } |, \ \forall \, k \in \mathcal { I },$$

and τ k = t 2 k = | ∆ k | 2 for all k ∈ A . Using ∑ k ∈I τ k = -∑ k ∈A τ k = -‖ τ A ‖ 1 , the estimates ‖ τ A ‖ 2 1 ≤ |A|‖ τ A ‖ 2 and

$$\frac { 1 } { 2 } \sum _ { k, j \in \mathcal { I$$

and setting m := |I| ≥ 1 , we obtain

$$\| \tau \| ^ { 2 } \leq \frac { 1 } { 2 m$$

Furthermore, it holds that

$$\text{Furthermore, it holds that} \\ 2 \| P _ { y } ^ { \per$$

Next, defining δ z := min { 1 min , { r 2 + , 1 } / 6 } , it follows ‖ τ I ‖ ∞ ≤ min { r 2 + , 1 } / 2 for all y ∈ B δ z ( z ) . Moreover, the latter condition implies | y k | 2 = t 2 k &gt; r 2 + / 2 for all k ∈ I and thus, it holds that

$$2 \sum _ { k \in \mathcal { A } } \sum _ { j \in$$

3 3 .

Similarly, we can show ∑ k,j ∈A τ k τ j ( τ k -τ j ) 2 = 2 ‖ τ A ‖ ‖ 1 τ A ‖ 3 3 -2 ‖ τ A ‖ 4 ≥ 0 . Due to ‖ τ I ‖ ∞ ≤ 1 / 2 , we have | τ k -τ j | ≤ 1 for all k, j ∈ I and consequently,

it follows ∑ k,j ∈I ( τ k -τ j ) 2 ≥ ∑ k,j ∈I | τ k -τ j | 3 . Together and using the estimate ‖ w ‖ 3 ≤ √ p ‖ w ‖ 3 3 , w ∈ C p , we finally obtain

$$\begin{array} {$$

Thus, the Łojasiewicz-type inequality (6.6) is satisfied with η z := ( n m ) 1 5 . c -1 .

Remark 5 If z ∈ CS n -1 is a stationary point of problem (1.1) with H = 0 , then we have f ( y ) -f ( z ) = ( β/ 2) ‖ τ ‖ 2 and ‖ grad f ( z ) ‖ = √ 2 β P ‖ ⊥ y diag( τ ) y ‖ and thus, Lemma 6.1 implies that the Łojasiewicz inequality (6.1) holds with θ = 1 4 . Moreover, this result can be used to show that the KL exponent can not be larger than 1 4 for general stationary points.

Remark 6 The proof of Lemma 6.1 implies that the exponent 3 2 can be improved to 1 if the index set A is empty. More generally, it can be shown that the Łojasiewicz-type inequality (6.6) holds with exponent 1 along directions y ∈ B ( z , δ z ) ∩ CS n -1 with y A = 0 .

Next, we prove that the KL exponent is at least 1 4 when the matrix A is diagonal.

Theorem 6.1 Let A = diag( a ) ∈ C n × n , a ∈ R n , be a diagonal matrix. Then, the KL exponent of problem (1.1) is 1 4 .

Proof In the case τ = 0 , we have f ( y ) -f ( z ) = 1 2 y ∗ H y and 2 ‖ grad f ( y ) ‖ 2 = y ∗ H 2 y -( y ∗ H y ) 2 . We now decompose y as follows

$$y = \mathfrak { u } + \mathbf v, \ \ H \mathfrak { u } = 0, \ \| H \mathbf v \| \geq \sigma _ { - } ( H ) \| \mathbf v \|, \ \text{ and } \ \mathfrak { u } ^ { * } \mathbf v = 0,$$

where σ -( H ) denotes smallest positive singular value of H . Furthermore, let σ + ( H ) ≥ 0 be the maximum singular value of H . It holds that

$$f ( \mathbf y ) - f ( \mathbf z ) \leq \frac { \sigma _ { + } ( H ) } { 2 } \| \mathbf v \| ^ { 2 }, \ \ \| \text{grad} f ( \mathbf y ) \| ^ { 2 } \geq \frac { \sigma _ { - } ( H ) ^ { 2 } } { 2 } \| \mathbf v \| ^ { 2 } - \frac { \sigma _ { + } ( H ) ^ { 2 } } { 2 } \| \mathbf v \| ^ { 4 }.$$

2 2 1

/negationslash

Thus, due to ‖ v ‖ ≤ ‖ ∆ ‖ , the inequality (6.1) is satisfied with exponent θ = 2 . Next, we consider the general case τ = 0 . In this situation, we have A [ AI ] = 0 , H [ IA ] = A [ IA ] = 0 and the KKT conditions imply

$$a _ { k } + 2 \beta | z _ { k } | ^ { 2 } - 2 \lambda = \underset { \mu } { 0 } \quad \forall \ k \in \mathcal { I } \quad \Longrightarrow \quad H _ { [ \mathcal { I } \mathcal { I } ] } = 0$$

and hence, due to τ k = | ∆ k | 2 = | y k | 2 = t 2 k for all k ∈ A , it follows

$$\hat { y } ^ { * } \text{diag} ( \tau ) H \mathbf y & = y _ { \mathcal { A } } ^ { * } \text{diag} ( \tau _ { \mathcal { A } } ) H _ { [ \mathcal { A } \cdot ] } \Delta + y _ { \mathcal { I } } ^ { * } \text{diag} ( \tau _ { \mathcal { I } } ) H _ { [ \mathcal { I } \cdot ] } \Delta \\ & = \Delta _ { \mathcal { A } } ^ { * } \text{diag} ( \tau _ { \mathcal { A } } ) A _ { [ \mathcal { A } \mathcal { A } ] } \Delta _ { \mathcal { A } } - 2 \lambda \| \tau _ { \mathcal { A } } \| ^ { 2 } = \sum _ { k \in \mathcal { A } } ( a _ { k } - 2 \lambda ) \tau _ { k } ^ { 2 }.$$

Using Young's inequality, t 2 k ≤ 1 , and τ k = t 2 k for all k ∈ A , it follows

$$y ^ { * } H y \cdot y ^ { * } \text{diag} ( \tau ) y = y ^ { * } H y \left [ \| \tau _ { \mathcal { A } } \| ^ { 2 } + \sum _ { k \in \mathcal { I } } t _ { k } ^ { 2 } \tau _ { k } \right ] & \leq \frac { 2 | y ^ { * } H y | ^ { q } } { q } + \frac { \| \tau _ { \mathcal { A } } \| ^ { 2 p } + \| \tau _ { \mathcal { I } } \| _ { 1 } ^ { p } } { p } \\. &. &. &. &.$$

/negationslash for p &gt; 1 and q = 1 + 1 p -1 . Let us now introduce the index set B := { k ∈ A : a k -2 λ = 0 } and let us define h -:= min k ∈B | a k -2 λ | and h + := max k ∈B | a k -2 λ | . Then, due to ‖ τ B ‖ 2 = ‖ y B ‖ 4 4 and (6.5), and applying the estimates derived in the proof of Lemma 6.1, we obtain

$$\text{prot} & \text{$of$ Lemma $6.1$, we obtain} \\ & \| \text{grad} \, f ( \boldsymbol y ) \| ^ { 2 } \\ & \geq \frac { h _ { 2 } } { 2 } \| y _ { \mathcal { B } } \| ^ { 2 } - \frac { h _ { + } ^ { 2 } } { 2 } \| y _ { \mathcal { B } } \| ^ { 4 } - \frac { 4 \beta } { q } h _ { + } ^ { q } \| y _ { \mathcal { B } } \| ^ { 2 q } - \frac { 2 \beta } { p } [ \| \tau _ { \mathcal { A } } \| ^ { 2 p } + \| \tau _ { \mathcal { T } } \| _ { 1 } ^ { p } ] \\ & \quad - 2 \beta h _ { + } \| \tau _ { \mathcal { B } } \| ^ { 2 } + 2 \beta ^ { 2 } \boldsymbol y ^ { * } \text{diag} ( | \tau | ^ { 2 } ) \boldsymbol y - 2 \beta ^ { 2 } ( \boldsymbol y ^ { * } \text{diag} ( \tau ) \boldsymbol y ) ^ { 2 } \\ & \geq \frac { h _ { 2 } ^ { 2 } } { 2 } \| y _ { \mathcal { B } } \| ^ { 2 } - o ( \| y _ { \mathcal { B } } \| ^ { 2 } ) + \frac { \beta ^ { 2 } r _ { + } ^ { 2 } } { 4 } \sum _ { k, j \in \mathcal { Z } } | \tau _ { k } - \tau _ { j } | ^ { 2 } + \beta ^ { 2 } r _ { + } m \| \tau _ { \mathcal { A } } \| _ { 3 } ^ { 3 } \\ & \quad - 2 \beta p ^ { - 1 } [ \| \tau _ { \mathcal { A } } \| ^ { 2 p } + \| \tau _ { \mathcal { T } } \| _ { 1 } ^ { p } ] \\ & \text{for} \, \| y _ { \mathcal { B } } \| \to 0, \, m \coloneqq | \mathcal { I } |, \, \text{and} \, \boldsymbol y \text{ sufficiently close to $z.$ By $(6.7), we have}$$

for ‖ y B ‖ → 0 , m := |I| , and y sufficiently close to z . By (6.7), we have

$$\| \tau _ { \mathcal { I } } \| _ { 1 } ^ { 4 } \leq m ^ { 2 } \| \tau _ { \mathcal { I } } \| ^ { 4 } & \leq \left [ \frac { 1 } { 2 } \sum _ { k, j \in \mathcal { I } } | \tau _ { k } - \tau _ { j } | ^ { 2 } + | \mathcal { A } | \| \tau _ { \mathcal { A } } \| ^ { 2 } \right ] ^ { 2 } \\ & \leq \left [ \sum _ { k, j \in \mathcal { I } } | \tau _ { k } - \tau _ { j } | ^ { 2 } \right ] ^ { 2 } + 2 ( n - m ) ^ { 2 } \| \tau _ { \mathcal { A } } \| ^ { 4 } \\ \text{and consequently, setting $p=4$, we can choose $\|\Delta\|$ (and thus $\|\tau\|$ and $\|y_{B}\|)$ suffix}$$

and consequently, setting p = 4 , we can choose ‖ ∆ ‖ (and thus ‖ τ ‖ and ‖ y B ‖ ) sufficiently small, such that

$$\| \text{grad} \, f ( \boldsymbol y ) \| ^ { 2 } & \geq \eta _ { 1 } \left [ \| y _ { \mathcal { B } } \| ^ { 2 } + \sum _ { k, j \in \mathcal { I } } | \tau _ { k } - \tau _ { j } | ^ { 2 } + \| \tau _ { \mathcal { A } } \| ^ { 3 } _ { 3 } \right ] \\ & \geq \eta _ { 2 } \left [ \| y _ { \mathcal { B } } \| ^ { 2 } + \sum _ { k, j \in \mathcal { I } } | \tau _ { k } - \tau _ { j } | ^ { 2 } + \| \tau _ { \mathcal { A } } \| ^ { 2 } \right ] ^ { \frac { 3 } { 2 } } \\ \text{ind} \, f ( \boldsymbol y ) - f ( \boldsymbol z ) \leq \eta _ { 3 } [ \| y _ { \mathcal { B } } \| ^ { 2 } + \sum _ { k. i \in \mathcal { I } } | \tau _ { k } - \tau _ { j } | ^ { 2 } + \| \tau _ { \mathcal { A } } \| ^ { 2 } ] \text{ for suitable} \, \eta _ { 1 }, \eta _ { 2 }, \eta _ { 3 } > 0$$

and f ( y ) -f ( z ) ≤ η 3 [ ‖ y B ‖ 2 + ∑ k,j ∈I | τ k -τ j | 2 + ‖ τ A ‖ 2 ] for suitable η , η 1 2 , η 3 &gt; 0 . This shows that the Łojasiewicz inequality is satisfied with θ = 1 4 .

Finally, we derive the KL exponent in the real case for global minimizers characterized by the positive semidefiniteness condition in Theorem 2.1.

Theorem 6.2 Suppose A ∈ R n × n is a symmetric matrix and z is a stationary point of problem (1.1) satisfying

$$H \succeq 0,$$

where H is defined in (2.4) . Then, the KL exponent of problem (1.1) at z is at least 1 4 .

Proof Without loss of generality we assume β = 1 . Let y ∈ S n -1 be arbitrary and let us set ∆ = y -z , and

$$\gamma _ { 1 } = \sum _ { k \in \mathcal { I } } z _ { k } ^ { 3 } \Delta _ { k }, \ \gamma _ { 2 } = \sum _ { k \in \mathcal { I } } z _ { k } ^ { 2 } \Delta _ { k } ^ { 2 }, \ \gamma _ { 3 } = \sum _ { k \in \mathcal { I } } z _ { k } \Delta _ { k } ^ { 3 }, \ \gamma _ { 4 } = \| \Delta \| _ { 4 } ^ { 4 }.$$

Based on the representation grad f ( y ) = P ⊥ y [ H + 2 diag( τ )] y , we now introduce the following decompositions

$$& 2 \text{diag} ( \tau ) \mathbf y = \mathbf w + c _ { 1 } \mathbf y, \quad \mathbf w = 2 P _ { \mathbf y } ^ { \perp } \text{diag} ( \tau ) \mathbf y, \quad c _ { 1 } = 2 \mathbf y ^ { T } \text{diag} ( \tau ) \mathbf y \\ & \Delta = \mathbf u + \mathbf v, \quad H \mathbf u = 0, \quad \mathbf u ^ { T } \mathbf v = 0, \quad \| H \mathbf v \| \geq \sigma _ { - } ( H ) \| \mathbf v \|,$$

where σ -( H ) denotes the smallest positive singular value of H . Using the latter decomposition and H y = H∆ , we can express the norm of the Riemannian gradient as follows

$$( 6. 8 ) \quad \| \text{grad} f ( \mathbf y ) \| ^ { 2 } = \| H \Delta + \mathbf w \| ^ { 2 } - ( \Delta ^ { T } H \Delta ) ^ { 2 } = \| H \mathbf v + \mathbf w \| ^ { 2 } - ( \mathbf v ^ { T } H \mathbf v ) ^ { 2 }$$

Let λ + ( H ) be the largest eigenvalue of H . Then, by definition of v , we obtain

$$( 6. 9 ) \quad | \mathbf v ^ { T } H \mathbf v | \leq \lambda _ { + } ( H ) \| \mathbf v \| ^ { 2 } \leq \lambda _ { + } ( H ) \sigma _ { - } ( H ) ^ { - 2 } \| H \mathbf v \| ^ { 2 } = \colon \bar { \sigma } ^ { - 1 } \cdot \mathbf v ^ { T } H ^ { 2 } \mathbf v.$$

Moreover, Lemma 6.1 yields

$$\| \tau \| ^ { \frac { 3 } { 2 } } \leq \eta _ { 1 } \| \mathbf w \|$$

for some constant η 1 &gt; 0 and for all y ∈ S n -1 sufficiently close to z . Let /epsilon1 &gt; 0 be an arbitrary small positive constant. We now discuss three different cases.

Case 1. ‖ w ‖ ≥ (1 + /epsilon1 ) ‖ H v ‖ or ‖ w ‖ ≤ (1 -/epsilon1 ) ‖ H v ‖ . In this case, we have

$$\| H \mathbf v + \mathbf w \| ^ { 2 } \geq \frac { \epsilon ^ { 2 } } { 2 } \left ( \| \mathbf w \| ^ { 2 } + \| H \mathbf v \| ^ { 2 } \right ). \\ \intertext { 0 sufficient} v \, \text{small such that } \| \mathbf v \| ^ { 2 } < \epsilon ^ { 2 } \bar { \sigma } / ( 4 \lambda _ { \perp } ( H ) )$$

Let us set δ z &gt; 0 sufficiently small such that ‖ v ‖ 2 ≤ /epsilon1 2 ¯ σ/ (4 λ + ( H )) and | v T H v | ≤ 1 . Using (6.9), (6.10), and the estimates ( v T H v ) 2 ≤ λ 2 + ( H ) ‖ v ‖ 4 and [ 1 2 | a + ] b | 3 / 2 ≤ [ | a | 3 / 2 + | b | 3 / 2 ] / √ 2 , a, b ∈ R , it follows

$$\mu \mu \rightarrow \cdots \int _ { 0 } \cdots \int _ { 0 } \cdots \int _ { 0 } \cdots \int _ { 0 } \cdots \int _ { 0 } \cdots \int _ { 0 } \cdots \int _ { 0 } \cdots \int _ { 0 } \cdots \int _ { 0 } \cdots \int _ { 0 } \cdots \int _ { 0 } \cdots \int _ { 0 } \cdots \int _ { 0 } \cdots \int _ { 0 } \cdots \int _ { 0 } \cdots \int _ { 0 } \cdots \int _ { 0 } \cdots \int _ { 0 } \cdots \int _ { 0 } \cdots \int _ { 0 } \cdots \int _ { 0 } \cdots \int _ { 0 } \cdots \int _ { 0 } \vdots \\ \left \| \text{grad} f ( y ) \right \| ^ { 2 } & \geq \frac { \epsilon ^ { 2 } } { 2 } ( \left \| \mathbf w \right \| ^ { 2 } + \left \| H \mathbf v \right \| ^ { 2 } ) - \lambda _ { + } ^ { 2 } ( H ) \right \| \mathbf v \right \| ^ { 4 } \geq \frac { \epsilon ^ { 2 } } { 4 } \left ( 2 \left \| \mathbf w \right \| ^ { 2 } + \left \| H \mathbf v \right \| ^ { 2 } \right ) \\ & \geq \frac { \epsilon ^ { 2 } } { 2 } \min \left \{ \frac { 1 } { \eta _ { 1 } }, \frac { \bar { \sigma } } { 2 } \right \} \left [ \left \| \tau \right \| ^ { 3 } + \left | \mathbf v ^ { T } H \mathbf v \right | ^ { \frac { 3 } { 2 } } \right ] \\ & \geq \frac { \epsilon ^ { 2 } \sqrt { 2 } } { 2 } \min \left \{ \frac { 1 } { \eta _ { 1 } }, \frac { \bar { \sigma } } { 2 } \right \} \cdot \left | f ( y ) - f ( z ) \right | ^ { \frac { 3 } { 2 } }. \\ \text{ Thus, we can infer that the KL exponent of problem (1.1) at $z$ is $1$}.$$

Thus, we can infer that the KL exponent of problem (1.1) at z is 1 4 .

Case 2. (2 -/epsilon1 ) r 2 + ‖ ∆ I ‖ ≥ ‖ ∆ ‖ 2 or γ 1 ≤ (2 -/epsilon1 ) r 2 + ‖ ∆ I ‖ ‖ 2 ∆ ‖ -2 . First, due to ∆ T y = 1 2 ‖ ∆ ‖ 2 , we have P ⊥ y ∆ = ∆ -1 2 ‖ ∆ ‖ 2 2 y . Defining t ∆ := ∆ P T ⊥ y ∆ = ‖ ∆ ‖ 2 -1 4 ‖ ∆ ‖ 4 , we will work with the following decompositions

$$H \Delta = \Delta ^ { T } H \Delta \cdot \mathbf y + c _ { 2 } P _ { \mathbf y } ^ { \perp } \Delta + \mathbf w _ { 1 }, \ \ c _ { 2 } = \frac { 1 - \frac { 1 } { 2 } \| \Delta \| ^ { 2 } } { t _ { \Lambda } } \Delta ^ { T } H \Delta,$$

$$\mathbf w = c _ { 3 } P _ { y } ^ { \perp } \Delta + \mathbf w _ { 2 }, \ \ c _ { 3 } = \frac { 1 } { t _ { \Delta } } [ 2 \Delta ^ { T } \text{diag} ( \tau ) \mathbf y - \| \Delta \| ^ { 2 } \mathbf y ^ { T } \text{diag} ( \tau ) \mathbf y ]$$

$$& \cdot \Delta ^ { T } H \Delta \cdot \mathbf y + c _ { 2 } P _ { \mathbf y } ^ { \perp } \Delta + \mathbf w _ { 1 }, \quad c _ { 2 } = \frac { 1 - \frac { 1 } { 2 } \| \Delta \| ^ { 2 } } { t _ { \Delta } } \Delta ^ { T } H \Delta, \\ & _ { 3 } P _ { \mathbf y } ^ { \perp } \Delta + \mathbf w _ { 2 }, \quad c _ { 3 } = \frac { 1 } { t _ { \Delta } } [ 2 \Delta ^ { T } \text{diag} ( \tau ) \mathbf y - \| \Delta \| ^ { 2 } \mathbf y ^ { T } \text{diag} ( \tau ) \mathbf y ] \\ & \cdot \quad \cdot \quad \cdot \dots \dots \dots \dots \dots$$

where w 1 and w 2 are vectors orthogonal to y and ∆ . Hence, by (6.8), it holds that

$$\| \text{grad} f ( \mathbf y ) \| ^ { 2 } = ( c _ { 2 } + c _ { 3 } ) ^ { 2 } \cdot t _ { \Delta } + \| \mathbf w _ { 1 } + \mathbf w _ { 2 } \| ^ { 2 } \geq ( c _ { 2 } + c _ { 3 } ) ^ { 2 } \cdot t _ { \Delta }.$$

Using the definitions introduced in the first case, we can express t ∆ · c 3 via

$$t _ { \Delta } \cdot c _ { 3 } = ( 2 - \| \Delta \| ^ { 2 } ) \gamma _ { 4 } + ( 6 - 4 \| \Delta \| ^ { 2 } ) \gamma _ { 3 } + ( 4 - 5 \| \Delta \| ^ { 2 } ) \gamma _ { 2 } - 2 \| \Delta \| ^ { 2 } \gamma _ { 1 }. \\ \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \end{array}$$

Now, if (2 -/epsilon1 ) r 2 + ‖ ∆ I ‖ ≥ ‖ ∆ ‖ 2 , we readily obtain (4 - ‖ 5 ∆ ‖ 2 ) γ 2 - ‖ 2 ∆ ‖ 2 γ 1 ≥ (2 /epsilon1 - ‖ 5 ∆ ‖ 2 ) r 2 + ‖ ∆ I ‖ 2 and thus, it follows

$$( 6. 1 1 ) \quad t _ { \Delta } \cdot c _ { 3 } \geq \gamma _ { 4 } + \epsilon r _ { + } ^ { 2 } \| \Delta _ { \mathcal { Z } } \| ^ { 2 } + o ( \| \Delta _ { \mathcal { Z } } \| ^ { 2 } ) \geq \| \Delta \| _ { 4 } ^ { 4 } + \frac { \epsilon r _ { + } ^ { 2 } } { 2 } \| \Delta _ { \mathcal { Z } } \| ^ { 2 }$$

for ∆ sufficiently small. Otherwise, if γ 1 ≤ (2 -/epsilon1 ) r 2 + ‖ ∆ I ‖ ‖ 2 ∆ ‖ -2 , then we also have (4 - ‖ 5 ∆ ‖ 2 ) γ 2 - ‖ 2 ∆ ‖ 2 γ 1 ≥ (2 /epsilon1 - ‖ 5 ∆ ‖ 2 ) r 2 + ‖ ∆ I ‖ 2 and thus, (6.11) holds in both sub-cases. Consequently, due to the positive semidefiniteness of H and ‖ ∆ ‖ 2 = -2 ∆ T z = -2 ∆ z T I I ≤ 2 ‖ ∆ I ‖ , we can infer

$$- 2 \Delta ^ { \prime } \, \mathbf z = - 2 \Delta _ { \mathcal { I } } ^ { 4 } \, z _ { \mathcal { I } } \leq 2 \| \Delta _ { \mathcal { I } } \|, \, \text{we can infer} \\ \| \text{grad} \, f ( \mathbf y ) \| & \geq | c _ { 2 } + c _ { 3 } | \sqrt { t _ { \Delta } } = \left [ \left ( 1 - \frac { 1 } { 2 } \| \Delta \| ^ { 2 } \right ) \Delta ^ { T } H \Delta + t _ { \Delta } c _ { 3 } \right ] t _ { \Delta } ^ { - 1 / 2 } \\ & \geq [ \Delta ^ { T } H \Delta + 2 \| \Delta \| _ { 4 } ^ { 4 } + \epsilon r _ { + } ^ { 2 } \| \Delta _ { \mathcal { I } } \| ^ { 2 } ] \cdot ( 2 \| \Delta \| ) ^ { - 1 } \\ & \geq [ \Delta ^ { T } H \Delta + 2 \| \Delta \| _ { 4 } ^ { 4 } + \epsilon r _ { + } ^ { 2 } \| \Delta _ { \mathcal { I } } \| ^ { 2 } ] ^ { \frac { 3 } { 4 } } \cdot \frac { \epsilon ^ { \frac { 1 } { 4 } } \sqrt { r _ { + } \| \Delta _ { \mathcal { I } } \| } } { 2 \| \Delta \| } \\ & \geq \eta _ { 2 } [ \Delta ^ { T } H \Delta + 2 \| \Delta \| _ { 4 } ^ { 4 } + \epsilon r _ { + } ^ { 2 } \| \Delta _ { \mathcal { I } } \| ^ { 2 } ] ^ { \frac { 3 } { 4 } }, \\ \text{where} \, \eta _ { 2 } \, \coloneqq \, \epsilon ^ { \frac { 1 } { 4 } } \sqrt { r _ { + } } / 2 \sqrt { 2 }. \, \text{Next, utilizing} \, ( 6. 4 ) \, \text{and} \, | \tau _ { k } | \leq 2 | \Delta _ { k } | \text{ for all} \, k \in \mathcal { I }, \, \text{we}$$

where η 2 := /epsilon1 1 4 √ r + / 2 √ 2 . Next, utilizing (6.4) and | τ k | ≤ 2 | ∆ k | for all k ∈ I , we finally obtain

$$\xi \cdots \\ | f ( \boldsymbol y ) - f ( \boldsymbol z ) | & = \frac { 1 } { 2 } [ \Delta ^ { T } H \Delta + \| \tau \| ^ { 2 } ] \\ & \leq \frac { 1 } { 2 } \left [ \Delta ^ { T } H \Delta + \| \Delta _ { \mathcal { A } } \| _ { 4 } ^ { 4 } + 4 \| \Delta _ { \mathcal { Z } } \| ^ { 2 } \right ] \leq \eta _ { 3 } \| \text{grad} \, f ( \boldsymbol y ) \| ^ { 4 } \\ \text{for some constant} \, \eta _ { 3 } & > 0 \text{ and for all} \, \boldsymbol y \text{ sufficiently close to} \, \boldsymbol z. \text{ Hence, the KL exponent}$$

Case 3. (1 -/epsilon1 ) ‖ H v ‖ ≤ ‖ w ‖ ≤ (1+ ) /epsilon1 ‖ H v ‖ , γ 1 ≥ (2 -/epsilon1 ) r 2 + ‖ ∆ I ‖ ‖ 2 ∆ ‖ -2 and ( 2 -/epsilon1 2 ) r 2 + ‖ ∆ I ‖ ≤ ‖ ∆ ‖ 2 ≤ 2 ‖ ∆ I ‖ . In this case, we have for some constant η 3 &gt; 0 and for all y sufficiently close to z . Hence, the KL exponent is 1 4 in this case.

$$( 6. 1 2 ) \ \gamma _ { 1 } = \Theta ( \| \Delta \| ^ { 2 } ), \ \gamma _ { 2 } = \Theta ( \| \Delta \| ^ { 4 } ), \ \gamma _ { 3 } = O ( \| \Delta \| ^ { 6 } ), \ \gamma _ { 4 } = \Theta ( \| \Delta \| ^ { 4 } ).$$

Let us set m := |I| and define σ k = ∆ z k k + 1 2 m ‖ ∆ ‖ 2 for all k ∈ I and σ k = 0 for all k ∈ A . Then, it follows

$$\sum _ { k \in [ n ] } \sigma _ { k } = 0, \quad \| \sigma \| _ { 1 } \geq \sum _ { k \in \mathcal { I } } z _ { k } ^ { 2 } \sigma _ { k } = \gamma _ { 1 } + \frac { 1 } { 2 } \| \Delta \| ^ { 2 },$$

and ‖ σ ‖ = Θ ( ‖ ∆ ‖ 2 ) . We now express ‖ w ‖ 2 in terms of γ 1 , γ 2 , γ 3 , and γ 4 . Specifically, by utilizing (6.12), we obtain

$$& \text{all} y, by utilizing ( 6. 1 2 ), \, \text{we obtain} \\ & \frac { 1 } { 4 } \| w \| ^ { 2 } = \text{y} ^ { T } \, \text{diag} ( | \tau | ^ { 2 } ) \text{y} - ( \text{y} \, \text{diag} ( \tau ) \text{y} ) ^ { 2 } \\ & \quad = \, \sum _ { k \in [ n ] } \Delta _ { k } ^ { 2 } [ \Delta _ { k } ^ { 4 } + 6 \Delta _ { k } ^ { 3 } z _ { k } + 1 3 \Delta _ { k } ^ { 2 } z _ { k } ^ { 2 } + 1 2 \Delta _ { k } z _ { k } ^ { 3 } + 4 z _ { k } ^ { 4 } ] - 4 \gamma _ { 1 } ^ { 2 } - 2 0 \gam$$

which implies ‖ w ‖ = Θ ( ‖ ∆ ‖ 2 ) and ‖ H v ‖ = Θ ( ‖ ∆ ‖ 2 ) . As a consequence, we get v T H v = Θ ( ‖ ∆ ‖ 4 ) and

$$( 6. 1 3 ) \quad \ 2 | f ( \mathbf y ) - f ( \mathbf z ) | = | \mathbf v ^ { T } H \mathbf v + \| \Delta \| _ { 4 } ^ { 4 } + 4 \gamma _ { 3 } + 4 \gamma _ { 2 } | = \Theta ( \| \Delta \| ^ { 4 } ).$$

For some index sets K J ⊂ , [ n ] , let H KJ ∈ R |K|×|J| denote the submatrix H KJ = ( H kj ) k ∈K ,j ∈J . Due to the positive semidefiniteness of H , we have H II /followsequal 0 and H AA /followsequal 0 . Furthermore, due to (6.8) and (6.12), we obtain

$$\| \text{grad} f ( \mathbf y ) \| ^ { 2 } & = \| H \Delta + \mathbf w \| ^ { 2 } - \Theta ( \| \Delta \| ^ { 8 } ) \\ & = \| H _ { \mathcal { I } \mathcal { A } } ^ { T } \Delta _ { \mathcal { I } } + H _ { \mathcal { A } \mathcal { A } } \Delta _ { \mathcal { A } } + 2 \, \text{diag} ( | \Delta _ { \mathcal { A } } | ^ { 2 } ) \Delta _ { \mathcal { A } } - c _ { 1 } \Delta _ { \mathcal { A } } \| ^ { 2 } \\ ( 6. 1 4 ) & \quad + \| H _ { \mathcal { I } \mathcal { I } } \Delta _ { \mathcal { I } } + H _ { \mathcal { I } \mathcal$$

We define

$$& \mathfrak { g } _ { 1 } \coloneqq H _ { \mathcal { I } \mathcal { I } } \Delta _ { \mathcal { I } } + H _ { \mathcal { I }, \mathcal { A } } \Delta _ { \mathcal { A } } + w _ { \mathcal { I } }, \\ ( 6. 1 5 ) & \mathfrak { g } _ { 2 } \coloneqq H _ { \mathcal { I }, \mathcal { A } } ^ { T } \Delta _ { \mathcal { I } } + H _ { \mathcal { A } \mathcal { A } } \Delta _ { \mathcal { A } } + 2 \, \text{diag} ( | \Delta _ { \mathcal { A } } | ^ { 2 } ) \Delta _ { \mathcal { A } } - c _ { 1 } \Delta _ { \mathcal { A } } \\ & \quad \quad \quad$$

Next, let η , η 4 5 &gt; 0 and µ ∈ (0 , 1 2 ) be given constants and suppose ∆ T I ( H II ∆ I + H IA ∆ A ) ≥ -η 4 ‖ ∆ ‖ 4+ µ . Then, using 1 2 c 1 = ‖ ∆ ‖ 4 4 +4 γ 3 +5 γ 2 +2 γ 1 , ∆ y T I I = - ‖ 1 2 ∆ ‖ 2 , and ∆ w T I I = 2 ‖ ∆ ‖ 4 4 +6 γ 3 +4 γ 2 -c 1 ∆ y T I I , it follows

$$\Delta _ { \mathcal { I } } ^ { T } \mathbf g _ { 1 } = \Delta _ { \mathcal { I } } ^ { T } ( H _ { \mathcal { I } \mathcal { I } } \Delta _ { \mathcal { I } } + H _ { \mathcal { I }, \mathcal { A } } \Delta _ { \mathcal { A } } ) + \Delta _ { \mathcal { I } } ^ { T } w _ { \mathcal { I } } \geq \Theta ( \| \Delta \| ^ { 4 } ).$$

Similarly, in the case ∆ T I ( H II ∆ I + H IA ∆ A ) ≤ -η 5 ‖ ∆ ‖ 4 -µ and if ‖ ∆ ‖ is sufficiently small, we get

$$\Delta _ { \mathcal { I } } ^ { T } \mathbf g _ { 1 } \leq - \frac { \eta _ { 5 } } { 2 } \| \Delta \| ^ { 4 - \mu },$$

Combining both cases, we can infer ‖ ∆ I ‖‖ g 1 ‖ ≥ | ∆ T I g 1 | ≥ η 6 ‖ ∆ ‖ 4 for some η 6 &gt; 0 and for all y sufficiently close to z . This implies ‖ g 1 ‖ ≥ [(2 -/epsilon1 2 ) r 2 + ] -1 η 6 ‖ ∆ ‖ 2 and hence, by (6.14), we obtain ‖ grad f ( y ) ‖ ≥ Θ ( ‖ ∆ ‖ 2 ) . Considering equation (6.13), the KL exponent has to be θ = 1 2 in these two cases.

∆ H T A AA ∆ A ≥ ∆ T A ( H T IA ∆ I + H AA ∆ A ) ≥ ∆ H∆ T = Θ ( ‖ ∆ ‖ 4 ) .

Now, let us suppose -η 5 ‖ ∆ ‖ 4 -µ ≤ ∆ T I ( H II ∆ I + H IA ∆ A ) ≤ -η 4 ‖ ∆ ‖ 4+ µ . Due to ∆ H T I II ∆ I ≥ 0 , this directly yields -η 5 ‖ ∆ ‖ 4 -µ ≤ ∆ H T I IA ∆ A &lt; 0 and

If we have ∆ H T A AA ∆ A ≥ η 7 ‖ ∆ ‖ 4 -2 µ for some constant η 7 &gt; 0 , then it holds that

$$\stackrel { \lambda } { \Delta _ { \mathcal { A } } ^ { T } \mathfrak { g } _ { 2 } } } & = \Delta _ { \mathcal { A } } ^ { T } ( H _ { \mathcal { I } \mathcal { A } } ^ { T } \Delta _ { \mathcal { I } } + H _ { \mathcal { A } \mathcal { A } } \Delta _ { \mathcal { A } } ) + 2 \| \Delta _ { \mathcal { A } } \| _ { 4 } ^ { 4 } - c _ { 1 } \| \Delta _ { \mathcal { A } } \| ^ { 2 } \\ & \geq \eta _ { 7 } \| \Delta \| ^ { 4 - 2 \mu } - \eta _ { 5 } \| \Delta \| ^ { 4 - \mu } + O ( \| \Delta \| ^ { 4 } ) \geq \frac { \eta _ { 7 } } { 2 } \| \Delta \| ^ { 4 - 2 \mu } \\ \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \,.$$

if ‖ ∆ ‖ is sufficiently close to zero. As before, this estimate can be utilized to show ‖ grad f ( y ) ‖ ≥ Θ ( ‖ ∆ ‖ 3 -2 µ ) and consequently, the KL exponent is 1+2 µ 4 .

$$\Delta _ { \mathcal { A } } = \psi _ { 1 } + \xi _ { 1 }, \quad \psi _ { 1 } \in \text{null} \ H _ { \mathcal { A } \mathcal { A } }, \quad \xi _ { 1 } \in [ \text{null} \ H _ { \mathcal { A } \mathcal { A } } ] ^ { \perp }, \\ \dots _ { \mathcal { A } } \left ( \Delta _ { \mathcal { A } } \right ) \Delta _ { \mathcal { A } } \right ) \dots _ { \mathcal { A } } \dots _ { \mathcal { B } } \pi \pi \right )$$

Finally, we consider η 8 ‖ ∆ ‖ 4 ≤ ∆ H T A AA ∆ A ≤ η 7 ‖ ∆ ‖ 4 -2 µ , where η 8 &gt; 0 is chosen such that ∆ H∆ T ≥ η 8 ‖ ∆ ‖ 4 . Let us define the decompositions

$$\text{diag} ( | \Delta _ { \mathcal { A } } | ^ { 2 } ) \Delta _ { \mathcal { A } } = \psi _ { 2 } + \xi _ { 2 }, \quad \psi _ { 2 } \in \text{null} \ H _ { \mathcal { A } \mathcal { A } }, \quad \xi _ { 2 } \in [ \text{null} \ H _ { \mathcal { A } \mathcal { A } } ] ^ { \perp }, \\ \dots \dots \dots \pi \, \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \pi \, \dots \dots \pi \, \pi \, \pi \, \dots \dots \pi \, \pi \, \pi \, \dots \dots \pi \, \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots\dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots \dots \pi \, \pi \, \dots.$$

Since H is positive semidefinite, we can show that null H AA ⊂ null H IA . If H IA = 0 , then this claim is certainly true. Otherwise, if we assume that the statement is false, the set S = null H AA ∩ [null H IA ] ⊥ is nonempty and there exists ψ ∈ S and ξ ∈ [null H T IA ] ⊥ . Then it holds where null M is the null space of matrix M . We then have ‖ ξ 1 ‖ = Θ ( ‖ H AA ξ 1 ‖ ) = Θ ( √ ξ T 1 H AA ξ 1 ) = O ( ‖ ∆ ‖ 2 -µ ) and ‖ ψ 1 ‖ = O ( ‖ ∆ ‖ ) . Notice that such decompositions exist due to the symmetry of H AA .

$$\begin{bmatrix} \xi \\ \nu \psi \end{bmatrix} \begin{bmatrix} H _ { \mathcal { I } \mathcal { I } } & H _ { \mathcal { I } \mathcal { A } } \\ H _ { \mathcal { I } \mathcal { A } } ^ { T } & H _ { \mathcal { I } \mathcal { A } } \\ H _ { \mathcal { I } \mathcal { A } } ^ { T } & H _ { \mathcal { I } \mathcal { A } } \end{bmatrix} \begin{bmatrix} \xi & \nu \psi \end{bmatrix} = \xi ^ { T } H _ { \mathcal { I } \mathcal { I } \xi } \xi + 2 \nu \psi ^ { T } H _ { \mathcal { I } \mathcal { A } } ^ { T } \xi \geq 0, \quad \forall \, \nu \in \mathbb { R }. \\ \text{But since } \psi ^ { T } H _ { \mathcal { I } \mathcal { A } } ^ { T } \xi \neq 0, \, \text{we can choose } \nu \text{ such that } \xi ^ { T } H _ { \mathcal { I } \mathcal { I } } \xi + 2 \nu \psi ^ { T } H _ { \mathcal { I } \mathcal { A } } ^ { T } \xi < 0,$$

/negationslash

$$2 \| \Delta _ { \mathcal { A } } \| _ { 4 } ^ { 4 } - c _ { 1 } \| \Delta _ { \mathcal { A } } \| ^ { 2 } & = \stackrel { \cdot } { 2 \psi _ { 1 } ^ { T } \psi _ { 2 } } - c _ { 1 } \| \psi _ { 1 } \| ^ { 2 } + 2 \xi _ { 1 } ^ { T } \xi _ { 2 } - c _ { 1 } \| \xi _ { 1 } \| ^ { 2 } \\ & = \psi _ { 1 } ^ { T } \mathfrak { d } + 2 \xi _ { 1 } ^ { T } \xi _ { 2 } - c _ { 1 } \| \xi _ { 1 } \| ^ { 2 } \geq - \frac { \eta \S _ { 1 } } { 2 } \| \Delta \| ^ { 4 } + O ( \| \Delta \| ^ { 5 - \mu } )$$

But since ψ T H T IA ξ = 0 , we can choose ν such that ξ T H II ξ + 2 νψ T H T IA ξ &lt; 0 , which is a contradiction. Hence, due to H T IA ∆ I ∈ ran H T IA = [null H IA ] ⊥ , we can infer H T IA ∆ I + H AA ∆ A ∈ [null H AA ⊥ ] . Consequently, g 2 can be written as g 2 = g 3 + d where g 3 ∈ [null H AA ⊥ ] and d = 2 ψ 2 -c 1 ψ 1 ∈ null H AA . If ‖ d ‖ ≥ η 8 2 ‖ ∆ ‖ 3 , then we obtain ‖ grad f ( y ) ‖ ≥ ‖ g 2 ‖ ≥ ‖ d ‖ ≥ η 8 2 ‖ ∆ ‖ 3 and, by (6.13), the KL exponent is 1 4 . Otherwise, if ‖ d ‖ ≤ η 8 2 ‖ ∆ ‖ 3 , it follows and

$$\Delta _ { \mathcal { A } } ^ { T } g _ { 2 } & = \Delta _ { \mathcal { A } } ^ { T } ( H _ { \mathcal { I } \mathcal { A } } ^ { T } \Delta _ { \mathcal { I } } + H _ { \mathcal { A } \mathcal { A } } \Delta _ { \mathcal { A } } ) + 2 \| \Delta _ { \mathcal { A } } \| _ { 4 } ^ { 4 } - c _ { 1 } \| \Delta _ { \mathcal { A } } \| ^ { 2 } \\ & \geq \Delta ^ { T } H \Delta - \frac { \eta _ { 8 } } { 2 } \| \Delta \| ^ { 4 } + O ( \| \Delta \| ^ { 5 - \mu } ) \\ & \geq \frac { \eta _ { 8 } } { 2 } \| \Delta \| ^ { 4 } + \Theta ( \| \Delta \| ^ { 5 - \mu } ) \geq \frac { \eta _ { 8 } } { 4 } \| \Delta \| ^ { 4 }.$$

Thus, we have ‖ grad f ( y ) ‖ ≥ Θ ( ‖ ∆ ‖ 3 ) and the KL exponent is 1 4 .

## 7 Conclusions

In this paper, we analyze the geometric properties of a class of quartic-quadratic optimization problems under a single spherical constraint. When the matrix A in the quadratic form is diagonal, the stationary points and local minima can be fully characterized and we show that the minimization problem does not possess any spurious local minima. Furthermore, a closed-form expression for global minimizer is available which is based on the projection onto the n -simplex. If A is a rank-one matrix, a similar analysis can be performed and we derive characteristic properties of associated local minima and uniqueness of global minima up to a certain phase shift. We verify that the problem satisfies a Riemannian-type strict-saddle property in the real space when the interaction coefficient is at least of order O n ( 3 / 2 ) or sufficiently small which corresponds to the case where either the quartic or the quadratic part is the leading term of the objective function. Finally, we estimate the Kurdyka-Łojasiewicz exponent θ of problem (1.1) and show that θ is 1 4 for all stationary points z if A is diagonal or if the problem is restricted to the real space and z fulfills a certain global optimality condition.

## References

- 1. Absil, P.A., Mahony, R., Andrews, B.: Convergence of the iterates of descent methods for analytic cost functions. SIAM J. Optim. 16 (2), 531-547 (2005)
- 2. Absil, P.A., Mahony, R., Sepulchre, R.: Optimization algorithms on matrix manifolds. Princeton University Press (2009)
- 3. Adhikari, S.K.: Numerical solution of the two-dimensional Gross-Pitaevskii equation for trapped interacting atoms. Physics Letters A 265 (1-2), 91-96 (2000)
- 4. Anandkumar, A., Ge, R.: Efficient approaches for escaping higher order saddle points in non-convex optimization. In: 29th Annual Conf. on Learn. Theory, Proceedings of Mach. Learn. Res. , vol. 49, pp. 81-102 (2016)
- 5. Arora, S., Ge, R., Ma, T., Moitra, A.: Simple, efficient, and neural algorithms for sparse coding. J. Mach. Learn. Res. (2015)
- 6. Attouch, H., Bolte, J.: On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Math. Program. 116 (1-2), 5-16 (2009)
- 7. Attouch, H., Bolte, J., Redont, P., Soubeyran, A.: Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kurdyka-Łojasiewicz inequality. Math. Oper. Res. 35 (2), 438-457 (2010)
- 8. Attouch, H., Bolte, J., Svaiter, B.F.: Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods. Math. Program. 137 (1-2, Ser. A), 91-129 (2013)
- 9. Bandeira, A.S., Boumal, N., Singer, A.: Tightness of the maximum likelihood semidefinite relaxation for angular synchronization. Math. Program. 163 (1-2), 145-167 (2017)
- 10. Bandeira, A.S., Boumal, N., Voroninski, V.: On the low-rank approach for semidefinite programs arising in synchronization and community detection. In: Conf. Learn. Theory, pp. 361-382 (2016)
- 11. Bao, W., Cai, Y.: Mathematical theory and numerical methods for Bose-Einstein condensation. Kinetic and Related Models 6 (1), 1-135 (2012)
- 12. Bolte, J., Daniilidis, A., Lewis, A.: The Łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAM J. Optim. 17 (4), 1205-1223 (2006)
- 13. Bolte, J., Daniilidis, A., Lewis, A.: A nonsmooth Morse-Sard theorem for subanalytic functions. J. Math. Anal. Appl. 321 (2), 729-740 (2006)

- 14. Bolte, J., Daniilidis, A., Lewis, A., Shiota, M.: Clarke subgradients of stratifiable functions. SIAM J. Optim. 18 (2), 556-572 (2007)
- 15. Bolte, J., Sabach, S., Teboulle, M.: Proximal alternating linearized minimization or nonconvex and nonsmooth problems. Math. Program. 146 (1-2), 459-494 (2014)
- 16. Bonettini, S., Loris, I., Porta, F., Prato, M., Rebegoldi, S.: On the convergence of a linesearch based proximal-gradient method for nonconvex optimization. Inverse Problems 33 (5) (2017)
- 17. Boumal, N.: Nonconvex phase synchronization. SIAM J. Optim. 26 (4), 2355-2377 (2016)
- 18. Cai, Y., Zhang, L., Bai, Z., Li, R.C.: On an eigenvector-dependent nonlinear eigenvalue problem. SIAM J. Matrix Anal. Appl. 39 (3), 1360-1382 (2018)
- 19. Cand` es, E.J., Li, X.: Solving quadratic equations via phaselift when there are about as many equations as unknowns. Found. Comput. Math. 14 (5), 1017-1026 (2014)
- 20. Cand` es, E.J., Li, X., Soltanolkotabi, M.: Phase retrieval via wirtinger flow: Theory and algorithms. IEEE Trans. Inf. Theory 61 (4), 1985-2007 (2015)
- 21. Cand` es, E.J., Strohmer, T., V oroninski, V .: Phaselift: Exact and stable signal recovery from magnitude measurements via convex programming. Comm. Pure and Appl. Math. 66 (8), 1241-1274 (2013)
- 22. Cand` es, E.J., Tao, T.: The power of convex relaxation: Near-optimal matrix completion. IEEE Trans. Inf. Theory 56 (5), 2053-2080 (2010)
- 23. Cartis, C., Gould, N.I.M., Toint, P.L.: Second-order optimality and beyond: characterization and evaluation complexity in convexly constrained nonlinear optimization. Found. Comput. Math. 18 (5), 1073-1107 (2018)
- 24. Chen, Y., Chi, Y ., Fan, J., Ma, C.: Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval. Math. Program. 176 (1-2, Ser. B), 5-37 (2019)
- 25. Chen, Y., Chi, Y., Goldsmith, A.J.: Exact and stable covariance estimation from quadratic sampling via convex programming. IEEE Trans. Inf. Theory 61 (7), 4034-4059 (2015)
- 26. Chi, Y., Lu, Y.M., Chen, Y.: Nonconvex optimization meets low-rank matrix factorization: An overview (2018). Preprint, https://arxiv.org/abs/1809.09573
- 27. D'Acunto, D., Kurdyka, K.: Explicit bounds for the Łojasiewicz exponent in the gradient inequality for polynomials. In: Ann. Polonici Mathematici, 87, pp. 51-61 (2005)
- 28. Dedieu, J.P.: Third- and fourth-order optimality conditions in optimization. Optimization 33 (2), 97104 (1995)
- 29. Edwards, M., Burnett, K.: Numerical solution of the nonlinear Schr¨dinger equation for small samples o of trapped neutral atoms. Physical Review A 51 (2), 1382 (1995)
- 30. Forti, M., Nistri, P., Quincampoix, M.: Convergence of neural networks for programming problems via a nonsmooth Łojasiewicz inequality. IEEE Trans. Neural Networks 17 (6), 1471-1486 (2006)
- 31. Gao, B., Liu, X., Chen, X., Yuan, Y .: On the Łojasiewicz exponent of the quadratic sphere constrained optimization problem (2016). Preprint, https://arxiv.org/abs/1611.08781
- 32. Gao, B., Liu, X., Chen, X., Yuan, Y .: A new first-order algorithmic framework for optimization problems with orthogonality constraints. SIAM J. Optim. 28 (1), 302-332 (2018)
- 33. Garc´ ıa-Ripoll, J.J., P´rez-Garc´ ıa, V .M.: Optimizing Schr¨dinger functionals using sobolev gradients: e o Applications to quantum mechanics and nonlinear optics. SIAM J. Sci. Comput. 23 (4), 1316-1334 (2001)
- 34. Ge, R., Huang, F., Jin, C., Yuan, Y .: Escaping from saddle pointsonline stochastic gradient for tensor decomposition. In: Conf. Learn. Theory, pp. 797-842 (2015)
- 35. Ge, R., Jin, C., Zheng, Y.: No spurious local minima in nonconvex low rank problems: A unified geometric analysis. In: Proceed. of the 34th Int. Conf. Mach. Learn., vol. 70, pp. 1233-1242 (2017)

36.

Ge, R., Lee, J.D., Ma, T.: Matrix completion has no spurious local minimum.

In: Adv. Neural Inf.

Process. Syst., pp. 2973-2981 (2016)

- 37. Ge, R., Ma, T.: On the optimization landscape of tensor decompositions. In: Adv. Neural Inf. Process. Systems, pp. 3653-3663 (2017)
- 38. Griffin, A., Snoke, D.W., Stringari, S.: Bose-Einstein condensation. Cambridge University Press (1996)
- 39. Gwo´ zdziewicz, J.: The łojasiewicz exponent of an analytic function at an isolated zero. Comment. Math. Helv. 74 (3), 364-375 (1999)
- 40. Hu, J., Jiang, B., Liu, X., Wen, Z.: A note on semidefinite programming relaxations for polynomial optimization over a single sphere. Sci. China Math. 59 (8), 1543-1560 (2016)
- 41. Hu, J., Milzarek, A., Wen, Z., Yuan, Y.: Adaptive quadratically regularized Newton method for Riemannian optimization. SIAM J. Matrix Anal. Appl. 39 (3), 1181-1207 (2018)
- 42. Jaganathan, K., Eldar, Y .C., Hassibi, B.: Phase retrieval: an overview of recent developments (2015). Preprint, https://arxiv.org/abs/1510.07713

- 43. Jain, P., Kar, P.: Non-convex optimization for machine learning. Found. and Trends R © in Mach. Learn. 10 (3-4), 142-336 (2017)
- 44. Keshavan, R.H., Montanari, A., Oh, S.: Matrix completion from a few entries. IEEE Trans. Inf. Theory 56 (6), 2980-2998 (2010)
- 45. Keshavan, R.H., Montanari, A., Oh, S.: Matrix completion from noisy entries. J. Mach. Learn. Res. 11 (Jul), 2057-2078 (2010)
- 46. Kreutz-Delgado, K.: The complex gradient operator and the CR-calculus (2009). Preprint, https://arxiv.org/abs/0906.4835
- 47. Kurdyka, K.: On gradients of functions definable in o-minimal structures. Ann. Inst. Fourier (Grenoble) 48 (3), 769-783 (1998)
- 48. Lee, J.D., Panageas, I., Piliouras, G., Simchowitz, M., Jordan, M.I., Recht, B.: First-order methods almost always avoid strict saddle points. Math. Program. 176 (1-2, Ser. B), 311-337 (2019)
- 49. Lee, J.D., Simchowitz, M., Jordan, M.I., Recht, B.: Gradient descent converges to minimizers. In: Conf. Learn. Theory, pp. 1246-1257 (2016)
- 50. Li, G., Pong, T.K.: Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods. Found. Comput. Math. 18 (5), 1199-1232 (2018)
- 51. Li, X., Zhu, Z., So, A.M.C., Vidal, R.: Nonconvex robust low-rank matrix recovery (2018). Preprint, https://arxiv.org/abs/1809.09237
- 52. Liang, S., Sun, R., Li, Y ., Srikant, R.: Understanding the loss surface of neural networks for binary classification. In: Int. Conf. Mach. Learn. pp. 2835-2843 (2018)
- 53. Liu, H., So, A.M.C., Wu, W.: Quadratic optimization with orthogonality constraint: explicit Łojasiewicz exponent and linear convergence of retraction-based line-search and stochastic variancereduced gradient methods. Math. Program. pp. 1-48 (2017)
- 54. Liu, H., Yue, M.C., Man-Cho So, A.: On the estimation performance and convergence rate of the generalized power method for phase synchronization. SIAM J. Optim. 27 (4), 2426-2446 (2017)
- 55. Łojasiewicz, S.: Une propri´ et´ topologique des sous-ensembles analytiques r´ eels. e Les ´ equations aux d´ eriv´es partielles e 117 , 87-89 (1963)
- 56. Luo, Z.Q., Pang, J.S.: Error bounds for analytic systems and their applications. Math. Program. 67 (13), 1-28 (1994)
- 57. Luo, Z.Q., Sturm, J.F.: Error bounds for quadratic systems. In: High Perform. Optim., pp. 383-404. Springer (2000)
- 58. Marˇ cenko, V .A., Pastur, L.A.: Distribution of eigenvalues for some sets of random matrices. Math. of the USSR-Sbornik 1 (4), 457 (1967)
- 59. Merlet, B., Nguyen, T.N., et al.: Convergence to equilibrium for discretizations of gradient-like flows on riemannian manifolds. Diff. and Integral Equations 26 (5/6), 571-602 (2013)
- 60. More, J.J.: Generalizations of the trust region problem. Optim. Methods and Software 2 (3-4), 189209 (1993)
- 61. Murty, K.G., Kabadi, S.N.: Some NP-complete problems in quadratic and nonlinear programming. Math. Program. 39 (2), 117-129 (1987)
- 62. Nocedal, J., Wright, S.J.: Numerical Optimization, second edn. Springer, New York, NY, USA (2006)
- 63. Ochs, P., Chen, Y., Brox, T., Pock, T.: iPiano: inertial proximal algorithm for nonconvex optimization. SIAM J. Imaging Sci. 7 (2), 1388-1419 (2014)
- 64. Panageas, I., Piliouras, G.: Gradient descent only converges to minimizers: Non-isolated critical points and invariant regions (2016). Preprint, https://arxiv.org/abs/1605.00405
- 65. Penot, J.P.: Higher-order optimality conditions and higher-order tangent sets. SIAM J. Optim. 27 (4), 2508-2527 (2017)
- 66. Pethick, C.J., Smith, H.: Bose-Einstein condensation in dilute gases. Cambridge University Press (2002)
- 67. Press, W.H., Flannery, B.P., Teukolsky, S.A., Vetterling, W.T.: Numerical recipes. Cambridge University Press (1986). The art of scientific computing
- 68. Recht, B.: A simpler approach to matrix completion. J. Mach. Learn. Res. 12 (Dec), 3413-3430 (2011)
- 69. Schneider, R., Uschmajew, A.: Convergence results for projected line-search methods on varieties of low-rank matrices via Łojasiewicz inequality. SIAM J. Optim. 25 (1), 622-646 (2015)
- 70. Shechtman, Y., Eldar, Y.C., Cohen, O., Chapman, H.N., Miao, J., Segev, M.: Phase retrieval with application to optical imaging: a contemporary overview. IEEE Signal Process. Mag. 32 (3), 87-109 (2015)
- 71. Sorber, L., Barel, M.V., Lathauwer, L.D.: Unconstrained optimization of real functions in complex variables. SIAM J. Optim. 22 (3), 879-898 (2012)

- 72. Sun, J.: When Are Nonconvex Optimization Problems Not Scary? Columbia University (2016)
- 73. Sun, J., Qu, Q., Wright, J.: A geometric analysis of phase retrieval. In: IEEE Int. Symp. Inf. Theory (ISIT), 2016, pp. 2379-2383. IEEE (2016)
- 74. Sun, J., Qu, Q., Wright, J.: Complete dictionary recovery over the sphere i: Overview and the geometric picture. IEEE Trans. Inf. Theory 63 (2), 853-884 (2017)
- 75. Sun, J., Qu, Q., Wright, J.: Complete dictionary recovery over the sphere ii: Recovery by riemannian trust-region method. IEEE Trans. Inf. Theory 63 (2), 885-914 (2017)
- 76. Sun, J., Qu, Q., Wright, J.: A geometric analysis of phase retrieval. Found. Comput. Math. 18 (5), 1131-1198 (2018)
- 77. Sun, R., Luo, Z.Q.: Guaranteed matrix completion via non-convex factorization. IEEE Trans. Inf. Theory 62 (11), 6535-6579 (2016)
- 78. Thoai, N.V.: General quadratic programming. In: Essays and Surv. in Glob. Optim., GERAD 25th Anniv. Ser. , vol. 7, pp. 107-129. Springer, New York (2005)
- 79. Wen, Z., Yin, W.: A feasible method for optimization with orthogonality constraints. Math. Program. 142 (1-2, Ser. A), 397-434 (2013)
- 80. Wu, X., Wen, Z., Bao, W.: A regularized Newton method for computing ground states of BoseEinstein condensates. SIAM J. of Sci. Comput. 73 (1), 303-329 (2017)
- 81. Yang, W.H.: Error bounds for convex polynomials. SIAM J. Optim. 19 (4), 1633-1647 (2008)
Haixiang Zhang Andre Milzarek Zaiwen Wen Wotao Yin
On The Geometric Analysis of A Quartic-quadratic Optimization Problem under A Spherical Constraint
This paper considers the problem of solving a special quartic-quadratic
optimization problem with a single sphere constraint, namely, finding a global
and local minimizer of
$\frac{1}{2}\mathbf{z}^{*}A\mathbf{z}+\frac{\beta}{2}\sum_{k=1}^{n}\lvert
z_{k}\rvert^{4}$ such that $\lVert\mathbf{z}\rVert_{2}=1$. This problem spans
multiple domains including quantum mechanics and chemistry sciences and we
investigate the geometric properties of this optimization problem. Fourth-order
optimality conditions are derived for characterizing local and global minima.
When the matrix in the quadratic term is diagonal, the problem has no spurious
local minima and global solutions can be represented explicitly and calculated
in $O(n\log{n})$ operations. When $A$ is a rank one matrix, the global minima
of the problem are unique under certain phase shift schemes. The strict-saddle
property, which can imply polynomial time convergence of second-order-type
algorithms, is established when the coefficient $\beta$ of the quartic term is
either at least $O(n^{3/2})$ or not larger than $O(1)$. Finally, the
Kurdyka-Lojasiewicz exponent of quartic-quadratic problem is estimated and it
is shown that the exponent is ${1}/{4}$ for a broad class of stationary points.