# On a manifold formulation
of self-concordant functions

Hiroshi HIRAI
Department of Mathematical Informatics,
Graduate School of Information Science and Technology,
The University of Tokyo, Tokyo, 113-8656, Japan.
<EMAIL_ADDRESS>
###### Abstract

In this paper, we address an extension of the theory of self-concordant
functions for a manifold. We formulate the self-concordance of a geodesically
convex function by a condition of the covariant derivative of its Hessian, and
verify that many of the analogous properties, such as the quadratic
convergence of Newton’s method and the polynomial iteration complexity of the
path-following method, are naturally extended. However it is not known whether
a useful class of self-concordant functions/barriers really exists for non-
Euclidean manifolds. To this question, we provide a preliminary result that
the squared distance function in the hyperbolic space of curvature $-\kappa$
is $\sqrt{\kappa}/2$-self-concordant and the associated logarithmic barrier of
a ball of radius $R$ is an $O(\kappa R^{2})$-self-concordant barrier. We also
give an application to the minimum enclosing ball in a hyperbolic space.

Keywords: geodesically convex optimziation, interior point method, self-
concordant functions, information geometry

##  1 Introduction

The present paper addresses the power of geodesically convex optimization from
computational complexity perspectives. This is motivated by the recent
development on operator scaling and its generalization [2, 5, 8], where
several important problems in mathematical science are shown to be formulated
as geodesically convex optimization on Riemannian manifolds. By first- or
second-order methods on the manifolds, some of them are successfully solved in
polynomial time [2, 5]. On the other hand, due to the limitation of current
methods [7], many of them still remain to desire a theoretically good
algorithm. In the literature, the design of optimization methods on manifolds,
which utilizes geodesic convexity and has polynomial iteration complexity, is
an important issue. Particularly, several papers asks an interior-point
polynomial algorithm for geodesically convex optimization on manifolds; see
[5, p. 99] and see also [6, 7].

For Euclidean convex optimization, interior-point methods provide a powerful
framework to derive polynomial time complexity. The underlying mathematical
basis is established by the theory of self-concordant functions due to
Nesterov and Nemirovskii [18]. The aim of the present paper is to examine an
extension of self-concordant functions and the associated path-following
method for a manifold setting. Actually, such an attempt has already been
addressed by Udriste [28] and Jiang, Moore, and Ji [11]. They considered self-
concordant functions on general manifolds, and claimed several results
analogous to the ones for the Euclidean case. However, we found that the both
papers contain several vague points on treatments of tensor fields and
covariant differentiation $\nabla$. For example, the both papers assume that
trilinear form $(X,Y,Z)\mapsto\nabla_{X}\nabla_{Y}\nabla_{Z}f$ is symmetric.
This is not true, even if $\nabla$ is a “symmetric” connection ($\nabla$ is
torsion-free); see Lemma 2.3. Although their arguments may be justified by
appropriate modifications and corrections, we here examine a “faithful
adaptation” of arguments in Nesterov’s books [16, 17] for a manifold setting,
by means of the standard language of differential geometry.

The first contribution of this paper is to show that such an adaptation is
actually possible. A naive definition of the self-concordance (SC) for a
Riemannian manifold $M$ is by differentiation via geodesic $\gamma:[0,1]\to M$
as $|(f\circ\gamma)^{\prime\prime\prime}(t)|\leq
2\sigma(f\circ\gamma)^{\prime\prime}(t)$. We point out that, due to the
asymmetry of $\nabla_{X}\nabla_{Y}\nabla_{Z}f$, a lemma of symmetric trilinear
forms by Nesterov and Nemirovski [18, Proposition 9.1.1] is not applicable.
Consequently, this naive definition is not enough to deriving desirable
properties of SC. We here employ a stronger condition as a definition of SC,
which concerns the covariant derivative of the Hessian $Hf$ of $f$ and
equivalents the original if $M={\mathbb{R}}^{n}$. Then we verify several
required properties of SC analogous to the Euclidean case. Although many of
presented arguments may be straightforward adaptations of those in [16, 17],
they clarify differential geometric nature of SC properties, which are hidden
for the Euclidean case. Particularly, we incorporate viewpoints of information
geometry [3] to the quadratic convergence proof of Newton’s method. We believe
that these are insightful even in the original Euclidean setting.

The second contribution of this paper addresses the next question: For non-
Euclidean manifolds, do nontrivial, or even useful, classes of SC functions
really exist ? We show that the squared distance function
$x\mapsto\frac{1}{2}d(p,x)^{2}$ in the hyperbolic space of curvature
$-\kappa<0$ is $\sqrt{\kappa}/2$-self-concordant. Together with the
logarithmic barrier construction, any ball $B$ of radius $R$ admits an
$O(\kappa R)$-self concordant barrier. We exhibit that our results can be
applied to the minimum enclosing ball problem in a hyperbolic space [15]. This
suggests the existence of an SC-barrier for a more general convex set and its
further applications. On the other hand, since the order of the barrier
parameter is tight, the presented barrier of a ball may be unsatisfactory; the
iteration complexity of the path-following method involving this barrier
depends on radius $R$. This suggests a further difficulty of constructing a
good SC-barrier, which is not easy already in the Euclidean case.
Nevertheless, we hope that these results will be a springboard for discussion
and stimulate further research in this direction.

#### Related work.

Optimization on manifolds (Riemannian optimization) is one of active areas in
continuous optimization. In its modeling flexibility, various problems in
machine learning, statistics, and control theory can be formulated in
Riemannian optimization, and (practically) efficient algorithms have been
developed; see textbooks [1, 4, 25]. The design of theoretically efficient
optimization algorithms, with basis on geodesic convexity, is a challenging
new direction of research; see [4, Chapter 11] and references therein.

The ellipsoid method is another powerful algorithm to derive polynomial-time
complexity. Rusciano [23] introduced a cutting plane method, similar to the
ellipsoid method, for Hadamard manifolds. He showed the existence of a cutting
plane sequence such that the volume of the domain including an optimum
decreases in linear order. However, the sequence is non-constructive. Also, as
pointed out in [7], the volume of a ball in a hyperbolic space depends
exponentially on its diameter (see e.g., [24, p. 189]), and hence the
iteration complexity depends on the diameter of the domain. So this algorithm,
even if it could be implemented, has difficulty for problems on a large
domain.

Already in Euclidean case, interior-point methods are closely linked to
Riemannian geometry. Nesterov and Todd [19] regarded the interior of the
feasible region of LP as a Riemannian manifold with Hessian metric induced by
a self-concordant barrier. They connected the Riemannian length of the central
curve with the complexity of interior-point methods. Along this line, Ohara
and Tsuchiya [21] developed an information geometric framework for LP, and
provided a sharp iteration bound of an interior point method by means of a
differential geometric measure of the central curve; see [12] for further
generalization. We are partly inspired by their framework: Our setting is on a
manifold $M$ with a connection $\nabla$ and a Riemannian metric
$\langle,\rangle_{f}$ given by the Hessian of an SC-function $f$. Here
$\nabla$ is not necessarily the Levi-Civita connection of
$\langle,\rangle_{f}$, and the dual connection $\nabla^{*}$, an information
geometric concept, plays a role.

One of important aspects of self-concordant functions is its relation to the
Fenchel-Legendre duality in convex analysis; see [17, Section 5.1.5]. Our
presented framework lacks such an aspect. Recently, several analogues of
Fenchel-Legendre duality are considered for Hadamard manifolds [9, 27]. It is
an interesting direction to incorporate them into the framework or to take
inspiration from them to introduce a more reasonable definition of self-
concordance on manifolds.

#### Organization.

The rest of this paper is organized as follows. In Section 2, we give
preliminaries on linear algebra and differential geometry. In Section 3, we
present the results on self-concordance. In Section 4, we present the results
on squared distance functions on hyperbolic spaces.

##  2 Preliminaries

###  2.1 Bilinear forms

In this paper, all vector spaces are finite dimensional and over
${\mathbb{R}}$. For a vector space $V$, let $V^{*}$ denote the dual space of
$V$, i.e., the vector space of all linear functions $V\to{\mathbb{R}}$. A
vector $p$ in $V^{*}$ is also written as $p(\cdot)$; this means that the dot
may be replaced by any vector $v\in V$, such as $p(v)$.

Let $U,V$ be vector spaces. For a linear map $\tau:U\to V$, let
$\tau^{*}:V^{*}\to U^{*}$ denote the dual map defined by $p(\cdot)\mapsto
p(\tau(\cdot))$. For a multilinear form $G\in V^{*}\otimes\cdots\otimes V^{*}$
on $V$, let $\tau^{*}G\in U^{*}\otimes\cdots\otimes U^{*}$ denote the
multilinear form on $U$ defined by
$\tau^{*}G:=G(\tau(\cdot),\cdots,\tau(\cdot))$.

A bilinear form $G\in V^{*}\otimes V^{*}$ is said to be symmetric if
$G(u,v)=G(v,u)$ for $u,v\in V$. A symmetric bilinear form $G\in V^{*}\otimes
V^{*}$ is viewed as $G:V\to V^{*}$ by $v\mapsto G(v,\cdot)=G(\cdot,v)$.
Suppose that $G$ is nondegenerate. The inverse map $G^{-1}:V^{*}\to V$ is
viewed as a symmetric bilinear form on $V^{*}$ by
$G^{-1}(p,q):=G(G^{-1}p,G^{-1}q)$. If $\tau:U\to V$ is a linear isomorphism,
then it holds,

$(\tau^{*}G)^{-1}=\tau^{-1}G^{-1},$ (2.1)

where $(\tau^{-1})^{**}=\tau^{-1}$. Indeed, it holds
$v\mapsto(\tau^{*}G)v=G(\tau(v),\tau(\cdot))=\tau^{*}(G\tau v)$, and hence
$p\mapsto(\tau^{*}G)^{-1}p=\tau^{-1}(G^{-1}(\tau^{*})^{-1}p)=G^{-1}((\tau^{-1})^{*}(p),(\tau^{-1})^{*}(\cdot))$.

For two symmetric bilinear forms $F,G$ on $U$, the notation $F\preceq G$ means
that $F(u,u)\leq G(u,u)$ for all $u\in U$. If $F\succeq 0$, then $F$ is called
positive semidefinite. In addition, if $F$ is nondegenerate, $F$ is called
positive definite. Let $G$ be a positive definite bilinear form on $U$. Then
$G$ defines the inner product $\langle,\rangle$ on $U$ by $\langle
u,v\rangle:=G(u,v)$, and the norm $\|u\|:=\sqrt{\langle u,u\rangle}$
accordingly. Let $F:U\to U^{*}$ be another symmetric bilinear form. The linear
transformation $G^{-1}F:U\to U$ is symmetric with respect to
$\langle,\rangle$, i.e., $\langle u,G^{-1}Fv\rangle=\langle
G^{-1}Fu,v\rangle(=F(u,v))$. In particular, $G^{-1}F$ can be diagonalized with
real eigenvalues and orthonormal eigenvectors. Then

$F\preceq G\Leftrightarrow\mbox{each eigenvalue of $G^{-1}F$ is at most $1$}.$
(2.2)

Suppose, in addition, that $F$ is also positive definite. Then it holds

$F\preceq G\Leftrightarrow F^{-1}\succeq G^{-1}.$ (2.3)

These can be seen from the matrix representation
$\tilde{F}=(F(e_{i},e_{j})),\tilde{G}=(G(e_{i},e_{j}))$ of $F,G$ with respect
to an orthonormal basis for $\langle,\rangle$ (so that
$\tilde{G}=\tilde{G}^{-1}=I$).

Additionally, $G$ defines an inner product $\langle,\rangle^{*}$ and norm
$\|\cdot\|^{*}$ of the dual space $U^{*}$ by $\langle
p,q\rangle^{*}:=G^{-1}(p,q)$ and $\|p\|^{*}:=\sqrt{\langle p,p\rangle^{*}}$.
Then the following version of Cauchy-Schwarz inequality holds:

$p(u)\leq\|p\|^{*}\|u\|\quad(u\in U,p\in U^{*}).$ (2.4)

This follows from $p(u)=(GG^{-1}p)(u)=G(G^{-1}p,u)=\langle
G^{-1}p,u\rangle\leq\|G^{-1}p\|\|u\|$ and
$\|G^{-1}p\|^{2}=G(G^{-1}p,G^{-1}p)=(\|p\|^{*})^{2}$.

###  2.2 Manifold with an affine connection

We here introduce basic terminologies for smooth manifolds; our references are
[4, 24]. Throughout the paper, sufficient smoothness is assumed for functions,
maps, and vector/tensor fields on manifolds. Let $M$ be an $n$-dimensional
manifold. For $x\in M$, let $T_{x}=T_{x}(M)$ denote the tangent space at $x$.
For a vector field $X$ on $M$, let $X_{x}\in T_{x}$ denote the vector at $x$.
For a map $\varphi:M\to N$ and $x\in M$, where $N$ is a manifold, let
$D\varphi(x):T_{x}(M)\to T_{\varphi(x)}(N)$ denote the differential of
$\varphi$ at $x$. For a curve $\gamma:[a,b]\to M$, let
$\dot{\gamma}(t):=D\gamma(t)(d/dt)$ be the vector tangent to $\gamma$ at
$t\in[a,b]$.

Suppose that $M$ has an affine connection $\nabla$ on tangent bundle
$T(M)=\bigcup_{x\in M}T_{x}$. Given a curve $\gamma:[a,b]\to M$ with
$x=\gamma(a)$, the connection $\nabla$ determines the parallel transport along
$\gamma$, which is a linear isomorphism $\tau_{\gamma,t}$ from $T_{x}$ to
$T_{\gamma(t)}$ for $t\in[a,b]$. For a vector field $Y$ and vector $u\in
T_{x}$ at $x\in M$, the covariant derivative $\nabla_{u}Y$ of $Y$ by $u$ is
given by $\nabla_{u}Y=\lim_{t\to
0}(\tau_{\gamma,t}^{-1}Y_{\gamma(t)}-Y_{x})/t$, where $\gamma:[0,l]\to M$ is
any smooth curve with $\gamma(0)=x$ and $\dot{\gamma}(0)=u$. The covariant
derivative $\nabla_{X}Y$ of $Y$ by a vector field $X$ is a vector field so
that $(\nabla_{X}Y)_{x}=\nabla_{X_{x}}Y$. The geodesic is a curve
$\gamma:[0,l]\to M$ such that
$\dot{\gamma}(t)=\tau_{\gamma,t}(\dot{\gamma}(0))$. A geodesic $\gamma$ is a
solution of differential equation $\nabla_{\dot{\gamma}(t)}\gamma(t)=0$, and
it is uniquely determined from initial point $x=\gamma(0)$ and direction
$u=\dot{\gamma}(0)$. Particularly, given $x\in M$ and $u\in T_{x}$, there is a
geodesic $\gamma:[0,l]\to M$ with $x=\gamma(0)$ and direction
$u=\dot{\gamma}(0)$. In this case, we write $\gamma(t)=\exp_{x}tu$. The map
$u\mapsto\exp_{x}1u$ is defined on a neighborhood of the origin of $T_{x}$,
and is called the exponential map.

The covariant derivative is extended for tensor fields; see [4, Section 10.7]
and [24, II.1.3]. In this paper, we consider it for covariant tensor fields.
For a $(0,k)$-tensor field $G=(G_{x})_{x\in M}$, where $G_{x}\in
T_{x}^{*}\otimes\cdots\otimes T_{x}^{*}$, the covariant derivative
$\nabla_{u}G$ by $u\in T_{x}$ is defined by

$\nabla_{u}G:=\left.\frac{\rm d}{{\rm
d}t}\tau_{\gamma,t}^{*}G_{x}\right|_{t=0},$ (2.5)

where $\gamma:[0,l]\to M$ is any curve with $\gamma(0)=x$ and
$\dot{\gamma}(0)=u$. The covariant derivative $\nabla_{X}G$ by vector field
$X$ is defined as a $(0,k)$-tensor field obtained by
$\nabla_{X}G=(\nabla_{X_{x}}G)_{x\in M}$. The covariant derivative
$\nabla_{X}G$ can also be written as (or defined by)

$(\nabla_{X}G)(Y_{1},\ldots,Y_{k})=X(G(Y_{1},\ldots,Y_{k}))-\sum_{i=1}^{k}G(Y_{1},\ldots,\nabla_{X}Y_{i},\ldots,Y_{k}),$
(2.6)

where $X,Y_{1},\ldots,Y_{k}$ are vector fields. Then
$(Y_{1},\ldots,Y_{k},X)\mapsto(\nabla_{X}G)(Y_{1},\ldots,Y_{k})$ is a
$(0,k+1)$-tensor field.

In this paper, we assume that $(M,\nabla)$ satisfies the following conditions:

  * •

$\nabla$ is torsion-free: $\nabla_{X}Y-\nabla_{Y}X=[X,Y]$ holds for vector
fields $X,Y$.

  * •

For each point $x\in M$, the exponential map $\exp_{x}$ is defined on $T_{x}$
and is a surjection from $T_{x}$ to $M$.

We basically consider the case where $M$ is a complete Riemannian manifold and
$\nabla$ is the Levi-Civita connection; then $(M,\nabla)$ satisfies the above
conditions; see [24, III.1]. However, by its affine invariant nature, our
argument in Section 3 does not use the intrinsic Riemannian metric
$\langle,\rangle$ of $M$, and also consider another metric
$\langle,\rangle_{f}$ induced by a smooth function $f$ in question. So we do
not make $\langle,\rangle$ explicit.

Let $f:M\to{\mathbb{R}}$ be a smooth function. The differential
$Df=(Df_{x})_{x\in M}$ of $f$ is a $(0,1)$-tensor field, where
$Df_{x}=Df(x):T_{x}\to T_{f(x)}({\mathbb{R}})={\mathbb{R}}$ is given by

$Df_{x}(u)=\left.\frac{\rm d}{{\rm d}t}f(\gamma(t))\right|_{t=0}\quad(u\in
T_{x})$ (2.7)

for any curve $\gamma:[0,l]\to{\mathbb{R}}$ with $\dot{\gamma}(0)=u$. If $f$
is viewed as a $(0,0)$-tensor, then $Df(X)$ equals $\nabla_{X}f$. A further
differentiation of $Df$ yields a $(0,2)$-tensor field $Hf=(Hf_{x})_{x\in M}$,
called the Hessian of $f$, as

$Hf(X,Y):=(\nabla_{X}Df)(Y)=X(Df(Y))-Df(\nabla_{X}Y),$ (2.8)

where $X,Y$ are vector fields. In the case where $\nabla$ is the Levi-Civita
connection of a Riemannian manifold, this matches the usual definition of the
Hessian $(X,Y)\mapsto\langle\nabla_{X}\mathop{\rm grad}f,Y\rangle$; see [4,
Example 10.78].

The bilinear form $Hf_{x}\in T^{*}_{x}\otimes T^{*}_{x}$ is called the Hessian
of $f$ at $x\in M$. The following is well-known. See [4, Proposition 5.15].

######  Lemma 2.1.

$Hf_{x}$ is a symmetric bilinear form on $T_{x}$.

###### Proof.

This follows from $(\nabla_{X}Df)(Y)=X(Df(Y))-Df(\nabla_{X}Y)=XYf-
Df(\nabla_{Y}X+[X,Y])=(XY-[X,Y])f-Df(\nabla_{Y}X)=YXf-
Df(\nabla_{Y}X)=(\nabla_{Y}Df)(X)$. ∎

The diagonal of the Hessian is given as follows. See [4, Eaxmple 10.81].

######  Lemma 2.2.

For $x\in M$ and $u\in T_{x}$, we have

$Hf_{x}(u,u)=\left.\frac{{\rm d}^{2}}{{\rm
d}t^{2}}f(\exp_{x}tu)\right|_{t=0}.$

###### Proof.

For $\gamma(t)=\exp_{x}tu$ we have $\dot{\gamma}(t)=\tau_{\gamma,t}u$ and
$Df_{\gamma(t)}(\tau_{\gamma,t}u)=Df_{\gamma(t)}(\dot{\gamma}(t))=\frac{\rm
d}{{\rm d}t}f(\gamma(t))$. Apply (2.5). ∎

We consider the covariant derivative of $(0,2)$-tensor field $Hf$, which
provides a $(0,3)$-tensor field $(X,Y,Z)\mapsto(\nabla_{X}Hf)(Y,Z)$.
Accordingly, we have a trilinear form $(u,v,w)\mapsto(\nabla_{u}H)(v,w)$ on
each $T_{x}$. In contrast to the Euclidean case, this tri-linear form is not
necessarily symmetric, due to nonzero curvature; see e.g., [4, Exercise
10.87]. Recall the curvature, which is a $(1,3)$-tensor field $(X,Y,Z)\mapsto
R(X,Y)Z$ defined by

$R(X,Y)Z:=\nabla_{X}\nabla_{Y}Z-\nabla_{Y}\nabla_{X}Z-\nabla_{[X,Y]}Z.$ (2.9)

######  Lemma 2.3.

$(\nabla_{X}Hf)(Y,Z)=(\nabla_{Y}Hf)(X,Z)-(R(X,Y)Z)f.$

###### Proof.

By definition, we have

$\displaystyle(\nabla_{X}Hf)(Y,Z)=X(Hf(Y,Z))-Hf(\nabla_{X}Y,Z)-Hf(Y,\nabla_{X}Z)$
$\displaystyle=X(YZf-
Df(\nabla_{Y}Z))-(\nabla_{X}Y)Df(Z)+Df(\nabla_{\nabla_{X}Y}Z)$
$\displaystyle\quad-YDf(\nabla_{X}Z)+Df(\nabla_{Y}\nabla_{X}Z).$

By changing role of $X,Y$, we have the expression of $(\nabla_{Y}Hf)(X,Z)$,
and obtain

$\displaystyle(\nabla_{X}Hf)(Y,Z)-(\nabla_{Y}Hf)(X,Z)$
$\displaystyle=([X,Y]-\nabla_{X}Y+\nabla_{Y}X)Zf+\nabla_{\nabla_{X}Y-\nabla_{Y}X}Zf+\nabla_{Y}\nabla_{X}Zf-\nabla_{X}\nabla_{Y}Zf$
$\displaystyle=-R(X,Y)Zf.$

∎

The diagonal of $\nabla_{X}Hf(Y,Z)$ is given by differentiation along
geodesic; see [4, Example 10.81].

######  Lemma 2.4.

For $x\in M$ and $u\in T_{x}$, we have

$(\nabla_{u}Hf)(u,u)=\left.\frac{{\rm d}^{3}}{{\rm
d}t^{3}}f(\exp_{x}tu)\right|_{t=0}.$

###### Proof.

For $\gamma=\exp_{x}tu$, we have $\frac{\rm d}{{\rm
d}t}Hf_{\gamma(t)}(\tau_{\gamma,t}u,\tau_{\gamma,t}u)=\frac{\rm d}{{\rm
d}t}Hf_{\gamma(t)}(\dot{\gamma}(t),\dot{\gamma}(t))=\frac{\rm d^{3}}{{\rm
d}t^{3}}f(\gamma(t))$. ∎

##  3 Self-concordant functions

Let $M$ be a manifold with an affine connection $\nabla$ (satisfying the above
conditions). A subset $C\subseteq M$ is said to be convex (or more precisely
geodesically convex) if for every geodesic $\gamma:[a,b]\to M$ with
$\gamma(a),\gamma(b)\in C$ it holds $\gamma(t)\in C$ for every $t\in[a,b]$.
Accordingly, a function $f:M\to{\mathbb{R}}\cup\\{+\infty\\}$ is said to
convex if for every geodesic $\gamma:[a,b]\to M$ the function
$f\circ\gamma:[a,b]\to{\mathbb{R}}\cup\\{+\infty\\}$ is convex.

Let $C\subseteq M$ be an open convex subset, which is viewed as a submanifold
of $(M,\nabla)$.

######  Lemma 3.1.

$f:C\to{\mathbb{R}}$ is convex if and only if the Hessian $Hf_{x}$ is positive
semidefinite for all $x\in C$.

###### Proof.

This follows from Lemma 2.2 and: $f$ is convex $\Leftrightarrow$
$(f\circ\gamma)^{\prime\prime}(t)\geq 0$ for every geodesic $\gamma$. ∎

We say that a convex function $f:C\to{\mathbb{R}}$ is nondegenerate if
$Hf_{x}$ is positive definite for all $x\in C$, and closed (or lower
semicontinuous) if its epigraph $\\{(x,y)\in C\times{\mathbb{R}}\mid y\geq
f(x)\\}$ is a closed set. We often omit the subscript $x$ of tensor $G_{x}$ at
$x\in M$ if $x$ is clear.

###  3.1 Definitions and properties

Let $C\subseteq M$ be an open convex set. A closed and nondegenerate convex
function $f:C\to{\mathbb{R}}$ is called $\sigma$-self-concordant ($\sigma$-SC)
for $\sigma\geq 0$ if it satisfies

$|(\nabla_{v}Hf)(u,u)|\leq 2\sigma Hf(v,v)^{1/2}Hf(u,u)\quad(u,v\in T_{x},x\in
C),$ (3.1)

and is called weakly $\sigma$-self-concordant ($\sigma$-WSC) if it satisfies

$|(\nabla_{u}Hf)(u,u)|\leq 2\sigma Hf(u,u)^{3/2}\quad(u\in T_{x},x\in C).$
(3.2)

By Lemmas 2.2 and 2.4, the latter condition (3.2) is equivalent to:

$\left|(f\circ\gamma)^{\prime\prime\prime}(t)\right|\leq
2\sigma(f\circ\gamma)^{\prime\prime}(t)^{3/2}\quad(\gamma:\mbox{geodesic in
$C$}).$ (3.3)

The condition (3.3) is a natural analogue of the original definition of the
self-concordance by Nesterov and Nemirovskii [18]. So papers [10, 11, 28]
consider (3.2) as the definition of the self-concordance on manifolds; see
also the footnote of [5, p. 31].

In Euclidean space $M={\mathbb{R}}^{n}$, the self-concordance and weak self-
concordance are the same. Indeed, $(X,Y,Z)\mapsto\nabla_{X}Hf(Y,Z)$ is
symmetric (by $R=0$ and Lemma 2.3). Then, by Nesterov-Nemirovski lemma [18,
Appendix 1] for symmetric multilinear forms, (3.2) implies (3.1). However, for
a manifold with nontrivial curvature $R$, the trilinear form
$\nabla_{X}Hf(Y,Z)$ is not necessarily symmetric, and the Nesterov-Nemirovski
lemma is not applicable. We see in Section 4 that SC and WSC are actually
different. Note that $\nabla_{X}Hf(Y,Z)$ is symmetric on $Y,Z$, and hence by
the lemma the condition (3.1) is equivalent to $|\nabla_{u}Hf(v,w)|\leq
2\sigma Hf(u,u)^{1/2}Hf(v,v)^{1/2}Hf(w,w)^{1/2}$.

The behavior of a weighted sum of (W)SC-functions is the same as in the
Euclidean case [16, Theorem 4.1.1]([17, Theorem 5.1.1]), as follows.

######  Lemma 3.2.

For $i=1,2$, let $f_{i}:C_{i}\to{\mathbb{R}}$ be $\sigma_{i}$-(W)SC. Suppose
that $C_{1}\cap C_{2}$ has nonempty interior. For $\alpha,\beta>0$, the
function $\alpha f_{1}+\beta f_{2}:C_{1}\cap C_{2}\to{\mathbb{R}}$ is
$\sigma$-(W)SC for
$\sigma:=\max\\{\sigma_{1}/\sqrt{\alpha},\sigma_{2}/\sqrt{\beta}\\}$

For the WSC-case, the proof is also exactly the same as in the Euclidean case,
and is omitted. For the SC-case, it needs a little modification.

###### Proof.

Let $f:=\alpha f_{1}+\beta f_{2}$. For $x\in C_{1}\cap C_{2}$ and $u,v\in
T_{x}$, we have

$\displaystyle\frac{|\nabla_{v}Hf(u,u)|}{2Hf(u,u)^{1/2}Hf(v,v)}$
$\displaystyle\leq$
$\displaystyle\frac{\alpha|\nabla_{v}Hf_{1}(u,u)|+\beta|\nabla_{v}Hf_{2}(u,u)|}{2\sqrt{\alpha
Hf_{1}(v,v)+\beta Hf_{2}(v,v)}(\alpha Hf_{1}(u,u)+\beta Hf_{2}(u,u))}$ (3.4)
$\displaystyle\leq$
$\displaystyle\frac{\sqrt{\alpha}\sigma_{1}x_{1}\omega_{1}+\sqrt{\beta}\sigma_{2}x_{2}\omega_{2}}{\sqrt{x_{1}^{2}+x_{2}^{2}}(\alpha\omega_{1}+\beta\omega_{2})},$

where we let $x_{i}:=\sqrt{\alpha}Hf_{i}(v,v)^{1/2}$ and
$\omega_{i}:=Hf_{i}(u,u)$ for $i=1,2$. We bound the maximum of this quantity
(3.4). Observing invariance under the change
$(x_{1},x_{2},\omega_{1},\omega_{2})\to(sx_{1},sx_{2},t\omega_{1},t\omega_{2})$
for $s,t>0$, we may consider the following optimization problem:

Max.
$\displaystyle\sqrt{\alpha}\sigma_{1}\omega_{1}x_{1}+\sqrt{\beta}\sigma_{2}\omega_{2}x_{2}$
s.t. $\displaystyle x_{1}^{2}+x_{2}^{2}=1,\alpha\omega_{1}+\beta\omega_{2}=1,$
$\displaystyle x_{1},x_{2},\omega_{1},\omega_{2}\geq 0.$

Under fixing $\omega_{i}$, maximize this by $x_{i}$. This is a linear
optimization over unit circle, and hence the optimum is given by
$(x_{1},x_{2})=(\sqrt{\alpha}\sigma_{1}\omega_{1},\sqrt{\beta}\sigma_{2}\omega_{2})/\sqrt{\alpha\sigma_{1}^{2}\omega_{1}^{2}+\beta\sigma_{2}^{2}\omega_{2}^{2}}$.
The problem reduces to

$\mbox{Max.}\sqrt{\alpha\sigma_{1}^{2}\omega_{1}^{2}+\beta\sigma^{2}_{2}\omega^{2}_{2}}\
\ \mbox{s.t.}\ \ \alpha\omega_{1}+\beta\omega_{2}=1,\omega_{1},\omega_{2}\geq
0.$

The maximum is attained by $(1/\alpha,0)$ or $(0,1/\beta)$, and (3.4)
$\leq\max(\sigma_{1}/\sqrt{\alpha},\sigma_{2}/\sqrt{\beta})$, as required. ∎

Let $f:C\to{\mathbb{R}}$ be WSC. The Hessian $Hf_{x}$ of $f$ gives an inner
product $\langle,\rangle_{f,x}$ on each $T_{x}$:

$\langle u,v\rangle_{f,x}:=Hf_{x}(u,v)\quad(u,v\in T_{x}).$ (3.5)

Accordingly, we define the local norm by $\|u\|_{f,x}:=\sqrt{\langle
u,u\rangle_{f,x}}$. The manifold $C$ is viewed as a Riemannian manifold with
respect to this inner product $\langle,\rangle_{f}$, although $\nabla$ is not
necessarily the Levi-Civita connection of this Riemannian structure.

######  Remark 3.3.

This setting may be discussed from viewpoints of information geometry and
Hessian geometry [3, 26]. We can consider the dual connection $\nabla^{*}$ via
$\langle Y,\nabla^{*}_{X}Z\rangle_{f}:=X\langle Y,Z\rangle_{f}-\langle
Y,\nabla_{X}Z\rangle_{f}$. The symmetry of $(0,3)$-tensor $\nabla_{X}Hf(Y,Z)$
corresponds to the Codazzi equation for metric $\langle,\rangle_{f}$, and to
$\nabla^{*}$ being torsion-free. If $R=0$ ($M$ is flat), then
$(M,\langle,\rangle_{f},\nabla,\nabla^{*})$ is a dually-flat statistical
manifold— a well-studied and central concept in information geometry. The main
focus in this paper is the case of $R\neq 0$. In the view of Lemma 2.3,
$\nabla^{*}$ is hardly torsion-free. Information geometry methods for such
situations seem less developed.

For $x\in C$ and $r\geq 0$, the Dikin ellipsoid $W^{0}(x;r)$ is defined by

$W^{0}(x;r):=\\{\gamma(1)\mid\mbox{$\exists$ geodesic }\gamma:[0,1]\to
C,\gamma(0)=x,\|\dot{\gamma}(0)\|_{f,x}<r\\},$

which is the image of the open ball of radius $r$ in $T_{x}$ by $\exp_{x}$. In
this setting, some of basic properties and arguments of (W)SC in the Euclidean
case can be extended in a straightforward manner. The following three
propositions and their proofs are direct adaptations of those in [16, 17];
they are basically replacements of type:

$\displaystyle\langle\nabla f(x),h\rangle=\left.\frac{\rm d}{{\rm
d}t}f(x+th)\right|_{t=0}\quad\Longrightarrow\quad
Df_{\gamma(0)}(\dot{\gamma}(0))=\left.\frac{\rm d}{{\rm
d}t}f(\gamma(t))\right|_{t=0},$ $\displaystyle\langle\nabla f(x+h)-\nabla
f(x),h\rangle=\int_{0}^{1}\langle\nabla^{2}f(x+th)h,h\rangle{\rm d}t$
$\displaystyle\quad\Longrightarrow\quad
Df_{\gamma(1)}(\dot{\gamma}(1))-Df_{\gamma(0)}(\dot{\gamma}(0))=\int_{0}^{1}Hf_{\gamma(t)}(\dot{\gamma}(t),\dot{\gamma}(t)){\rm
d}t.$

where $\gamma:[0,1]\to M$ is a geodesic. The first one corresponds to [16,
Theorem 4.1.5] ([17, Theorem 5.1.5]).

######  Proposition 3.4.

Suppose that $f$ is $\sigma$-WSC.

  * (1)

For any $x\in C$, it holds $W^{0}(x;1/\sigma)\subseteq C.$

  * (2)

For a geodesic $\gamma:[0,1]\to C$, it holds

$\|\dot{\gamma}(1)\|_{f,\gamma(1)}\geq\frac{\|\dot{\gamma}(0)\|_{f,\gamma(0)}}{1+\sigma\|\dot{\gamma}(0)\|_{f,\gamma(0)}}.$
(3.6)

In addition, if $\gamma(1)\in W^{0}(\gamma(0);1/\sigma)$, then

$\|\dot{\gamma}(1)\|_{f,\gamma(1)}\leq\frac{\|\dot{\gamma}(0)\|_{f,\gamma(0)}}{1-\sigma\|\dot{\gamma}(0)\|_{f,\gamma(0)}}.$
(3.7)

###### Proof.

(1). Consider a geodesic $\gamma:[0,1]\to M$ with $\gamma(0)=x$. Suppose that
for $a\in(0,1]$ the point $\gamma(a)$ is in the boundary of $C$. Define a
univariate function $\phi:[0,a)\to{\mathbb{R}}$ by

$\phi(t):=1/\|\dot{\gamma}(t)\|_{f,\gamma(t)}=Hf(\dot{\gamma}(t),\dot{\gamma}(t))^{-1/2}=(f\circ\gamma)^{\prime\prime}(t)^{-1/2}.$
(3.8)

Then we have

$\left|\phi^{\prime}(t)\right|=\frac{\left|(f\circ\gamma)^{\prime\prime\prime}(t)\right|}{2(f\circ\gamma)^{\prime\prime}(t)^{3/2}}\leq\sigma.$

By integrating $-\sigma\leq\phi^{\prime}(t)\leq\sigma$ from $0$ to $a$, we
have

$\phi(0)-\sigma a\leq\lim_{t\to a}\phi(t)\leq\phi(0)+\sigma a$ (3.9)

Since $f$ is lower semicontinuous and $C$ is open, it holds
$f(\gamma(t))\to\infty$ for $t\to a$. Then $\lim_{t\to a}\phi(t)=0$. Hence it
must hold $a\geq\phi(0)/\sigma$. If
$\phi(0)/\sigma>1\Leftrightarrow\|\dot{\gamma}(0)\|_{f,x}<1/\sigma$, then
$\gamma(1)$ belongs to the domain $C$ of $f$. This implies (1).

(2). From (3.9) and $\gamma(1)\in C$, we have $\phi(1)\leq\phi(0)+\sigma$,
which is equivalent to $1/\|\dot{\gamma}(1)\|_{f,x}\leq
1/\|\dot{\gamma}(0)\|_{f,x}+\sigma$. This is (3.6). The second equation (3.7)
follows similarly from $\phi(1)\geq\phi(0)-\sigma$. ∎

The next corresponds to [16, Theorems 4.1.7 and 4.1.8] ([17, Theorems 5.1.8
and 5.1.9]).

######  Proposition 3.5.

Suppose that $f$ is $\sigma$-WSC. For a geodesic $\gamma:[0,1]\to C$, it holds

$\displaystyle
Df_{\gamma(1)}(\dot{\gamma}(1))-Df_{\gamma(0)}(\dot{\gamma}(0))\geq\frac{\|\dot{\gamma}(0)\|^{2}_{f,\gamma(0)}}{1+\sigma\|\dot{\gamma}(0)\|_{f,\gamma(0)}},$
(3.10) $\displaystyle f(\gamma(1))\geq
f(\gamma(0))+Df_{\gamma(0)}(\dot{\gamma}(0))+\frac{1}{\sigma^{2}}\omega(\sigma\|\dot{\gamma}(0)\|_{f,\gamma(0)}),$
(3.11)

where $\omega(t):=t-\log(1+t)$. In addition, if $\gamma(1)\in
W^{\circ}(\gamma(0);1/\sigma)$, then it holds

$\displaystyle
Df_{\gamma(1)}(\dot{\gamma}(1))-Df_{\gamma(0)}(\dot{\gamma}(0))\leq\frac{\|\dot{\gamma}(0)\|^{2}_{f,\gamma(0)}}{1-\sigma\|\dot{\gamma}(0)\|_{f,\gamma(0)}},$
(3.12) $\displaystyle f(\gamma(1))\leq
f(\gamma(0))+Df_{\gamma(0)}(\dot{\gamma}(0))+\frac{1}{\sigma^{2}}\omega_{*}(\sigma\|\dot{\gamma}(0)\|_{f,\gamma(0)}),$
(3.13)

where $\omega_{*}(t):=-t-\log(1-t)$.

###### Proof.

We only show the latter part; the former is similar.

$\displaystyle
Df_{\gamma(1)}(\dot{\gamma}(1))-Df_{\gamma(0)}(\dot{\gamma}(0))=\int_{0}^{1}\frac{\rm
d}{{\rm d}t}Df_{\gamma(t)}(\dot{\gamma}(t)){\rm
d}t=\int_{0}^{1}Hf_{\gamma(t)}(\dot{\gamma}(t),\dot{\gamma}(t)){\rm d}t$
$\displaystyle=\int_{0}^{1}\|\dot{\gamma}(t)\|^{2}_{f,\gamma(t)}{\rm
d}t\leq\int_{0}^{1}\frac{\|\dot{\gamma}(0)\|^{2}_{f,\gamma(0)}}{(1-\sigma
t\|\dot{\gamma}(0)\|_{f,\gamma(0)})^{2}}{\rm d}t,$

where the inequality follows by applying (3.7) for geodesic
$s\mapsto\gamma(ts)$, and the last integration equals the RHS of (3.12). By
using (3.7) for geodesic $s\mapsto\gamma(ts)$, we have

$\displaystyle
f(\gamma(1))-f(\gamma(0))-Df_{\gamma(0)}(\dot{\gamma}(0))=\int_{0}^{1}\frac{\rm
d}{{\rm d}t}f(\gamma(t)){\rm d}t-Df_{\gamma(0)}(\dot{\gamma}(0))$
$\displaystyle=\int_{0}^{1}Df_{\gamma(t)}(\gamma(t))-Df_{\gamma(0)}(\dot{\gamma}(0)){\rm
d}t\leq\int_{0}^{1}\frac{t\|\dot{\gamma}(0)\|^{2}_{f,\gamma(0)}}{1-\sigma
t\|\dot{\gamma}(0)\|_{f,\gamma(0)}}{\rm d}t,$

where the last integration equals the third term of RHS of (3.13). ∎

We next consider properties of SC that cannot be derived from WSC. The
following corresponds to [16, Theorem 4.1.6 and Corollary 4.1.4] ([17, Theorem
5.1.7 an Corollary 5.1.5]).

######  Proposition 3.6.

Suppose that $f$ is $\sigma$-SC. For a geodesic $\gamma:[0,1]\to C$ with
$\gamma(1)\in W^{0}(\gamma(0);1/\sigma)$, it hold

$(1-\sigma\|\dot{\gamma}(0)\|_{f,\gamma(0)})^{2}Hf_{\gamma(0)}\preceq\tau_{\gamma,1}^{*}Hf_{\gamma(1)}\preceq\frac{1}{(1-\sigma\|\dot{\gamma}(0)\|_{f,\gamma(0)})^{2}}Hf_{\gamma(0)},$
(3.14)

and

$\displaystyle\left\\{1-\sigma\|\dot{\gamma}(0)\|_{f,\gamma(0)}+\frac{1}{3}\sigma^{2}\|\dot{\gamma}(0)\|_{f,\gamma(0)}^{2}\right\\}Hf_{\gamma(0)}$
$\displaystyle\quad\quad\preceq\int_{0}^{1}\tau_{\gamma,t}^{*}Hf_{\gamma(t)}{\rm
d}t\preceq\frac{1}{1-\sigma\|\dot{\gamma}(0)\|_{f,\gamma(0)}}Hf_{\gamma(0)}.$
(3.15)

###### Proof.

Let $u\in T_{x}$. Define $\psi:[0,1]\to{\mathbb{R}}$ by

$\psi(t):=\|\tau_{\gamma,t}u\|^{2}_{f,\gamma(t)}=\tau^{*}_{\gamma,t}Hf_{\gamma(t)}(u,u).$

Then we have

$\displaystyle\left|\psi^{\prime}(t)\right|$ $\displaystyle=$
$\displaystyle\left|(\nabla_{\dot{\gamma}(t)}Hf_{\gamma(t)})(\tau_{\gamma,t}u,\tau_{\gamma,t}u)\right|\leq
2\sigma\|\dot{\gamma}(t)\|_{f,\gamma(t)}\|\tau_{\gamma,t}u\|_{f,\gamma(t)}^{2}$
$\displaystyle\leq$
$\displaystyle\frac{2\sigma\|\dot{\gamma}(0)\|_{f,\gamma(0)}}{1-\sigma
t\|\dot{\gamma}(0)\|_{f,\gamma(0)}}\psi(t).$

Integrating $(\log\psi(t))^{\prime}=\psi^{\prime}(t)/\psi(t)$ from $0$ to $1$,
we have

$2\log(1-\sigma\|\dot{\gamma}(0)\|_{f,\gamma(0)})\leq\log\frac{\psi(1)}{\psi(0)}\leq-2\log(1-\sigma\|\dot{\gamma}(0)\|_{f,\gamma(0)}),$

which means (3.14). The latter inequality (3.15) is obtained by integrating

$(1-\sigma
t\|\dot{\gamma}(0)\|_{f,\gamma(0)})^{2}Hf_{\gamma(0)}\preceq\tau_{\gamma,t}^{*}Hf_{\gamma(t)}\preceq\frac{1}{(1-\sigma
t\|\dot{\gamma}(0)\|_{f,\gamma(0)})^{2}}Hf_{\gamma(0)}$

from $0$ to $1$. ∎

An equivalent formulation of (3.14) is

$1-\sigma\|\dot{\gamma}(0)\|_{f,\gamma(0)}\leq\frac{\|\tau_{\gamma,1}u\|_{f,\gamma(1)}}{\|u\|_{f,\gamma(0)}}\leq\frac{1}{1-\sigma\|\dot{\gamma}(0)\|_{f,\gamma(0)}}\quad(u\in
T_{\gamma(0)}).$ (3.16)

Namely, the parameter $\sigma$ controls variance of the local norm
$\|\cdot\|_{f}$ under the parallel transport with respect to $\nabla$. This is
in fact equivalent to SC; the book by Renegar [22] adopts (3.16) as the
definition of SC in the Euclidean case. Indeed, by a similar calculation in
[22, p. 61], we can rewrite (3.16) as

$\displaystyle-2\sigma\|u\|_{f,\gamma(0)}^{2}\|v\|_{f,\gamma(0)}+\sigma^{2}t\|v\|^{2}_{f,\gamma(0)}\leq$
$\displaystyle\quad\quad\frac{\|\tau_{\gamma,t}u\|_{f,\gamma(t)}^{2}-\|u\|_{f,\gamma(0)}^{2}}{t}\leq\frac{2\sigma\|u\|_{f,\gamma(0)}^{2}\|v\|_{f,\gamma(0)}+\sigma^{2}t\|v\|^{2}_{f,\gamma(0)}}{(1-\sigma
t\|v\|_{f,\gamma(0)})^{2}},$

where $v:=\dot{\gamma}(0)$. For $t\to 0$, we have (3.1).

#### Information geometric view.

We finally present a (dual) formulation of the above properties in terms of
information geometry. Define the dual inner product
$\langle,\rangle^{*}_{f,x}$ on $T_{x}^{*}$ by $\langle
p,q\rangle^{*}_{f,x}:=Hf_{x}^{-1}(p,q)$. Accordingly, define the dual norm
$\|p\|_{f,x}^{*}:=\sqrt{\langle p,q\rangle^{*}_{f,x}}$.

######  Lemma 3.7.

Under the same assumption of Proposition 3.6, it holds

$1-\sigma\|\dot{\gamma}(0)\|_{f,\gamma(0)}\leq\frac{\|p\|^{*}_{f,\gamma(1)}}{\|\tau_{\gamma,1}^{*}p\|^{*}_{f,\gamma(0)}}\leq\frac{1}{1-\sigma\|\dot{\gamma}(0)\|_{f,\gamma(0)}}\quad(p\in
T_{\gamma(1)}^{*}).$ (3.17)

This is obtained from inverting (3.14) by (2.1) and (2.3). The covariant
derivative (2.5) of covariant vectors defines a connection $\nabla$ of
cotangent bundle $T^{*}(M)=\bigcup_{x\in M}T^{*}_{x}$, where the parallel
transport is given by $(\tau^{*}_{\gamma,t})^{-1}:T^{*}_{\gamma(0)}\to
T^{*}_{\gamma(t)}$. The Hessian $Hf$ is a vector bundle isomorphism $T(M)\to
T^{*}(M)$. Then, the dual connection $\nabla^{*}$ (Remark 3.3) is the pull
back of the connection $\nabla$ on $T^{*}(M)$ by $Hf$; see [20, Proposition
5.1]. Specifically, $\nabla^{*}$ is given by

$\nabla^{*}_{u}X=Hf^{-1}_{x}\nabla_{u}Hf(X)\quad(u\in T_{x},x\in M),$ (3.18)

where $Hf(X)=(Hf_{x}(X_{x},\cdot))_{x\in M}$ is a $(0,1)$-tensor field. The
corresponding parallel transport $\delta_{\gamma,t}:T_{\gamma(0)}\to
T_{\gamma(t)}$ for a curve $\gamma:[0,t]\to M$ is given by

$\delta_{\gamma,t}(u)=Hf_{\gamma(1)}^{-1}(\tau^{*}_{\gamma,t})^{-1}Hf_{\gamma(0)}(u,\cdot)\quad(u\in
T_{\gamma(0)}).$ (3.19)

Consider to transport a vector $u\in T_{\gamma(0)}$ to $T_{\gamma(t)}$ along
curve $\gamma$ by means of $\nabla$, and then return it back to
$T_{\gamma(0)}$ along $\gamma$ by means of $\nabla^{*}$. This gives rise to an
automorphism $\delta_{\gamma,t}^{-1}\tau_{\gamma,t}$ on $T_{\gamma(0)}$, which
is written as

$\delta_{\gamma,t}^{-1}\tau_{\gamma,t}u=Hf_{\gamma(0)}^{-1}Hf_{\gamma(t)}(\tau_{\gamma,t}u,\tau_{\gamma,t}(\cdot))\quad(u\in
T_{\gamma(0)}).$ (3.20)

Particularly, $\delta_{\gamma,t}^{-1}\tau_{\gamma,t}$ is a symmetric
automorphism with respect to $\langle,\rangle_{f,x}$. Then, via (2.2),
Proposition 3.6 is rephrased as follows.

######  Proposition 3.8.

Under the same assumption of Proposition 3.6, we have the following:

  * (1)

Each eigenvalue $\mu$ of $\delta_{\gamma,1}^{-1}\tau_{\gamma,1}$ satisfies

$(1-\sigma\|\dot{\gamma}(0)\|_{f,x})^{2}\leq\mu\leq\frac{1}{(1-\sigma\|\dot{\gamma}(0)\|_{f,x})^{2}}.$

Additionally, each eigenvalue $\mu^{\prime}$ of
$\int_{0}^{1}\delta_{\gamma,t}^{-1}\tau_{\gamma,t}{\rm d}t$ satisfies

$1-\sigma\|\dot{\gamma}(0)\|_{f,x}+\frac{1}{3}\sigma^{2}\|\dot{\gamma}(0)\|_{f,x}^{2}\leq\mu^{\prime}\leq\frac{1}{1-\sigma\|\dot{\gamma}(0)\|_{f,x}}.$

  * (2)

It holds

$1-\sigma\|\dot{\gamma}(0)\|_{f,\gamma(0)}\leq\frac{\|v\|_{f,\gamma(1)}}{\|\delta_{\gamma,1}^{-1}v\|_{f,\gamma(0)}}\leq\frac{1}{1-\sigma\|\dot{\gamma}(0)\|_{f,\gamma(0)}}\quad(v\in
T_{\gamma(1)}).$ (3.21)

The second statement follows from Lemma 3.7 and
$\|\tau_{\gamma,1}^{*}p\|^{*}_{f,\gamma(0)}=\|\delta^{-1}_{\gamma,1}v\|_{f,\gamma(0)}$
for $p=Hf_{\gamma(1)}v$.

###  3.2 Newton’s method

Here we consider the Newton’s method on $M$; see [4, Section 6.2] for a
manifold version of Newton’s method. Based on the second order approximation
$u\mapsto f(x)+Df_{x}(u)+\frac{1}{2}Hf_{x}(u,u)$ of $u\mapsto f(\exp_{x}u)$,
the Newton direction at $x\in C$ is defined as the vector $\overline{u}\in
T_{x}$ satisfying

$Df_{x}(\cdot)+Hf_{x}(\overline{u},\cdot)=0.$ (3.22)

Equivalently, $\overline{u}:=-Hf_{x}^{-1}(Df_{x})$, where $Hf_{x}$ is viewed
as $T_{x}\to T_{x}^{*}$. Then the Newton update at $x$ is formulated as

$x\leftarrow x^{+}:=\exp_{x}\overline{u}.$ (3.23)

The Newton decrement $\lambda_{f}(x)$ is defined by

$\lambda_{f}(x):=\|\overline{u}\|_{f,x}=\|Df_{x}\|^{*}_{f,x}.$ (3.24)

For SC functions, the Newton decrement provides a certificate for the current
point $x$ to belong to the region of quadratic convergence of the Newton
iterations. The following corresponds to [16, Theorem 4.1.14] ([17, Theorem
5.2.2.1]),

######  Theorem 3.9.

Suppose that $f$ is $\sigma$-SC. For $x\in C$, if $\lambda_{f}(x)<1/\sigma$,
then $x^{+}\in C$ and

$\lambda_{f}(x^{+})\leq\frac{\sigma\lambda_{f}(x)^{2}}{(1-\sigma\lambda_{f}(x))^{2}}.$
(3.25)

In particular, if $\lambda_{f}(x)<(3-\sqrt{5})/2\sigma=0.3819\cdots/\sigma$,
then the point $x$ belongs to the region of quadratic convergence of the
Newton iteration.

The proof basically adapts [16, Therem 4.1.14], although it may be less
obvious than others and has a different presentation for revealing its
information geometric nature. The following formula of the next Newton
direction by parallel transports $\delta,\tau$ of $\overline{u}$ may be
interesting in its own right, though it is an obvious rewriting.

######  Lemma 3.10.

Suppose that $x^{+}=\exp_{x}\overline{u}$ belongs to $C$. Let
$\overline{u}^{+}$ denote the Newton direction at $x^{+}$. Then,

$\delta_{\gamma,1}^{-1}\overline{u}^{+}=\overline{u}-\int_{0}^{1}\delta_{\gamma,t}^{-1}\tau_{\gamma,t}\overline{u}{\rm
d}t,$ (3.26)

where $\gamma(t):=\exp_{x}t\overline{u}$.

###### Proof.

From $\overline{u}^{+}=-Hf_{\gamma(1)}^{-1}Df_{\gamma(1)}$, it holds
$\delta_{\gamma,1}^{-1}\overline{u}^{+}=-Hf_{\gamma(0)}^{-1}\tau^{*}_{\gamma,1}Hf_{\gamma(1)}Hf_{\gamma(1)}^{-1}Df_{\gamma(1)}=-Hf_{\gamma(0)}^{-1}\tau^{*}_{\gamma,1}Df_{\gamma(1)}$.
Here $\tau^{*}_{\gamma,1}Df_{\gamma(1)}$ is written as

$\tau_{\gamma,1}^{*}Df_{x^{+}}=Df_{x}(\cdot)+\int_{0}^{1}\frac{\rm d}{{\rm
d}t}Df_{\gamma(t)}(\tau_{\gamma,t}(\cdot)){\rm
d}t=-Hf_{x}(\overline{u},\cdot)+\int_{0}^{1}Hf_{\gamma(t)}(\tau_{\gamma,t}\overline{u},\tau_{\gamma,t}(\cdot)){\rm
d}t.$

Applying $-Hf_{\gamma(0)}^{-1}$, we have (3.26). ∎

###### Proof of Theorem 3.9.

Let $\lambda:=\lambda_{f}(x)$. Then $x^{+}\in C$ follows from Proposition 3.13
(1) and $\lambda_{f}(x)=\|\overline{u}\|<1/\sigma$. By Proposition 3.8 (2), we
have

$\lambda_{f}(x^{+})=\|\overline{u}^{+}\|_{f,x^{+}}\leq\frac{1}{1-\sigma\lambda}\|\delta_{\gamma,1}^{-1}\overline{u}^{+}\|_{f,x}.$
(3.27)

Let $K:T_{x}\to T_{x}$ denote the symmetric linear transformation defined by

$Ku:=u-\int_{0}^{1}\delta_{\gamma,t}^{-1}\tau_{\gamma,t}u{\rm d}t.$

By the above lemma, it holds
$\delta_{\gamma,1}^{-1}\overline{u}^{+}=K\overline{u}$. By Proposition 3.8 (1)
(and $\sigma\lambda<1$), the absolute value of each eigenvalue of $K$ is
bounded above by $(1-\sigma\lambda)^{-1}-1=\sigma\lambda/(1-\sigma\lambda)$.
Hence we have

$\|\delta_{\gamma,1}^{-1}\overline{u}^{+}\|_{f,x}=\|K\overline{u}\|_{f,x}\leq\|K\|_{\rm
op}\|\overline{u}\|_{f,x}\leq\frac{\sigma\lambda}{1-\sigma\lambda}\lambda,$
(3.28)

where $\|K\|_{\rm op}:=\sup_{u\in T_{x},u\neq 0}\|Ku\|_{f,x}/\|u\|_{f,x}$
denotes the operator norm of $K$. By (3.27) and (3.28), we have (3.25). ∎

Consider a scaled variant (damped Newton update) of the Newton update

$x\leftarrow x^{+}_{\rm
damp}:=\exp_{x}\frac{1}{1+\sigma\lambda_{f}(x)}\overline{u}.$ (3.29)

This guarantees global convergence, as in [16, Theorem 4.1.12]([17, Theorem
5.1.14]).

######  Proposition 3.11.

Suppose that $f$ is $\sigma$-WSC. It holds $x^{+}_{\rm damp}\in C$ and

$f(x^{+}_{\rm damp})\leq
f(x)-\frac{1}{\sigma^{2}}\omega(\sigma\lambda_{f}(x)).$ (3.30)

Thus, for given $x_{0}\in M$, the damped Newton update produces a point $x$
with $\lambda_{f}(x)<\beta/\sigma$ in
$O(\sigma^{2}(f(x_{0})-f^{*})/\omega(\beta))$ iterations.

###### Proof.

Let $\lambda:=\lambda_{f}(x)$. By
$\|\overline{u}/(1+\sigma\lambda)\|_{f,x}=\lambda/(1+\sigma\lambda)<1/\sigma$
and Proposition 3.4 (1), it holds $x_{\rm damp}^{+}\in C$. By Proposition 3.5,
we have

$\displaystyle f(x^{+}_{\rm damp})$ $\displaystyle\leq$ $\displaystyle
f(x)+\frac{1}{1+\sigma\lambda}Df_{x}(\overline{u})+\frac{1}{\sigma^{2}}\omega_{*}\left(\sigma\frac{\lambda}{1+\sigma\lambda}\right)$
$\displaystyle=$ $\displaystyle
f(x)-\frac{\lambda^{2}}{1+\sigma\lambda}+\frac{1}{\sigma^{2}}\omega_{*}\left(\sigma\frac{\lambda}{1+\sigma\lambda}\right)=f(x)-\frac{1}{\sigma^{2}}\omega(\sigma\lambda).$

∎

###  3.3 Self-concordant barrier

For $\nu>0$, a $\nu$-self-concordant barrier ($\nu$-SCB) of (the closure of)
$C$ is a $1$-SC function $F:C\to{\mathbb{R}}$ satisfying

$\sup_{u\in T_{x}}2DF(u)-HF(u,u)\leq\nu\quad(x\in M).$ (3.31)

By nondegeneracy of $F$, this condition is equivalent to

$DF(u)^{2}\leq\nu HF(u,u)\quad(u\in T_{x},x\in M).$ (3.32)

The following corresponds to [16, Theorem 4.2.2] ([17, Theorem 5.3.2]).

######  Lemma 3.12.

Let $F_{i}:C_{i}\to{\mathbb{R}}$ be a $\nu_{i}$-SCB for $i=1,2$. If $C_{1}\cap
C_{2}$ has nonempty interior, then $F_{1}+F_{2}:C_{1}\cap
C_{2}\to{\mathbb{R}}$ is a $(\nu_{1}+\nu_{2})$-SCB.

The proof is the same and is omitted. The next corresponds to [16, Theorem
4.2.4.1] ([17, Theorem 5.3.7.1]).

######  Proposition 3.13.

Let $F:C\to{\mathbb{R}}$ be a $\nu$-SCB. For any geodesic $\gamma:[0,1]\to C$,
it holds

$DF_{\gamma(0)}(\dot{\gamma}(0))<\nu.$ (3.33)

###### Proof.

We can assume that $DF_{\gamma(0)}(\dot{\gamma}(0))>0$. Define
$\phi:[0,1]\to{\mathbb{R}}$ by $t\mapsto DF_{\gamma(t)}(\dot{\gamma}(t))$. By
(3.32), it holds

$\phi^{\prime}(t)=HF_{\gamma(t)}(\dot{\gamma}(t),\dot{\gamma}(t))\geq(1/\nu)\phi(t)^{2}.$

In particular, $\phi$ is monotone increasing, and positive. Integrating
$\phi^{\prime}/\phi^{2}\geq 1/\nu$ from $0$ to $1$, we have

$-1/\phi(1)+1/\phi(0)\geq 1/\nu.$

Then $\phi(0)<\nu$, and we have (3.33). ∎

Instead of formulating other properties of SCB, we directly describe the path-
following method for minimization of an affine function on a compact convex
set. Here an affine function is a function $\ell$ such that it is an affine
function on every geodesic $\gamma$, i.e.,
$(\ell\circ\gamma)^{\prime\prime}(t)=0$. In a general manifold, nonconstant
affine functions are very rare. The main situation we think of is the
minimization of $(x,y)\mapsto c^{\top}y$ over $C\subseteq
M\times{\mathbb{R}}^{k}$; see Example 4.4.

Let $Q\subseteq M$ be a compact convex set such that its interior $Q^{\circ}$
is nonempty. For an affine function $\ell:Q\to{\mathbb{R}}$, consider the
following optimization problem:

$\mbox{Min.}\quad\ell(x)\quad{\rm s.t.}\quad x\in Q.$ (3.34)

We can assume that $\ell$ is not a constant function; then $D\ell_{x}\neq 0$
for all $x\in Q^{\circ}$. Let $\ell^{*}$ denote the minimum of $\ell(x)$ over
$x\in Q$.

Let $F:Q^{\circ}\to{\mathbb{R}}$ be a $\nu$-SCB of $Q$. Consider the
parametric problem with $t\geq 0$:

$\mbox{Min.}\quad f_{t}(x):=t\ell(x)+F(x)\quad{\rm s.t.}\quad x\in Q^{\circ}.$
(3.35)

Let $x^{*}(t)$ denote the minimizer of $f_{t}$. As in Euclidean case, the
curve $t\mapsto x^{*}(t)$ is called the central path, and the starting point
$x^{*}(0)$, the minimizer of $F$, is called the analytic center of $Q$
(relative to $F$). The path-following method can be formulated as in [16,
Section 4.2.4]:

Path-following method

Input:

A point $x_{0}\in Q^{\circ}$ with $\lambda_{F}(x_{0})\leq\beta$, where
$0<\beta<\frac{\sqrt{\beta}}{1+\sqrt{\beta}}$; say $\beta:=1/9$.

0:

$(x,t)\leftarrow(x_{0},0)$.

1:

$t^{+}:=t+\alpha/\|D\ell_{x}\|^{*}_{F,x}$, where
$\alpha:=\frac{\sqrt{\beta}}{1+\sqrt{\beta}}-\beta>0$.

2:

$x^{+}:=\exp_{x}\overline{u}$, where $\overline{u}$ is the Newton direction of
$f_{t^{+}}$ at $x$.

3:

$(x,t)\leftarrow(x^{+},t^{+})$; go to 1.

The initial point $x_{0}$ can be obtained by the damped Newton method. The
polynomial iteration complexity is obtained as in the Euclidean case:

######  Theorem 3.14.

Suppose that $\|(Df_{t})_{x}\|^{*}_{F,x}\leq\beta$. Then it holds

  * (1)

$\|(Df_{t^{+}})_{x^{+}}\|^{*}_{F,x^{+}}\leq\beta$.

In addition, if $t>0$, then it holds:

  * (2)

$\|D\ell_{x}\|^{*}_{F,x}\leq\frac{1}{t}(\beta+\sqrt{\nu})$; then
$t^{+}\geq\left(1+\frac{\gamma}{\beta+\sqrt{\nu}}\right)t$.

  * (3)

$\ell(x)-\ell^{*}\leq\frac{1}{t}\left(\nu+\frac{(\beta+\sqrt{\nu})\beta}{1-\beta}\right)$.

Thus, given $\epsilon>0$, the path-following method produces a point $x\in
Q^{\circ}$ with $\ell(x)-\ell^{*}\leq\epsilon$ in
$O(\sqrt{\nu}\log\nu\|D\ell_{x_{0}}\|^{*}_{F,x_{0}}/\epsilon)$ iterations.

###### Proof.

(1). Let $\lambda_{0}:=\|(Df_{t})_{x}\|_{F,x}^{*}\leq\beta$,
$\lambda_{1}:=\|(Df_{t^{+}})_{x}\|_{F,x}^{*}$ and
$\lambda^{+}:=\|(Df_{t^{+}})_{x^{+}}\|_{F,{x^{+}}}^{*}$. Then

$\lambda_{1}=\|\alpha
D\ell_{x}/\|D\ell_{x}\|_{F,x}^{*}+(Df_{t})_{x}\|_{F,x}^{*}\leq\alpha+\|(Df_{t})_{x}\|_{F,x}^{*}\leq\alpha+\beta=\frac{\sqrt{\beta}}{1+\sqrt{\beta}}<1.$

Here $f_{t}$ is $1$-SC for $t\geq 0$. By Theorem 3.9 (with
$\|(Df_{t^{+}})_{x}\|^{*}_{f_{t^{+}},x}=\lambda_{1}<1$), it holds

$\lambda^{+}\leq\left(\frac{\lambda_{1}}{1-\lambda_{1}}\right)^{2}\leq\left(\frac{\beta+\alpha}{1-\beta-\alpha}\right)^{2}=\beta.$

(2).
$\|D\ell_{x}\|^{*}_{F,x}=\frac{1}{t}\|(Df_{t})_{x}-DF_{x}\|^{*}_{F,x}\leq\frac{1}{t}(\|(Df_{t})_{x}\|_{F,x}^{*}+\|DF_{x}\|^{*}_{F,x})\leq\frac{1}{t}(\beta+\sqrt{\nu})$.

(3). Let $x^{*}$ be a minimizer of $\ell$ over $Q$, and $x^{*}(t)$ be the
unique minimizer of $f_{t}$ over $Q^{\circ}$. By the assumption of
$(M,\nabla)$, we can choose a geodesic $\gamma:[0,1]\to Q$ from $x^{*}(t)$ to
$x^{*}$. Since $\ell$ is an affine function and
$(Df_{t})_{x^{*}(t)}=tD\ell_{x^{*}(t)}+DF_{x^{*}(t)}=0$, we have

$\ell(x^{*}(t))-\ell(x^{*})=-D\ell_{x^{*}(t)}(\dot{\gamma}(0))=\frac{1}{t}DF_{x^{*}(t)}(\dot{\gamma}(0))\leq\frac{\nu}{t},$
(3.36)

where the last inequality follows from Proposition 3.13. Also, for geodesic
$c:[0,1]\to Q$ connecting $c(0)=x$ and $c(1)=x^{*}(t)$, we have

$t(\ell(x)-\ell(x^{*}(t)))=-tD\ell_{x}(\dot{c}(0))\leq
t\|D\ell_{x}\|^{*}_{F,x}\|\dot{c}(0)\|_{F,x}\leq(\beta+\sqrt{\nu})\frac{\beta}{1-\beta}.$
(3.37)

For the last inequality, we use $\|\dot{c}(0)\|_{F,x}\leq\beta/(1-\beta)$,
which can be seen as follows. By (3.10) with $(Df_{t})_{x^{*}(t)}=0$ and
Cauchy-Schwarz (2.4), it holds

$\frac{\|\dot{c}(0)\|^{2}_{F,x}}{1+\|\dot{c}(0)\|_{F,x}}\leq-(Df_{t})_{x}(\dot{c}(0))\leq\|(Df_{t})_{x}\|^{*}_{F,x}\|\dot{c}(0)\|_{F,x}\leq\beta\|\dot{c}(0)\|_{F,x}.$

By (3.36) and (3.37), we have (1). ∎

We finally examine construction of the logarithmic barrier. For a convex
function $f:M\to{\mathbb{R}}$ and $\beta\in{\mathbb{R}}$, the level set
$L_{f,\beta}\subseteq M$ is defined by

$L_{f,\beta}:=\\{x\in M\mid f(x)\leq\beta\\}.$ (3.38)

Denote by $L_{f,\beta}^{\circ}$ its interior. Define the logarithmic barrier
$F_{\beta}:L_{f,\beta}^{\circ}\to{\mathbb{R}}$ by

$F_{\beta}(x):=-\log(\beta-f(x))\quad(x\in L_{f,\beta}^{\circ}).$ (3.39)

######  Lemma 3.15.

$F=F_{\beta}$ is closed convex, and satisfies

$DF(u)^{2}\leq HF(u,u)\quad(u\in T_{x},x\in L_{f,\beta}^{\circ}).$ (3.40)

###### Proof.

Let $\omega:=\beta-f(x)>0$. Then we have

$DF(u)=\frac{Df(u)}{\omega},\quad
HF(u,u)=\frac{Hf(u,u)}{\omega}+\frac{Df(u)^{2}}{\omega^{2}}.$ (3.41)

Then $HF(u,u)\geq 0$ and hence $F$ is convex. Also $HF(u,u)\geq DF(u)^{2}$
holds. ∎

If a $\sigma$-SC function $F$ for $\sigma>0$ satisfies (3.40), then
$\sigma^{2}F$ is a $\sigma^{2}$-SCB. The following is a correspondent of [17,
Theorem 5.1.4].

######  Proposition 3.16.

Suppose that $f:M\to{\mathbb{R}}$ is $\sigma$-SC. Then
$F_{\beta}:L_{f,\beta}^{\circ}\to{\mathbb{R}}$ is $\tilde{\sigma}$-SC for

$\tilde{\sigma}:=\sqrt{(\sigma(\beta-f^{*})^{1/2}+1)^{2}+9/4},$

where $f^{*}:=\inf_{x\in M}f(x)$. In particular, $L_{f,\beta}$ admits an
$O(\sigma^{2}(\beta-f^{*}))$-SCB.

In the case of WSC, the constant $\tilde{\sigma}$ can be taken as
$\sqrt{\sigma^{2}(\beta-f^{*})+1}$, since precisely the same proof of [17,
Theorem 5.1.4] works. For the SC case, as in the proof of Lemma 3.2, a little
modification is required, which causes the increase of the constant.

###### Proof.

From (3.41), $Df(u)^{2}=(Df\otimes Df)(u,u)$, and $\nabla_{v}(Df\otimes
Df)(u,u)=(\nabla_{v}Df\otimes Df+Df\otimes\nabla_{v}Df)(u,u)=2Df(u)Hf(u,v)$
(see [24, II. Proposition 1.3 (1)]), the covariant derivative of $HF$ is given
by

$\nabla_{v}HF(u,u)=\frac{\nabla_{v}Hf(u,u)}{\omega}+\frac{Df(v)Hf(u,u)}{\omega^{2}}+\frac{2Df(u)Hf(u,v)}{\omega^{2}}+\frac{2Df(v)Df(u)^{2}}{\omega^{3}}.$
(3.42)

Hence we have

$\displaystyle|\nabla_{v}HF(u,u)|$ $\displaystyle\leq$
$\displaystyle\frac{2\sigma
Hf(v,v)^{1/2}Hf(u,u)}{\omega}+\frac{|Df(v)|Hf(u,u)}{\omega^{2}}$
$\displaystyle+\frac{2|Df(u)|Hf(v,v)^{1/2}Hf(u,u)^{1/2}}{\omega^{2}}+\frac{2|Df(v)|Df(u)^{2}}{\omega^{3}}.$

Define $\tau_{1},\tau,\xi_{1},\xi$ by

$\tau_{1}:=(Hf(v,v)/\omega)^{1/2},\ \tau:=(Hf(u,u)/\omega)^{1/2},\
\xi_{1}:=|Df(v)|/\omega,\ \xi:=|Df(u)|/\omega.$

Then we have

$\frac{|\nabla_{v}HF(u,u)|}{2HF(v,v)^{1/2}HF(u,u)}\leq\frac{\sigma\omega^{1/2}\tau_{1}\tau^{2}+(1/2)\xi_{1}\tau^{2}+\xi\tau_{1}\tau+\xi_{1}\xi^{2}}{(\tau_{1}^{2}+\xi_{1}^{2})^{1/2}(\tau^{2}+\xi^{2})}.$
(3.43)

We bound the RHS. By homogeneity, we may consider the optimization problem:

$\mbox{Max.}\quad\sigma\omega^{1/2}\tau_{1}\tau^{2}+(1/2)\xi_{1}\tau^{2}+\xi\tau_{1}\tau+\xi_{1}\xi^{2}\quad\mbox{s.t.}\quad\tau_{1}^{2}+\xi_{1}^{2}=1,\
\tau^{2}+\xi^{2}=1.$

Fixing $(\tau,\xi)$, optimize $(\tau_{1},\xi_{1})$, which is a linear
optimization over the unit circle. The optimum is
$(\sigma\omega^{1/2}\tau^{2}+\xi\tau,(1/2)\tau^{2}+\xi^{2})/\sqrt{(\sigma\omega^{1/2}\tau^{2}+\xi\tau)^{2}+((1/2)\tau^{2}+\xi^{2})^{2}}$.
Then we have

$\mbox{Max.}\quad\sqrt{(\sigma\omega^{1/2}\tau^{2}+\xi\tau)^{2}+((1/2)\tau^{2}+\xi^{2})^{2}}\quad\mbox{s.t.}\quad\tau^{2}+\xi^{2}=1.$

Therefore, the RHS of (3.43) is at most
$\sqrt{(\sigma\omega^{1/2}+1)^{2}+((1/2)+1)^{2}}$. ∎

##  4 Squared distance function

Let $M$ be a Riemannian manifold, where the inner product and norm on $T_{x}$
are denoted by $\langle,\rangle_{x}$ and $\|\cdot\|_{x}$, respectively. The
length of a curve $\gamma:[a,b]\to M$ is defined as
$\int_{a}^{b}\|\dot{\gamma}(t)\|_{\gamma(t)}dt$. The distance $d(x,y)$ between
two points $x,y$ is defined as the infimum of the length of a curve connecting
$x,y$. We consider the Levi-Civita connection $\nabla$. Then a minimum-length
curve is a geodesic with respect to $\nabla$. For a $2$-dimensional subspace
$F$ in $T_{x}$, the sectional curvature of $F$ is defined as $\langle
R(u,v)v,u\rangle_{x}$ where $\\{u,v\\}$ is an orthonormal basis of $F$.

Suppose that $M$ is an Hadamard manifold, i.e., it is complete, simply-
connected, and has nonpositive sectional curvature for every tangent plane at
every point. Then a geodesic connecting any two points is uniquely determined,
up to the choice of an affine parameter. The exponential map
$u\mapsto\exp_{x}u$ gives a diffeomorphism from $T_{x}$ to $M$. The distance
$d(x,y)$ coincides with the length of the unique geodesic between $x$ and $y$.
See [24, VI. Theorem 4.1].

Fix an arbitrary point $p\in M$. Define the distance and squared distance
functions $d_{p},f_{p}:M\to{\mathbb{R}}$ by

$d_{p}(x):=d(p,x),\quad f_{p}(x):=\frac{1}{2}d(p,x)^{2}\quad(x\in M).$

It is known [14, Lemma 12.15] that $f_{p}$ is smooth and $1$-strongly convex
(i.e.,$Hf_{p}(u,u)\geq\|u\|^{2}$ for $u\in T_{x},x\in M$), and hence
nondegenerate. Note that $d_{p}$ is also convex but nondifferentiable at $p$
and degenerate.

For exploring a nontrivial class of SC-functions, the first trial might be to
examine whether $f_{p}$ is SC or not. In this section, we show that $f_{p}$ is
SC for hyperbolic spaces. A hyperbolic space of curvature $-\kappa<0$ is an
Hadamard manifold such that every sectional curvature of every point is
constant $-\kappa$. The main result in this section is the following.

######  Theorem 4.1.

Suppose that $M$ is a hyperbolic space with curvature $-\kappa<0$, and let
$p\in M$.

  * (1)

$f_{p}$ is $\sqrt{\kappa}/2$-SC, and is not $(\sqrt{\kappa}/2-\epsilon)$-SC
for every small $\epsilon>0$.

  * (2)

$f_{p}$ is $\sqrt{4\kappa/27}$-WSC, and is not
$(\sqrt{4\kappa/27}-\epsilon)$-WSC for every small $\epsilon>0$.

Note that in the hyperboloid model ($\kappa=1$), the $\sqrt{4/27}$-WSC
property of $f_{p}$ is claimed in [10, Lemma 4] (without proof). It seems
reasonable to conjecture that $f_{p}$ is $\sqrt{\kappa}/2$-SC for any Hadamard
manifold having curvature lower bound $-\kappa$; it may be proved via
comparison theory.

As a consequence of Theorem 4.1 and Proposition 3.13, any ball in a hyperbolic
space admits an SCB. For $R>0$, let $B(p;R)^{\circ}:=\\{x\in M\mid
d(p,x)<R\\}$ be the open ball with center $p$ and radius $R$. let
$F_{p,R}:B(p;R)^{\circ}\to{\mathbb{R}}$ be defined by

$F_{p,R}(x):=-\log\left(R^{2}-d(p,x)^{2}\right)\quad(x\in M).$ (4.1)

######  Corollary 4.2.

Suppose that $M$ is a hyperbolic space with curvature $-\kappa<0$. Then
$F_{p,R}$ is $O(\sqrt{\kappa}R)$-SC. In particular, the open ball
$B(p;R)^{\circ}$ admits an $O(\kappa R^{2})$-SCB.

We show that the order $O(\sqrt{\kappa}R)$ cannot be improved. Define the
function $R\mapsto\sigma_{\kappa}(R)$ as the infimum of $\sigma$ for which
$F_{p,R}$ is $\sigma$-SC.

######  Proposition 4.3.

Suppose that $M$ is a hyperbolic space with curvature $-\kappa<0$. Then
$\sigma_{\kappa}(R)=\Omega(\sqrt{\kappa}R)$.

This may be a pity result. In the path-following method, for guaranteeing the
existence of the analytic center, we need to add a constraint to make the
feasible region bounded. A natural constraint is the distance constraint
$d(p,x)\leq R$. Then, adding the above barrier increases the barrier parameter
$\nu$ by $\Omega(\kappa R^{2})$, and the resulting iteration complexity of the
path-following method depends on $\sqrt{\kappa}R$.

In the Euclidean case, the logarithmic barrier of $f_{p}$ provides a $2$-SCB
for a ball of arbitrary diameter. Further, a general result of Nesterov and
Nemirovskii [18] says that every bounded convex set in ${\mathbb{R}}^{n}$
admits an $O(n)$-SCB. The above result may suggest the nonexistence of such an
SCB with constant independent of the size of diameter.

We provide one example to which the presented results are applicable.

######  Example 4.4 (Minimum enclosing ball in hyperbolic space [15]).

The minimum enclosing ball problem (MEB) on a manifold $M$ is: Given distinct
points $p_{1},p_{2},\ldots,p_{m}$ in $M$, find the smallest ball including
them. MEB is a nonsmooth optimization problem:

$\mbox{Min.}\quad r\quad{\rm s.t.}\quad(x,r)\in M\times{\mathbb{R}},\
d(p_{i},x)\leq r\ (i=1,2,\ldots,m).$ (4.2)

In the case of Euclidean space $M={\mathbb{R}}^{n}$, MEB is a well-studied
problem in computational geometry, and can be formulated by second-order cone
program to which an interior-point method is applicable; see e.g., [13].

We here assume that $M$ is a $d$-dimensional hyperbolic space with curvature
$-\kappa$. This case is addressed by Nielsen and Hadjeres [15]. We may further
assume $\kappa=1$ (see below). Let $r^{*}$ denote the optimal value of MEB.
Let $R:=2\max_{1\leq i<j\leq m}d(p_{i},p_{j})$. Clearly $r^{*}<R$. So we may
add constraint $r^{*}\leq R$ to make the feasible region bounded. For applying
our framework, we consider the following equivalent formulation:

$\mbox{Min.}\quad s\quad{\rm s.t.}\quad(x,s)\in M\times{\mathbb{R}},\
d(p_{i},x)^{2}\leq s\leq R^{2}\ (i=1,2,\ldots,m).$ (4.3)

Consider the following barrier

$F(x,s):=-\sum_{i=1}^{m}K^{2}\log(s-d(p_{i},x)^{2})-\log(R^{2}-s),$ (4.4)

where $K=\sqrt{2^{-1/2}(R+1)^{2}+9/4}$. By Theorem 4.1, $(s,x)\mapsto
d(p_{i},x)^{2}-s$ is (degenerate) $2^{-1/2}$-SC. The proof of Proposition 3.16
implies that $(s,x)\mapsto\log(s-d(p_{i},x)^{2})$ satisfies (3.1) with
$\sigma=K$ if $d(p_{i},x)^{2}\leq s\leq R^{2}$. The last term of $F$ is a
well-known $1$-SCB. With Lemmas 3.2 and 3.12, we conclude that $F$ is an
$O(mR^{2})$-SCB for the problem (4.3).

By the damped Newton method with starting point $(p_{i},R^{2}/2)$ (say), we
obtain the next starting point $(x_{0},s_{0})$ in $O(mR^{2}\log R)$
iterations. Given $\epsilon>0$, by the path-following method with starting
point $(x_{0},s_{0})$ and accuracy $\epsilon^{\prime}:=\epsilon/\min_{1\leq
i<j\leq m}d(p_{i},p_{j})$, we obtain an additive $\epsilon$-approximation
solution $(x,\sqrt{s})$ of MEB with
$\sqrt{s}-r^{*}\leq\epsilon^{\prime}/(\sqrt{s}+r^{*})\leq\epsilon$ in
$O(m^{1/2}R\log mR\alpha_{0}/\epsilon)$ iterations, where
$\alpha_{0}:=\|(0,1)\|^{*}_{F,s_{0}}$. The total number of Newton iterations
is $O(mR^{2}\log R+m^{1/2}R\log mR\alpha_{0}/\epsilon)$. Although the
dependence of $R$ is disappointing, it seems the first $\log
1/\epsilon$-dependence algorithm to this problem. As far as we know, the only
known algorithm having explicit complexity is an $O(dm/\epsilon^{2})$-time
$(1+\epsilon)$-approximation due to Nielsen and Hadjeres [15].

The rest of this section is devoted to proving Theorem 4.1 and Proposition
4.3. Although there are several models of hyperbolic space in which explicit
computation can be performed, we do not take such an approach and take a
“model-free” approach based on Jacobi fields.

For a geodesic $\gamma:[0,l]\to M$, a Jacobi field along $\gamma$ is a vector
field $X=(X(t))_{t\in[0,l]}$, where $X(t)\in T_{\gamma(t)}$, satisfying the
Jacobi equation

$\nabla_{\dot{\gamma}(t)}\nabla_{\dot{\gamma}(t)}X(t)+R(X(t),\dot{\gamma}(t))\dot{\gamma}(t)=0\quad(t\in[0,l]).$
(4.5)

This is a linear differential equation. Then, the solution $X(t)$ is uniquely
determined under the initial values $X(0),\nabla_{\dot{\gamma}(0)}X(0)$, or
under boundary values $X(0),X(l)$.

######  Lemma 4.5 (see [24, p.35, 36]).

Let $\alpha:[0,l]\times(-\epsilon,\epsilon)\to M$ be a smooth map such that
the curve $t\mapsto\alpha(t,s)$ is a geodesic for each
$s\in(-\epsilon,\epsilon)$. Then $D\alpha(t,0)(\frac{\partial}{\partial s})$
is a Jacobi field along geodesic $t\mapsto\alpha(t,0)$.

The Hessian of $f=f_{p}$ is given as follows. Recall distance function
$d=d_{p}:M\to{\mathbb{R}}$.

######  Lemma 4.6 (see [24, p.108–110]).

Let $x\in M$ with $p\neq x$, and let $\gamma:[0,l]\to M$ be a geodesic with
$\gamma(0)=p$, $\gamma(l)=x$, and $l=d(p,x)$. For $u\in T_{x}$, it holds

  * (1)

$Dd(u)=\langle\dot{\gamma}(l),u\rangle$.

  * (2)

$Df(u)=d(p,x)\langle\dot{\gamma}(l),u\rangle$.

  * (3)

$Hf(u,u)=d(p,x)\langle\nabla_{\dot{\gamma}(l)}X(l),u\rangle$, where $X$ is the
Jacobi field along $\gamma$ under the boundary condition

$X(0)=0,\quad X(l)=u.$

Suppose that $M$ is a hyperbolic space with curvature $-\kappa<0$. It is known
[24, II. Lemma 3.3] that the curvature tensor $R$ is written as

$R(X,Y)Z=-\kappa(\langle Y,Z\rangle X-\langle X,Z\rangle Y),$ (4.6)

from which solutions of the Jacobi equation are explicitly written.

For a positive real $\alpha>0$, consider the change of metric
$\langle,\rangle\to\alpha\langle,\rangle$. The distance $d$ changes as
$d\to\sqrt{\alpha}d$. The Levi-Civita connection $\nabla$ and curvature tensor
$R$ do not change. The sectional curvature $-\kappa$ changes as
$-\kappa\to-\kappa/\alpha$. Therefore, by changing metric, we may assume

$\kappa=1.$ (4.7)

This normalization is for simplicity of the equations we will compute.

######  Lemma 4.7.

Let $x\in M$ with $x\neq p$ and let $\gamma:[0,l]\to M$ be the geodesic from
$p$ to $x$ with $l=d(p,x)$. Then it holds

$\displaystyle Hf(u,u)$ $\displaystyle=$ $\displaystyle(l\coth l)\left(\langle
u,u\rangle-\langle u,\dot{\gamma}(l)\rangle^{2}\right)+\langle
u,\dot{\gamma}(l)\rangle^{2},$ (4.8) $\displaystyle\nabla_{v}Hf(u,u)$
$\displaystyle=$ $\displaystyle\Phi(l)\langle
v,\dot{\gamma}(l)\rangle\left(\langle u,u\rangle-\langle
u,\dot{\gamma}(l)\rangle^{2}\right)$ (4.9)
$\displaystyle+2\left(l-\Phi(l)\right)\langle
u,\dot{\gamma}(l)\rangle\left(\langle v,\dot{\gamma}(l)\rangle\langle
u,\dot{\gamma}(l)\rangle-\langle u,v\rangle\right),$

where $\Phi:{\mathbb{R}}\to{\mathbb{R}}$ is defined by

$\Phi(z):=(z\coth z)^{\prime}=\coth z+z-z\coth^{2}z.$

Explicit computation of Jacobi fields and the Hessian $Hf(u,u)$ in a
hyperbolic space can be found in several textbooks; see e.g., [24, p. 136, p.
154]. We include it for computation of $\nabla_{v}Hf(u,u)$.

###### Proof.

We explicitly compute the Jacobi field $X=(X(t))_{t\in[0,l]}$ along $\gamma$,
under boundary condition $X(0)=0$, $X(l)=u$, where [24, p.136] has similar
computation we consult. Decompose $X(t)$ as

$X(t)=\tilde{X}(t)+b(t)\dot{\gamma}(t),$

where $b(t):=\langle X(t),\dot{\gamma}(t)\rangle$ and
$\tilde{X}(t):=X(t)-b(t)\dot{\gamma}(t)$. Namely $\tilde{X}(t)$ is the
component of $X(t)$ orthogonal to $\dot{\gamma}(t)$. By (4.6), it holds
$R(X(t),\dot{\gamma}(t))\dot{\gamma}(t)=-(\langle\dot{\gamma}(t),\dot{\gamma}(t)\rangle
X(t)-\langle\dot{\gamma}(t),X(t)\rangle\dot{\gamma}(t))=-\tilde{X}(t)$, where
$\langle\dot{\gamma}(t),\dot{\gamma}(t)\rangle=1$ by $l=d(p,x)$. Parallel
transports of $\tilde{X}(t)$ along $\gamma$ keep orthogonal to the tangent
direction of $\gamma$. From this fact, the Jacobi equation is decomposed as

${b}^{\prime\prime}(t)=0,\quad\nabla_{\dot{\gamma}(t)}\nabla_{\dot{\gamma}(t)}\tilde{X}(t)-\tilde{X}(t)=0.$

Represent $\tilde{X}(t)=\sum_{i}\alpha_{i}(t)\tau_{\gamma,t}e_{i}$, where
$\\{e_{i}\\}$ is a basis of the subspace of $T_{\dot{\gamma}(0)}$ orthogonal
to $\dot{\gamma}(0)$. Then the second equation becomes
$\alpha_{i}^{\prime\prime}(t)-\alpha_{i}(t)=0$. Thus we obtain

$b(t)=b(0)+b^{\prime}(0)t,\quad\tilde{X}(t)=(\cosh
t)\tau_{\gamma,t}\tilde{X}(0)+(\sinh
t)\tau_{\gamma,t}\nabla_{\dot{\gamma}(0)}\tilde{X}(0).$

Consider the boundary condition $X(0)=0$ and $X(l)=u$. By $X(0)=0$, it must
hold $\tilde{X}(0)=0$ and $b(0)=0$. Since
$\tau_{\gamma,l}\nabla_{\dot{\gamma}(0)}\tilde{X}(0)$ is orthogonal to
$\dot{\gamma}(l)=\tau_{\gamma,l}\dot{\gamma}(0)$,
$X(l)=b^{\prime}(0)l\dot{\gamma}(l)+(\sinh
l)\tau_{\gamma,t}\nabla_{\dot{\gamma}(0)}\tilde{X}(0)=u$ implies

$b^{\prime}(0)=\langle
u,\dot{\gamma}(l)\rangle/l,\quad\tau_{\gamma,l}\nabla_{\dot{\gamma}(0)}\tilde{X}(0)=(u-\dot{\gamma}(l)\langle
u,\dot{\gamma}(l)\rangle)/\sinh l.$

Then $\nabla_{\dot{\gamma}(l)}X(l)$ is given by

$\nabla_{\dot{\gamma}(l)}X(l)=\dot{\gamma}(l)\langle
u,\dot{\gamma}(l)\rangle/l+\ (\coth l)(u-\dot{\gamma}(l)\langle
u,\dot{\gamma}(l)\rangle).$ (4.10)

Apply Lemma 4.6 (3) to obtain (4.8).

Consider the geodesic $s\mapsto c(s):=\exp_{x}sv$. Let $\gamma_{s}:[0,l]\to M$
be the geodesic from $p$ to $c(s)$ (not parametrized by the arc-length). For
$s\in(-\epsilon,\epsilon)$, let $l_{s}:=d(p,c(s))$ and $u_{s}:=\tau_{c,s}u$.
By (4.8) with reparametrized geodesic $t\mapsto\gamma_{s}((l/l_{s})t)$
$(t\in[0,l_{s}])$, we have

$(Hf)_{c(s)}(u_{s},u_{s})=(l_{s}\coth l_{s})\langle
u_{s},u_{s}\rangle+\left(1-l_{s}\coth l_{s}\right)(l/l_{s})^{2}\langle
u_{s},\dot{\gamma}_{s}(l)\rangle^{2}.$ (4.11)

By (2.5), the covariant derivative $\nabla_{v}Hf(u,u)$ is obtained by
computing $\partial_{s\to 0}:=d/ds\mid_{s\to 0}$ of (4.11). We use

$\partial_{s\to 0}l_{s}=\langle\dot{\gamma}(l),v\rangle,\quad\partial_{s\to
0}\langle u_{s},u_{s}\rangle=0,\quad\partial_{s\to 0}\langle
u_{s},\dot{\gamma}_{s}(l)\rangle=\langle
u,\left.\nabla_{\dot{c}(s)}\dot{\gamma}_{s}(l)\right|_{s\to 0}\rangle,$

where the first one follows from Lemma 4.6 (1) and the other follow from
$X\langle Y,Z\rangle=\langle\nabla_{X}Y,Z\rangle+\langle Y,\nabla_{X}Z\rangle$
and $\nabla_{\dot{c}(s)}u_{s}=0$. Hence we have

$\displaystyle\nabla_{v}f(u,u)$ $\displaystyle=$
$\displaystyle\Phi(l)\langle\dot{\gamma}(l),v\rangle\langle
u,u\rangle+\left(-\Phi(l)-2/l+2\coth
l\right)\langle\dot{\gamma}(l),v\rangle\langle u,\dot{\gamma}(l)\rangle^{2}$
$\displaystyle+2\left(1-l\coth l\right)\langle u,\dot{\gamma}(l)\rangle\langle
u,\left.\nabla_{\dot{c}(s)}\dot{\gamma}_{s}(l)\right|_{s\to 0}\rangle.$
$\displaystyle=$ $\displaystyle\Phi(l)\langle\dot{\gamma}(l),v\rangle(\langle
u,u\rangle-\langle u,\dot{\gamma}(l)\rangle^{2})$
$\displaystyle+2\left(1-l\coth l\right)\langle
u,\dot{\gamma}(l)\rangle(\langle
u,\left.\nabla_{\dot{c}(s)}\dot{\gamma}_{s}(l)\right|_{s\to 0}\rangle-\langle
v,\dot{\gamma}(l)\rangle\langle u,\dot{\gamma}(l)\rangle/l).$

To compute $\nabla_{\dot{c}(s)}\dot{\gamma}_{s}(l)|_{s\to 0}$, consider the
(smooth) map $\alpha:[0,l]\times(-\epsilon,\epsilon)\to M$ such that
$(t,s)\mapsto\gamma_{s}(t)$. Let $\frac{\partial\alpha}{\partial
s}(t,s):=D\alpha(t,s)(\frac{\partial}{\partial t})$ and
$\frac{\partial\alpha}{\partial t}(t,s):=D\alpha(t,s)(\frac{\partial}{\partial
s})$. Then $\left.\nabla_{\dot{c}(s)}\dot{\gamma}_{s}(l)\right|_{s\to
0}=\nabla_{\frac{\partial\alpha}{\partial s}}\frac{\partial\alpha}{\partial
t}(l,0)=\nabla_{\frac{\partial\alpha}{\partial
t}}\frac{\partial\alpha}{\partial s}(l,0)$, since
$\nabla_{\frac{\partial\alpha}{\partial s}}\frac{\partial\alpha}{\partial
t}=\nabla_{\frac{\partial\alpha}{\partial t}}\frac{\partial\alpha}{\partial
s}+[\frac{\partial\alpha}{\partial s},\frac{\partial\alpha}{\partial t}]$ and
$[\frac{\partial\alpha}{\partial s},\frac{\partial\alpha}{\partial
t}]=D\alpha([\frac{\partial}{\partial s},\frac{\partial}{\partial t}])=0$; see
[24, II. Lemma 2.2]. By Lemma 4.5, $Y(t):=\frac{\partial\alpha}{\partial
s}(t,0)$ is a Jacobi field along the geodesic $\gamma$, and satisfies $Y(0)=0$
and $Y(l)=v$. By (4.10), it holds

$\left.\nabla_{\dot{c}(s)}\dot{\gamma}_{s}(l)\right|_{s\to
0}=\nabla_{\dot{\gamma}(l)}Y(l)=\dot{\gamma}(l)\langle
v,\dot{\gamma}(l)\rangle/l+(\coth l)(v-\dot{\gamma}(l)\langle
v,\dot{\gamma}(l)\rangle).$

By substituting it, we obtain (4.14). ∎

#### Proof of Theorem 4.1.

We are going to bound

$\sigma_{x}(u,v):=\frac{|\nabla_{v}Hf(u,u)|}{2Hf(v,v)^{1/2}Hf(u,u)}\quad(u,v\in
T_{x}).$

From $d(p,x)=l$, it holds $\|\dot{\gamma}(l)\|=1$. We can also assume that
$\|u\|=\|v\|=1$. Therefore, $u,v,\dot{\gamma}(l)$ can be assumed unit vectors
in ${\mathbb{R}}^{3}$ and represented in the spherical coordinate system as
$\dot{\gamma}(l)=(0,0,1)$, $u=(\sin\theta,0,\cos\theta)$,
$v=(\sin\varphi\cos\alpha,\sin\varphi\sin\alpha,\cos\varphi)$ for
$\theta,\varphi\in[0,\pi]$ and $\alpha\in[0,2\pi]$. By Lemma 4.7, we have

$\displaystyle Hf(v,v)$ $\displaystyle=$ $\displaystyle\cos^{2}\varphi+(l\coth
l)\sin^{2}\varphi,$ (4.12) $\displaystyle Hf(u,u)$ $\displaystyle=$
$\displaystyle\cos^{2}\theta+(l\coth l)\sin^{2}\theta,$ (4.13)
$\displaystyle\nabla_{v}Hf(u,u)$ $\displaystyle=$
$\displaystyle\Phi(l)\cos\varphi\sin^{2}\theta+2\left(l-\Phi(l)\right)\cos\theta\sin\varphi\sin\theta(-\cos\alpha).$
(4.14)

By elementary calculus111Use $\sinh z=z+(1/3!)z^{3}+\cdots$ and $\cosh
z=z^{2}+(1/4!)z^{4}+\cdots$ to show $\lim_{z\to 0}z\coth z=1$ and
$\Phi(0)=0\leq\Phi^{\prime}(z)$ for $z\geq 0$, we see

$0\leq\Phi(z)\leq\min(1,z)\quad(z\in[0,\infty)).$ (4.15)

In (4.14), the quantities $\Phi(l)$, $l-\Phi(l)$, $\sin\theta$, and
$\sin\varphi$ are all nonnegative. Thus

$|\nabla_{v}Hf(u,u)|\leq\Phi(l)|\cos\varphi|\sin^{2}\theta+2\left(l-\Phi(l)\right)\sin\varphi\sin\theta|\cos\theta|.$
(4.16)

For $C:=l\coth l\geq 1$, observe

$\displaystyle\max_{\phi\in[0,\pi]}\frac{|\cos\phi|}{\sqrt{\cos^{2}\phi+C\sin^{2}\phi}}=1,\quad\max_{\phi\in[0,\pi]}\frac{\sin\phi}{\sqrt{\cos^{2}\phi+C\sin^{2}\phi}}=\frac{1}{\sqrt{C}},$
$\displaystyle\max_{\theta\in[0,\pi]}\frac{\sin\theta|\cos\theta|}{\cos^{2}\theta+C\sin^{2}\theta}=\max_{\theta\in[0,\pi]}\frac{|\tan\theta|}{1+C\tan^{2}\theta}=\max_{z\in[0,\infty)}\frac{z}{1+Cz^{2}}=\frac{1}{2\sqrt{C}}.$

Then

$\displaystyle\sigma_{x}(u,v)$ $\displaystyle\leq$
$\displaystyle\max_{\varphi,\theta\in[0,\pi]}\frac{\Phi(l)|\cos\varphi|\sin^{2}\theta+2(l-\Phi(l))\sin\varphi\sin\theta|\cos\theta|}{2\sqrt{\cos^{2}\varphi+C\sin^{2}\varphi}\left(\cos^{2}\theta+C\sin^{2}\theta\right)}$
$\displaystyle\leq$ $\displaystyle\Phi(l)/2C+(l-\Phi(l))/2C=(\tanh l)/2\leq
1/2.$

Thus $f$ is $1/2$-SC.

Choose $\varphi=\pi/2$, $\tan^{2}\theta=1/C$, and $\alpha\in\\{0,\pi\\}$. From
(4.14) we have

$\sigma_{x}(u,v)=\frac{(l-\Phi(l))|\cos\theta|\sin\theta}{\sqrt{C}(\cos^{2}\theta+C\sin^{2}\theta)}=\frac{l-\Phi(l)}{2C}=(l-\Phi(l))\frac{\tanh
l}{2l}.$

For $l\to\infty$, it holds $\sigma_{x}(u,v)\to 1/2$. Hence the constant $1/2$
is tight. This completes the proof of (1).

Showing (2), we consider the case of $u=v$; then $\varphi=\theta$ and
$\alpha=0$. From (4.14), we have

$\nabla_{u}Hf(u,u)=(-2l+3\Phi(l))\cos\theta\sin^{2}\theta.$ (4.17)

Then we have

$\displaystyle\sup_{u\in
T_{x}}\sigma_{x}(u,u)=\max_{\theta\in[0,\pi/2]}\frac{|2l-3\Phi(l)|\tan^{2}\theta}{2(1+C\tan^{2}\theta)^{3/2}}=\max_{z\in[0,\infty)}\frac{|2l-3\Phi(l)|z}{2(1+Cz)^{3/2}}$
$\displaystyle=\frac{|2l-3(\coth
l+l-l\coth^{2}l)|}{\sqrt{27}C}=\frac{|-3/l-\tanh l+3\coth l|}{\sqrt{27}},$

where the maximum of $z/(1+Cz)^{3/2}$ is attained at $z=2/C=2(\tanh l)/l$. The
supremum of the last quantity is attained at $l\to\infty$, and equals
$2/\sqrt{27}$. This means that $f$ is $\sqrt{4/27}$-WSC, tightly.

By recovering the normalization $f\to(1/\kappa)f$, we obtain tight
$\sqrt{\kappa}/2$-SC and $\sqrt{4\kappa/27}$-WSC properties of the original
$f$.

#### Proof of Proposition 4.3.

Let $x\in B_{p,R}^{\circ}$. We bound $\sigma_{x}(u,u)$ from below. We use the
notation $l,\theta$ in the previous proof. Let $\omega=\omega_{p,R,x}$ be
defined by $\omega:=R^{2}/2-d(p,x)^{2}/2=R^{2}/2-f(x).$ By (3.41), Lemma 4.6
(2), and (4.13), we have

$\displaystyle DF(u)$ $\displaystyle=$
$\displaystyle\frac{l\cos\theta}{\omega},$ $\displaystyle HF(u,u)$
$\displaystyle=$ $\displaystyle\frac{1}{\omega}\left(\cos^{2}\theta+l\coth
l\sin^{2}\theta\right)+\frac{l^{2}}{\omega^{2}}\cos^{2}\theta$
$\displaystyle=$
$\displaystyle\frac{\omega+l^{2}}{\omega^{2}}\left(\cos^{2}\theta+\left(\frac{\omega}{\omega+l^{2}}\right)l\coth
l\sin^{2}\theta\right).$

With (3.42) for $u=v$ and (4.17), we have

$\nabla_{u}HF(u,u)=\frac{-2l+3\Phi(l)}{\omega}\cos\theta\sin^{2}\theta+\frac{3l}{\omega^{2}}\cos\theta(\cos^{2}\theta+l\coth
l\sin^{2}\theta)+\frac{2l^{3}}{\omega^{3}}\cos^{3}\theta.$

Take $\theta$ so that
$\tan^{2}\theta=\left(\frac{\omega+l^{2}}{\omega}\right)\frac{\tanh l}{l}$
(say). Then $HF(u,u)=\frac{2(\omega+l^{2})}{\omega^{2}}\cos^{2}\theta$, and
$\sigma_{x}(u,u)$ is given by

$\displaystyle\frac{\omega^{3}}{2^{3/2}(\omega+l^{2})^{3/2}}\left|\frac{-2l+3\Phi(l)}{\omega}\left(\frac{\omega+l^{2}}{\omega}\right)\frac{\tanh
l}{l}\right.\left.+\frac{3l}{\omega^{2}}\left(\frac{\omega+l^{2}}{\omega}\right)+\left(\frac{3l}{\omega^{2}}+\frac{2l^{3}}{\omega^{3}}\right)\right|$
$\displaystyle\geq\frac{\omega}{2^{3/2}\sqrt{\omega+l^{2}}}\left|2\tanh
l-3\Phi(l)\frac{\tanh
l}{l}\right|-\frac{3l}{2^{3/2}\sqrt{\omega+l^{2}}}-\frac{3\omega
l+2l^{3}}{2^{3/2}(\omega+l^{2})^{3/2}}$
$\displaystyle\geq\frac{R^{2}-l^{2}}{4\sqrt{R^{2}+l^{2}}}\left|2\tanh
l-3\Phi(l)\frac{\tanh l}{l}\right|-\frac{5}{2^{3/2}},$

where $l/\sqrt{\omega+l^{2}}\leq 1$ and $(3\omega
l+2l^{3})/(\omega+l^{2})^{3/2}=2(1+(3/2)\alpha)/(1+\alpha)^{3/2}\leq 2$ for
$\alpha=\omega/l^{2}$ (see [16, p. 177]). Take $x$ such that
$d(p,x)^{2}=l^{2}=R^{2}/2$ (say). For $R\to\infty$, the absolute value
$|\cdot|$ converges to $2$, and hence it holds $\sigma_{x}(u,u)=\Omega(R)$.

## Acknowledgments

The author was supported by JST PRESTO Grant Number JPMJPR192A, Japan.

## References

  * [1] P. A. Absil, R. Mahony, R. Sepulchre: Optimization Algorithms on Matrix Manifolds. Princeton University Press, Princeton, NJ, 2008.
  * [2] Z. Allen-Zhu, A. Garg, Y. Li, R. Oliveira: and A. Wigderson, Operator scaling via geodesically convex optimization, invariant theory and polynomial identity testing. arXiv:1804.01076, 2018. (the conference version in STOC 2018)
  * [3] S. Amari and K. Nagaoka: Methods of Information Geometry. American Mathematical Society, Providence, RI, 2000.
  * [4] N. Boumal: An Introduction to Optimization on Smooth Manifolds. Cambridge University Press, Cambridge, 2023 (to appear).
  * [5] P. Bürgisser, C. Franks, A. Garg, R. Oliveira, M. Walter, and A. Wigderson: Towards a theory of non-commutative optimization: geodesic first and second order methods for moment maps and polytopes. arXiv:1910.12375, 2019. (the conference version in FOCS 2019)
  * [6] P. Bürgisser, Y. Li, H. Nieuwboer, and M. Walter: Interior-point methods for unconstrained geometric programming and scaling problems. arXiv:2008.12110, 2020.
  * [7] C. Franks and P. Reichenbach: Barriers for recent methods in geodesic optimization. arXiv:2102.06652, 2021. (the conference version in CCC2021)
  * [8] A. Garg, L. Gurvits, R. Oliveira, and A. Wigderson, Operator scaling: theory and applications. Foundations of Computational Mathematics20 (2020),223–290
  * [9] H. Hirai: Convex analysis on Hadamard spaces and scaling problems. arXiv:2203.03193, 2022.
  * [10] H. Ji, J. H. Manton, and J. B. Moore: A globally convergent conjugate gradient method for minimizing self-concordant functions on Riemannian manifolds. IFAC Proceedings Volumes 41 (2008), 14313–14318.
  * [11] D. Jiang, J. B. Moore, H. Ji: Self-concordant functions for optimization on smooth manifolds. Journal of Global Optimization 38 (2007), 437–457.
  * [12] S. Kakihara, A. Ohara, T. Tsuchiya: Information geometry and interior-point algorithms in semidefinite programs and symmetric cone programs. Journal of Optimization Theory and Applications 157 (2013), 749–780.
  * [13] P. Kumar, J. S. B. Mitchel, and E. A. Yildirim: Approximate minimum enclosing balls in high dimensions using core-sets. ACM Journal of Experimental Algorithmics 8 2003, 1.1-es.
  * [14] J. M. Lee: Introduction to Riemannian Manifolds. Springer, Cham, 2018.
  * [15] F. Nielsen and G. Hadjeres: Approximating covering and minimum enclosing balls in hyperbolic geometry. Geometric Science of Information, Lecture Notes in Computer Science 9389 (2015), 586–594.
  * [16] Y. Nesterov: Introductory Lectures on Convex Optimization. A Basic Course. Kluwer Academic Publishers, Boston, MA, 2004.
  * [17] Y. Nesterov: Lectures on Convex Optimization. Springer, Cham, 2018.
  * [18] Y. Nesterov and A. Nemirovskii: Interior-Point Polynomial Algorithms in Convex Programming. SIAM, Philadelphia, PA, 1994.
  * [19] Y. Nesterov and M. J. Todd: On the Riemannian geometry defined by self-concordant barriers and interior-point methods. Foundations of Computational Mathematics 2 (2002), 333–361.
  * [20] K. Nomizu and T. Sasaki: Affine Differential Geometry. Geometry of Affine Immersions. Cambridge University Press, Cambridge, 1994.
  * [21] A. Ohara and A. Tsuchiya: An information geometric approach to polynomial-time interior-point algorithms: complexity bound via curvature Integral. Research Memorandum No.1055, The Institute of Statistical Mathematics, 2007.
  * [22] J. Renegar: A Mathematical View of Interior-Point Methods in Convex Optimization. SIAM, Philadelphia, PA, 2001.
  * [23] A. Rusciano: A Riemannian corollary of Helly’s theorem, Journal of Convex Analysis 27 (2020), 1261–1275.
  * [24] T. Sakai: Riemannian Geometry. American Mathematical Society, Providence, RI, 1996.
  * [25] H. Sato: Riemannian Optimization and Its Applications, Springer, Cham, 2021.
  * [26] H. Shima: The Geometry of Hessian Structures. World Scientific, Hackensack, NJ, 2007.
  * [27] M. Silva Louzeiro, R. Bergmann, and R. Herzog: Fenchel duality and a separation theorem on Hadamard manifolds, SIAM Journal on Optimization 32 (2022), 854–873.
  * [28] C. Udriste: Optimization methods on Riemannian manifolds. Algebras, Groups and Geometries 14 (1997), 339–358.