数理解析研究所講究録
1004 巻 1997 年 71-89

71

Information Geometric Analysis of a Interior-Point Method for
Semidefinite Programming.
大阪大学基礎工学部

1

小原敦美(Atsumi Ohara)

Introduction

Sillceproposed an interior point algorithm with polynomial-time complexity)
to solve lillear
problems [11], many works have contributed to theand applications of interior-point methods of nlathematical programming (Seefor sollle text books [16, 5. 21, 22] .
Among them, some researchers have brought differential geometric points of view andelucidated lllathelllatical structures behind the mechanisln of interior-point methodology[2, 12, 20. 8. 6].
In particular, (continuous version of) affine scaling trajectories in LP has been known
integrable via Legendre transformation and regarded as geodesics for a certain connection$[20, 6]$ . These results are crucially relying on several dualistic properties of the problem
and one of the key tool.unifying them has been so-called information geometry [1]. As forthe integrability of affine scaling trajectories. we should also refer to $[10_{\eta}4,15,7]$ .
On the other hand, recent study is developing the applicable area of Polynomial-time
interior-point framework to broader class of convex programming problems. One of thelllost significant in the engineering application is semidefinite programming (SDP), whichis actually useful in svstem and control theory [3] and combinatorial optimization [21].
Further, the set of positive definite matrices is one of the} where dualistic natureappears in the simplest way and is easy to analyze [18], e.g., Legendre transformation turns
out to be essentially matrix inversion. This fact implies that analyzing SDP enables us to
exploit abundant dualistic structure of interior-point methodology via direct calculations.
This paper first introduce preliminary results of information geometry in Section 2.
Section 3 discusses the interior-point machinery for the general convex programming interms of the frame work of information geometry. In this case, we again find that various
dualistic structure on a considering convex region, such as Legendre transformation, dual
connection and so on, naturally appear and play important roles. This part can be
regarded as a silnple extension of the work given by $[20, 6]$ in LP case.
Next, by examining the above results, we consider in Section 4 the possibility of a newalgorithm using Legendre transformation. Consequently, we show some class of nontrivial
problems ill SDP can be solved without any iterations. This class is characterized bygeometric term:-autoparallelism. Further this class turns out to be related to Jordan
subalgebra of symmetric matrices under a certain circumstance.
Finally in Section 5, we exploit the above result quantitatively, i.e., we show a certain
geometric quantities called the second fundamental form (, or Euler-Schouten enlbedding
curvature) is directly related to predictor step size we can take without increasing computational complexity in the succeeding corrector phase. This result shows one approach tohow over all computational complexity is dependent on structure of each problem
to be solved.
$\mathrm{I}_{\check{\mathrm{t}}\mathrm{a}1^{\backslash }\mathrm{n}\mathrm{u}}\mathrm{a}\mathrm{r}1_{\backslash }^{- \mathrm{a}}1$$1$$\mathrm{r}\mathrm{o}\mathrm{g}\mathrm{r}\mathrm{a}\mathrm{m}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{g}(\mathrm{L}\mathrm{P})$$1)1^{\cdot}\mathrm{o}\mathrm{g}\mathrm{r}\mathrm{e}\mathrm{S}\mathrm{s}$$)$$\mathrm{e}\mathrm{x}\mathrm{a}\mathrm{l}\mathrm{n}\mathrm{p}$$\nabla^{*}$$\mathrm{a}\mathrm{n}\mathrm{d}.\backslash ’ \mathrm{z}\mathrm{e}$$\mathrm{e}\mathrm{S}$72: the set of by real symmetric matrices, $PD(n)$ : the set of by
of the vector space $Sym(n)$ ,real positive definite.
: Kronelgar’s delta.
Further. we obey the following convention for the simplicity of notation:
Convention: When Super- or sub.scripts are used without any range, Italic letters$N$ . Similarly, the other Italic
are supposed to index integers from 1 to 1V, e.g., $p=1,$
to
and Greek super- or subscripts are respeCtivel.V supposed to index$N$ .
$i=1\ldots$
to.V,
,
.
and
e.g..
and from

Notation:$Sy’ ??(t\iota)$

$n$

$n$

$n$

$n$

$\mathrm{m}\mathrm{a}\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{c}\mathrm{e}\mathrm{s},$$\cdot.’.\cdot\backslash \cdot \mathrm{s}..\mathrm{i}\mathrm{o}\mathrm{n}$$N:\sim(=.|l=.\cdot:(|l+.1)/2)\mathrm{d}\mathrm{i}\mathrm{m}\mathrm{e}\mathrm{n}\backslash \backslash \cdot.\cdot:\overline{\backslash }$$\delta_{i}^{j}$$p,$ $q,$ $r$$\ldots,$$m$$\mathrm{i}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{g}_{P}\mathrm{e}\mathrm{r}\mathrm{S}\mathrm{f}\mathrm{r}\mathrm{o}\mathrm{m}\backslash \prime 1$$l?\mathrm{l}+1$$t\overline{\iota}=m+1,$$??\mathit{1}$$\ldots,$

Preliminaries for Information Geometry2

In this section. we give a brief introduction of some results in dualistic geometry to beails and further results
used in the following sections. Those who are interested in the
can refer to [1, 6, 18].
. One of the simplest way to define
be an arbitrary open convex set inLet
is using a convex potential function. As is shown in theinfolmation geometry on
followings. we can obtain key geometric quantities which define dualistic struct-ures
derivatives of the function.
that has positive definite Hessian
be any snlooth convex function onLet. Now consider a Riemannian manifold
is a coordinate system for
matrix. , where, i.e.,, whereRiemannian metric is given by the Hessian matrix ofde..t$\mathrm{R}^{m}$$\mathcal{M}$$\mathcal{M}$$\mathrm{a}.\mathrm{s}$:$\mathcal{M}$$l_{\vee}’(I)$$\mathrm{R}^{m}$$(x^{1})$$(\mathcal{M}.g)$$\psi(x)$$\mathrm{i}\mathrm{t}_{\mathrm{T}}\mathrm{s}$$g_{ij}(x):=\partial_{i}\partial_{j}\mathrm{t}’’(x)$, where$\partial_{i}:=\frac{\partial}{\partial x^{i}}$

(2.1)

.

represent the components of Riemannian lnetric .
HereNext we will introduce a pair of connections andon our Riemannian manifold. While in mathematical physics the Levi-Civita connection on Riemannian manifolds plays an important role. non-Levi-Civita connections are crucial in our frame work.
Let denote the components of and$g_{ij}(.r)$$g$$\nabla$$\nabla^{*}$$(\mathcal{M}, g)$$\nabla$$\nabla^{*}\mathrm{b}\backslash .\cdot$$\Gamma_{ijk}(.T)=g(\nabla_{\partial_{i}}\partial_{j}, \partial_{k}.)$.

$.\Gamma_{ijk(x}^{*}$and define these connections respectively by their,$\Gamma_{jj\lambda}.(X):=[ij:k](X)-.\frac{1}{2}T_{j}jk\cdot(.\mathrm{r})=0$)$=g(\nabla_{\partial j}^{*}:^{\partial,\partial_{k}})$$\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{p}\mathrm{o}\mathrm{n}\mathrm{e}\mathrm{n}\mathrm{t}|\mathrm{s}$

.

(2.2)

:

$\Gamma_{ijk}^{*}(x):=[ij;k](x)+\frac{1}{2}T_{ijk}(X)=T_{?jk}.(x)=\partial_{i}g_{jk}(x)$

.

(2.3)
Here,

$[ij\cdot, k]$represent the coluponents of the Riemannian (Levi-Civita).

$[ij:k,]:= \frac{1}{2}(\partial_{i/}(i_{j}k$$+\partial jg\kappa.i-\partial_{kJ)}c_{ij}$$\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{n}\mathrm{e}\mathrm{c}\mathrm{f}|\mathrm{i}\mathrm{o}\mathrm{n}$

:

.

and
$\tau_{ijk}(\backslash \tau):=\partial_{i}\partial j\partial k\psi(x)$

Since
not

$\Gamma_{jj\mathrm{A}}.(.\Gamma)=0$. the coordinate system
inlplies.

$\mathrm{n}\mathrm{l}\mathrm{e}\mathrm{t}\mathrm{r}\mathrm{l}\mathrm{C}-\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{e}\mathrm{r}\mathrm{l}r\dot{\mathrm{n}}\mathrm{l}\mathrm{g}$$x$is called

(2.4)

,

$\nabla$-affine. Although$\nabla$and$\nabla^{*}$are$(\mathit{2}.3)$$\partial_{i/\zeta_{jk}}=\Gamma_{ij\mathrm{A}}$.

$+\Gamma_{ikj}^{\mathrm{x}}\backslash$

’

i.e..

$\mathrm{s}4g(B, C)=g(\nabla_{A}B, c)+g(B, \nabla^{*}.{}_{4}C)$

(2.5)

73

\sim

for any vector fields -4, andmutually dual with respect to .
$B$

on

$C$

. Due to this property, we say$arrow$$- \mathcal{M}$$\nabla$and$\nabla^{*}$

are

$g$

Thus, we can easily derive the structure of information geometry$(\mathcal{M}, g, \nabla, \nabla^{*})$

from thepotential functionon .
In casedual connections
andare derived from a potential function in themanner of (2.3). it is known that torsion and curvature tensors on
with respect to. If this is the case, we call
anddually flat.
dually flat, we can introduce a new coordinate systenl
Whenand convex (withrespect to ) function $o(y)$ via Legendre transform:$\iota_{p}.!(x)$$\mathcal{M}$$\nabla^{*}$$\nabla$$\mathrm{t}_{(}\mathrm{h}\mathrm{a}\mathrm{t}$$\mathcal{M}$$\nabla$$\mathcal{M}$$\nabla^{*}\backslash \cdot \mathrm{a}\mathrm{n}\mathrm{i}\mathrm{s}\mathrm{h}$$\mathcal{M}$$(y_{i})$$y$$y_{7}\cdot:=\partial_{\mathrm{i}}\iota’(X)$.

$\phi(y):=\mathrm{t}^{j*}’(y)=\sup_{x\in.\mathrm{W}}\mathrm{t}x^{i}y_{i}-\psi(X)\}$

.

(2.6)

Note that we use subscripts for the components of . Let us define as
the components of Rielnannian metric and the dual connections andto are represented in the dual manner as, thenwith respect$\partial^{i}:=\partial/\partial y_{i}$$y$$\nabla$$g$$\nabla^{*}$

$y$

(2.7)

,

$x^{i}=\partial^{i}\emptyset(y)$$g^{ij}(y)=\partial^{i}\partial^{j}\phi(y)$$\Gamma^{ijk}(y)=\partial i\partial j\partial^{k}\mathit{0}-(y)$$\Gamma^{*ijk}(y)=0$,. is similarly calledSince-affine. Aof the transformation between and is just , i.e.,$\Gamma^{*\mathrm{i}jk}(y)=0$$\nabla^{*}$

$y$

$x$

$y$

(2.8)

,

$\mathrm{c}\mathrm{r}\mathrm{u}\mathrm{C}\mathrm{i}\mathrm{a}\mathrm{l}$

.

(2.9)

point is that Jacobian matrix$g$$\partial_{i}=g_{ij}\partial^{j},$$:\cdot\partial^{i}=g^{ij}\partial j$

and $(g_{ij}(x))$ is an inverse matrix ofat$p=p(x)=p(y)$ . Note that it follows fronl (2.10)$(g^{\uparrow j}(y))$$\mathrm{a}\mathrm{n}_{3^{r}}.$$g(\partial_{i}, \partial^{j})=\delta_{i}^{J}\sim$(2.10),

same.point.ed$\mathrm{s}_{\vee}\mathrm{p}\mathrm{e}\mathrm{c}\mathrm{i}\mathrm{f}\mathrm{i}$.

$\mathrm{b},\mathrm{y}x$

and

$y$

:

(2.11)

Finally. we should note that using theof the connections, we can represent
differential equations of their geodesics as follows: For a geodesic with respect to theconnection . we have$\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{p}_{\mathrm{o}\mathrm{n}\mathrm{e}}\mathrm{n}\mathrm{t}\mathrm{s}$$\nabla$.7$\mathrm{i}(t)=0$.

which are represented in andwithto the connection$\sum_{j=1}^{m}g^{i}jijj(t)+\sum_{1j.k=}^{\mathit{1}}\Gamma^{ij}ktn\dot{y}_{j}()\dot{y}k(t)=0$$y\mathrm{c}\mathrm{o}\mathrm{o}\mathrm{r}\dot{\mathrm{d}}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{t}\mathrm{e}$$x$$1^{\cdot}\mathrm{e}\mathrm{s}\mathrm{p}\mathrm{e}c\mathrm{f}$$\nabla^{*}$

system,$\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{p}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{i}\backslash r\mathrm{e}\mathrm{l}\mathrm{y}$,. imilarly for a geodesic$..\mathrm{S}$,$\sum_{j=1}^{-m}gij.\ddot{\tau}^{j}.(t)+\sum_{j,k=1}.\tau\kappa^{\dot{X}(}t)i^{*}j’\dot{x}^{k}mj(t)=0$Here. denotes derivative by the parameter .
$t$,$j\mathrm{i}_{r}(\dagger)--\mathrm{o}$.

743Some Interior Point Methods and Geodesics
of continuous trajectories associated with some (primal)interior point methods in terms of information geometry. Next, we discuss the possibilityof new algorithln based on this result.
, , consider the following$i=1,$and convex functions
Given a vector
objectivefunction:convex programming problem with a linear
Here, we show the$\mathrm{P}^{\mathrm{r}\mathrm{o}}\mathrm{P}^{\mathrm{e}\mathrm{r}\mathrm{t}}.\mathrm{v}$’$\min c^{T}x$ ,$h$$f_{i}(x),$$c\in \mathrm{R}^{\eta}$$\mathrm{s}.\mathrm{t}$.

$x\in \mathcal{M}\subset \mathrm{R}^{m},$$\ldots$$\mathcal{M}=\{x|fi(x)\leq 0, i=1, \ldots, h\}$ .

(3.1)

can transform general convex programming problems with arbitrary convex
Note that:
objective function$\backslash \backslash ^{-}\mathrm{e}$$f_{0}(X)$$1\mathrm{l}\dot{\mathrm{u}}\mathrm{n}f_{0}(X)$$\mathrm{t}\mathrm{o}\backslash$.

$\mathrm{s}.\mathrm{t}$.

$x\in \mathcal{M}\subset \mathrm{R}^{m},$ $\mathcal{M}=\{x|f\mathrm{i}(x)\leq

the the form (3.1). By introducing new variable$x^{?7l+1}$0, i=1, \ldots , h\}$(3.2)

and convex function(3.3)$f_{h+1}(X, x^{m})+1:=f_{0}(x)-X^{n\mathit{1}}+1$ ,we obtain the equivalent problem
lnin$X^{m+1}=c^{T}\tilde{x}$.

$c^{T}=[\mathrm{o}\ldots 1]$ ,$\tilde{\mathcal{M}}=\{_{\backslash }\mathrm{t}^{\backslash }\sim|fi(x)\leq 0.i=1, \ldots, h+1\}$,$.\tilde{\gamma j}\in\tilde{\mathcal{M}}\subset \mathrm{R}^{m+1}$$\tilde{x}^{T}=[xX^{m}]\tau+1$,$f_{i}(x)$,: convex,$i=0,$$\ldots$, $h+1$ .

Thus, we can regard (3.1) as one of standard forms for convex programming problems.

is bounded.
In this section. we will assumeforLet us consider a barrier function$\mathcal{M}$$\phi(x)$Bl)

is three imes$\dot{\mathrm{t}}$$\iota_{-}’’(X)$B2) Hessian matrix of
B3)$\mathrm{t}’’(x)arrow\infty,$$\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{i}\mathrm{n}\dot{\mathrm{u}}$$\mathrm{k}’’(x)$$(xarrow\partial \mathcal{M})$For example, when$f_{i}(x)$$\mathcal{M}$that satisfies the following conditions:ously differentiable on

is positive definite on$\mathcal{M}$$\mathrm{i}\mathrm{n}\mathrm{t}\mathcal{M}$

,

,

.

is linear or quadratic (, more generally, relatively Lipschitz$[1\overline{/}]$

)

(3.4)

$\phi’(x):=-\sum_{i=1}^{/_{\mathit{1}}}\log(-fi(x))$

is said logarithmic barrier
is known to satisfy the above conditions. Such a function, called analytic center, plays an important role inforand its unique minimizer oninterior-point methodology.
Now alllong some classes of interior-point algorithms, we consider path $foll\dot{o}wing$ andaffine scaling lnethods for the problem (3.1) and analyz.e their associated continuous
trajectories.
One of the simplest path following methods is barrier method, which involves the mininlization problelu for the following weighted sum of the barrier and objective functions:$\iota l’(x)$$\mathcal{M}$$\mathcal{M}$$\Psi_{t}(x):=tc^{T}x+\uparrow l)(X)arrow\min$

,

(3.5)

75

where $t>0$ is aparameter. Let
origin-al convex problem (3.1), then we obtainbe a minimizer of$x\#$$(tarrow+\infty)$$x^{t}(t)arrow \mathrm{U}\tau^{\#}$For heand$x(\# t)$$\backslash \backslash ^{r}\mathrm{e}\mathrm{i}\mathrm{g}\mathrm{h}\iota \mathrm{i}\mathrm{n}\mathrm{g}$$\Psi_{t}(x)$and the.

by discretizing properly as an increasing sequenceandfinding. for each . approxinlant of
by Newton method, we obtain a sequence that
follows near the path $x(\# t)$ converging to . The pathis called central path.
In addition to this method. there are also some variants of the path following methods,
which nlinilllize. for exalnple.
$\mathrm{t}$$\mathrm{i}\mathrm{m}\mathrm{p}\mathrm{l}\mathrm{e}\mathrm{m}\mathrm{e}\mathrm{n}\{\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$,$t$$\{t_{i}\}$$x\#(t_{i})$$t_{\mathrm{i}}$$x\#$$x^{\mathrm{t}}(t)$$\Psi_{9,\llcorner}(x):=-\zeta\log(S-C^{\tau_{X}})+\psi(x)arrow\min$,for given $\zeta>0$

(3.6)

.

(3.7)

or
$\mathrm{r}t)(x)arrow\min$Let,$\mathrm{s}.\mathrm{t}$.

$c^{T}x=\tau$be theof (3.6) and (3.7), respectively, then we find they
converge to when the parameters or approach the optimal value offrom theabove [16]. Note that. however, $x(\# s)$ andc.oinc.ide with the central path $x\#(t)$ withdifferent parameterizations.
Thus, the above three types of path-following methods finally generate sequences thatconverge to the optimal solution following the central path. Further, when the barrier
function $v’(x)$ has a property called self-concordance [16], i.e.,$x^{\dot{i}}(s)\mathrm{a}\mathrm{n}\mathrm{d}.r\#(\mathcal{T})$$\mathrm{l}\mathrm{n}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{n}\dot{\mathrm{u}}\mathrm{z}\mathrm{e}\mathrm{r}\mathrm{s}$’$x^{\aleph}$$t$$c^{T}x$$\tau$$x\#(\tau)$

$x\#$

,

$\forall h=(h^{i})\in \mathrm{R}^{m},$$| \sum_{1i.j.k,=}^{m}\Gamma^{*}llhijh^{k}ijk\cdot|\leq o(\sum_{i,j=1}^{m}gijhihj)^{3/}2$$\exists a\in \mathrm{R}$

,

(3.8)

these methods are known to work efficiently in terms of worst-case computational complexity.

1

On the other hand, affine scaling method is essentially a gradient method along thefield:$\prime \mathrm{e}\mathrm{C}\mathrm{t}\mathrm{o}\mathrm{r}$$.\dot{\tau}=g^{-1}(_{X})_{C}$where $g(x)$ is the Hessian matrix of$\psi(x)$

(3.9)

,

, i.e.,$g(x):=(gij(x))$ ,$g_{ij}(X):=\partial 2\psi(X)/\partial x^{i}\partial_{X^{j}}$.

The right-hand side of (3.9) can be interpreted as gradient vector for the objective function
with respect to the Riemannian metric defined on.
Now we show both central path and affine scaling trajectories are characterized as-geodesics of dualistic geometry derived from the barrier function. This.asgeneralization of [20] for linear Programming case. Let us consider$c^{T}x$$\mathcal{M}$$g$$\nabla$$\uparrow\int’(x)$$\mathrm{f}\mathrm{a}\mathrm{c}.\mathrm{t}\mathrm{w}$$\Psi_{t}(x):=t_{C^{T}x}+u\acute’(X)$Since the Hessian matrix of
optimality condition:$\Psi_{t}(x)$,$c^{T}:=[c_{1}$$c_{2}$. ..

$c_{m}]$.

(3.10)is also positive definite, $x\#(t)$ is a unique solution of the$\frac{\partial\Psi_{t}(x)}{\partial x^{i}}.\cdot=t_{C_{i}}+\frac{\partial_{\mathrm{t}}/)(x)}{\partial x^{i}}=0$,$i=1,$$\ldots,$$m$.

(3.11)

76
T..his condition can be represented in dual coordinate system as follows:$y_{i}(t)=-c_{i}t$ ,$t>0$ ,

$i=1,$$\ldots,$$m$.

(3.12)

Thus, the central pathturns out to be a half straight line in the dual coordinate
in (3.12) satisfies
system, where its initial point is the origin. Since$y^{t}(t)$$y_{i}(t)$$\frac{d_{\mathrm{t}j_{i}}}{clt}=-c_{i}$.

$i=1_{f}\ldots$

we have differential equations for the central path.,using (2.10)$x(\# t)$$\frac{d\iota^{\backslash }j}{dt}=-\sum_{j=1}^{m}\mathit{9}^{\dot{J}}ic_{i}=-\sum_{j=1}^{m}g^{ji}\partial_{i}(c^{T}x)$$j=1,$,

with its initial point. i.e., analytic center for(3.9)
equation withfor the affine scaling trajector.v,
a solution of the gradient system of the object function$x(\mathrm{O})=x_{\mathrm{A}\mathrm{C}}$(3.13),$m$(3.14), $m$ ,. This is the same differential
implies the central path is also$\mathcal{M}$$\mathrm{W}\mathrm{h}\mathrm{i}_{\mathrm{C}\mathrm{h}}$$c^{T}x$$g$$\ldots$

under the Riemannian metric.

Finally. multiply both sides of (3.14) by
the differential equation of -geodesics:

and differentiate theln by , then we obtain$t$$g_{\dot{\{}j}$$\nabla^{*}$.

$i=1,$$\sum_{j=1}^{n\mathit{1}}gij^{\frac{d^{2}\tau^{j}}{clt^{\mathit{2}}}}\backslash +\Gamma_{ijk^{\frac{cl\tau^{j}}{dt}}}^{*}.\frac{d\mathfrak{r}^{k}}{dt}=0$.

$\ldots$

,

$n$

,

where

$\sum_{j,k=1}^{m}\Gamma_{i}^{*}jk=\partial_{i}\partial_{k}\partial_{j^{\psi’}}|=\partial_{k}g_{ij}$.

(3.15)

Hence both central path and affine scaling trajectories are proved to be -geodesics.
Further, in contrast with the primal coordinate case, following these trajectories in the
dual coordinate systelll is a very easy task with no iteration, i.e., just extending a straightline as shown in (3.13).
Therefore, one intuitive idea that arises from this fact is that following the central pathor affine scaling trajectories in the dual coordinate system, via Legendre transformation,
nlay have better performance than doing so in the primal coordinate system. in terms ofcomputational complexity. Additionally whenis a self-concordant, there also exists
the relation between and an error [16]$\nabla^{\star}$$\mathrm{t}_{L}’!(X)$$t$(3.16)$C^{T}X(t)-c^{\tau}x^{\#}\leq\theta/t$ ,where the constant is a parameter depending only on. Consequently, the roughsketch of the al.g.orithnl. as:
Algorithm.
Step 1. Find the initial feasible point.
Step 2.
, the Legendre transform of $x\#(0)$ , using (2.6).
Step 3. For sufficiently large (decided by the accuracy estimate (3.16)),by (3.12).
, inverse Legendre transform of
Step 4. Find
, by (2.7).
$\theta$$\psi(x)$$\mathrm{i}\mathrm{S}\backslash \cdot$$\mathrm{f}.\mathrm{o}\mathrm{l}1_{0}\mathrm{w}\mathrm{s}$$r_{\mathrm{A}}$$x\#(0)\in \mathcal{M}$$\mathrm{C}^{\mathrm{t}}\mathrm{a}\mathrm{l}\mathrm{c}\mathrm{u}\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{e}y’|(0)$$t$$.\mathrm{r}^{t}(t)$$\mathrm{c}.\mathrm{a}1_{\mathrm{C}\mathrm{u}}1\mathrm{a}\mathrm{t}\mathrm{e}y\#(t)$$y(\# t)$77
However, this optimistic idea, of course, turns out false.

Generally, obtaining the
explicitlyaasof is difficult. Hence, to find $x\#(t)$ for
Legendre conjugate
given $y(t)$ in Step 4. we nlust solve, instead of using (2.7) directly, the following nonlinear.
equation:$i=1,$ $\ldots.7n$ , find, .
.. . .
’. given$u^{*}’(y)$$\mathrm{f}\mathrm{u}\mathrm{n}\mathrm{c}\mathrm{t}\mathrm{i}_{\mathrm{o}\mathrm{n}}$$y$$x_{i}(t),$$y_{i}(t),$$-$$\mathrm{s}.\mathrm{f}.$$\frac{\partial.\iota^{\mathit{1}|}}{\partial\tau^{i}}\vdash(x)=y_{i}(t)$$i=1,$,$\ldots,$$m$(3.17),

or equivalently the following convex problems:$\arg \mathrm{l}\mathrm{n}\mathrm{i}\mathrm{n}\{v’x\dagger(X\mathrm{I}-\sum_{=i1}^{\mathrm{z}}nyi(t)x^{i}\}’.$

isEven ifgood initial estilllates for$\psi(x)$$\mathrm{s}\mathrm{e}\mathrm{l}\mathrm{f}_{-_{\mathrm{C}}}\cdot \mathrm{o}\mathrm{n}\mathrm{C}\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{a}\mathrm{n}\mathrm{t},$$x^{l}$$\mathrm{c}\mathrm{o}\mathrm{m}_{\mathrm{P}}\mathrm{u}\{\mathrm{i}\mathrm{n}\mathrm{g}X^{b_{(}}t$$i=1,$$\ldots,$

$t?l$

.

) in such a way might cost more, without, than the path-following methods mentioned before.

4

Semidefinite Programming

4.1

Information Geometry for P.ositive Definite Matrices

In this section. we specialize the previous discussions to semidefinite programming (SDP)

case.

Let
basis of$c\in \mathrm{R}^{n?}$$Sym(\mathrm{t}?)$and $E_{i}\in Sym(n).i=0,$ $\ldots.m$ , whereare linearly independent. Consider the following form of SDP problems:$\{E_{i}\}_{i=}^{m_{1}}$$\min_{x}c^{T}x,$$\mathrm{s}.\mathrm{t}$. $P(X)$$=E_{0}+ \sum_{i=1}^{m}xiE_{i}\geq 0$

.

(4.1)

.

We introduce notation for some sets associated with the above SDP probleln. Denote. vector and affine subspaces in $Sym(n)$ respectively defined as
and$\mathrm{b}.\mathrm{v}$$E_{0}+\mathcal{V}$$\mathcal{V}$$\mathcal{V}:=\{X|X\in \mathrm{s}\mathrm{p}\mathrm{a}\mathrm{n}\{Ei\}_{i=1}m\}$.

$E_{0}+\mathcal{V}:=\{X|X-E_{0}\in \mathcal{V}\}$

Then the constrained set of $P(x)$ in (4.1) is the closure ofconic form [16]. i.e.,$\mathcal{L}:=PD(\uparrow\iota)\cap(E_{0}+\mathcal{V})$

$L$

.

(4.2)

which is defined as so-called

.

(4.3)

that coincides with tangent space of .
In SDP case. path-following algorithms commonl.v use a self-concordant function$-\backslash ^{\mathrm{T}}\mathrm{o}\mathrm{t}\mathrm{e}$$\mathcal{V}$$\mathcal{L}$$\mathrm{t}^{\mathit{1}}’(x)=$as a barrier. Then. according to thestructure
as follows [18]:$(\mathcal{L}, g.\nabla, \nabla^{*})$-logdet $P(x)$$\mathrm{s}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{i}_{0}\mathrm{n}3$(4.4), we can introduce inforlnation geometric

to define dual coordinate, Riemannian metric and$y_{i}=-\mathrm{t}\mathrm{r}(P(-.\tau)^{-}1Ei)$,$g_{ij}(x)=\mathrm{t}\mathrm{r}(P(x)^{-}1EiP(x)^{-1}Ej)$$\nabla^{*}$-connection
(4.5)

(4.6)

,

$\Gamma_{1jk}^{*}.(x)=-2\mathrm{t}\mathrm{r}(P^{-1}(X)EiP(x)-1E_{j}P(x)^{-1}Ek)$

.

(4.7)

78
The affine-scaling trajectories and central path are still a solution of-geodesic
equation (3.15) on the interior of . As described in the previous section, Legendre
conjugate
and transform.$\tau=x(y)$ can not be generally expressed as functions of .
Now we turn our points of view treating the problem in. Let
beany basis matrices of a subspace complementary to and define the set of bi-orthogonalbasis matrices
as follows:$\mathrm{t}_{}\mathrm{h}\mathrm{e}\nabla^{*}$$\mathcal{L}$$n^{}!^{*}(y)$$y$$PD(\uparrow?)$$\mathrm{t}_{\mathfrak{i}}\mathrm{o}$$\{E_{i}\}^{N}i=m+1$$\mathcal{V}$$\{E^{j}\}_{j=1}^{\mathrm{V}}\mathrm{A}$$-\mathrm{t}\mathrm{r}\{E^{i}E_{j}\}=\delta_{j}^{i}$,$i=1,$$\ldots,$$N$,$j=1,$$\ldots$

, N.

(4.8)

Then we can express any $P\in Sym(n)$ as$P=P( \theta):=\sum_{i=1}^{N}\theta^{i}Ei$

Hence,$\theta=(\theta^{1}\ldots\theta^{\mathrm{A}}\backslash ^{-})T$

coordinate for$P(x)\in \mathcal{L}$

.

(4.9)

is regarded as a.coordinate system for $PD(?l)$ . Note thatis$\theta^{i}=x^{i}+\theta_{0}^{i},$$i=1,$ . .., $l7l$ ,$\theta^{i}=\theta_{0}^{i},$$i=m+1,$ .

$.$, , $N$$\theta$(4.10),(4.11)$\theta=+\theta_{0}$ ,whereis a coordinate for , i.e.,.
To introduce information geometric structure on $PD(n)[18]$ , we use a barrier (potential)on the whole $PD(??)$$\theta_{0}=(\theta_{0}^{1}\ldots\theta^{\backslash }\wedge 0\tau)^{\tau}$$\theta$$E_{0}= \sum_{i=1}^{\mathrm{v}i}\wedge\theta_{0}Ei$$E_{0}$$\mathrm{f}\mathrm{u}\mathrm{n}\mathrm{c}\mathrm{t}\mathrm{i}_{\mathrm{o}\mathrm{n}}$(4.12)$\iota’\mathrm{t}(\theta)=-\log\det P(\theta \mathrm{I}\cdot$

Then the Legendre transform of$\theta$,denoted by$\eta$, is$\eta_{i}(\theta)=-\mathrm{t}\mathrm{r}(P(\theta)^{-1}Ei)$

Note that for all

$P$

on

.

(4.13)$\mathcal{L}$$m-$. $i=1\ldots.,$
holds from (4.5) and (4.13). The dual coordinate$PD(’ ?)$ as follows:$.j\iota i=\eta_{i}$(4.14)$\eta=(\eta_{1}\ldots\eta_{N})^{\tau}$represents any $P\in$(4.15)$P=P( \eta):=(_{i=1}\sum^{\mathrm{A}}’|iEi\mathrm{I}^{-1}$

Riemannian llletric and coefficients of -connection are also in the salne form as (4.6)
andexcept replaced by .
will use the same notation
both and$PD(n)$ . Information geometric structure
coincides with induced one from$(PD(l?), g, \nabla, \nabla^{*})$ defined likethis.
A significant point for the case of $PD(n)$ is that we can give explicit expressions ofLegendre conjugate
and inverse Legendre transform as functions of :$\nabla^{*}$$g$$(4.\overline{l})$$x$$\theta$$\mathrm{W}^{\mathrm{v}}\mathrm{e}$$g,$$\nabla,$$\nabla^{*}\mathrm{f}\mathrm{o}\Gamma$$\mathcal{L}$$(\mathcal{L}, g_{\mathfrak{c}}.\nabla, \nabla^{*})$$\iota\vee^{*}/’(\eta)$$\eta$$\iota_{-}’’(*\eta)=-\log\det P(\eta)^{-1}$$\theta^{i}(\eta)=-\mathrm{t}\mathrm{r}(P(\eta)E^{i})$.

,(4.16)(4.17)

Thus, frolll (4.13) and (4.17) the (inverse) Legendre transformation on $PD(n)$ from one
coordinate to the other is essentially. inverting symmetric positive definite lnatrices andis very cheaply executed without iterative optimization procedures as in general c.ases.

79

4.2

$\nabla^{*}$-autoparallel submanifold in $PD(n)$Now computational difficulty of the inverse Legendre transfornl is avoided in case of$PD(71)$ . Further, the central path and affine-scaling trajectories are-geodesics inand there holds a relation (4.14). Then the natural question that arises is as follows:
Question: Does the algorithm considered in the previous section workwithout. iterative
optilnization )in $PD(n)$ ?
Unfortunately. the answer is generally NO. The reason is that-geodesic of thesubmanifold
is not} that of the alnbient manifold $PD(?l)$ . However, if both-geodesics coincide, the ansrver for the question is affirmative. Such a property is characterized by a geonletric term: totally geodesic or autoparallel.
We use the following definition and fact:
Definition [13] : Let $N$ be a lnanifold equipped with a certain connection andbea submanifold with induced connection from of alnbient manifold $N$ . The submanifold
is said to be -autoparallel if for any vector fields $X$ and lr onderivative
is again tangent toat every point.
Proposition 4.1 [13] : Let (is torsion-free, then a submanifold
is autoparallel
$N$
in
iff
is totally geodesic, i.e., an every geodesic of $N$ starting from a point onwith an initial vector tangent tostays in.
$\nabla^{*}$$\mathcal{L}$$\mathrm{r}\mathrm{o}\mathrm{C}\mathrm{e}\mathrm{d}\mathrm{u}\mathrm{r}\mathrm{e}\mathrm{s}$$1$$\nabla^{*}$$\mathcal{L}$$\mathrm{a}1\backslash \backslash ^{7}\mathrm{a}$$\mathrm{s}$$\nabla$$\overline{\nabla}$$\mathcal{M}$$\overline{\nabla}$$\overline{\nabla}$$\mathcal{M}$$\mathcal{M},$$\overline{\nabla}_{X}l^{r}$$\mathrm{c}.0\backslash r\mathrm{a}\mathrm{r}\mathrm{i}\mathrm{a}\mathrm{n}\mathrm{t}$$x\in \mathcal{M}$$\mathcal{M}$$N,\overline{\nabla}$$\mathcal{M}$$\mathcal{M}$$\mathcal{M}$$\mathcal{M}$$\mathcal{M}$

Recalling that theconnecfion is torsion-free, we immediately obtain a main resultof this section:
Theorem 4.2: If is-autoparallel. we can solve SDP problem (4.1) without any
optimization procedure by executing the algorithm in the section 3.
Remark: i) The converse is not true. i.e.. there exist SDP problems that can be solvedby the algorithnl while associated with them are not-autoparallel. This is due tocolnbination of the initial point and (See exanlple 2 below). ii) The submanifold
is always -autoparallel by its definition [18]. Hence-autoparallel submanifold isdually autoparallel with respect to both andconnections.
$\nabla^{*}$$\mathcal{L}$$\nabla^{*}$$\mathcal{L}$$\nabla^{*}$$c$$\mathcal{L}$$\nabla$$\nabla^{*}$$\nabla$To check whether the isLemma 4.3: A subnlanifold$\mathcal{L}$$\mathcal{L}$$\nabla^{*}$-autoparallel. we have the following condition:of (4.3) in $PD(n)$ is-autoparallel if and only if$\nabla^{*}$$\mathcal{L}$$\nabla^{*}$$-E_{i}P^{-1}E_{j}-EjP^{-}1E_{i}\in \mathcal{V}$ ,for$\forall P\in \mathcal{L}$,$1\leq i,j\leq m$.

(4.18). to $Sym(n)$ , we can identify the
Proof: Since the tangent space of $PD(??)$ istangent vector at and thematrix . Then -covariant derivative
can be shown to
the following matrix representation [18]:$\mathrm{i}_{\mathrm{S}\mathrm{O}1}\mathrm{n}\mathrm{o}\mathrm{r}_{\mathrm{P}}\mathrm{h}\mathrm{i}\mathrm{c}$$P$$\partial_{i}$$\mathrm{s}_{3}\mathrm{m}\mathrm{m}\mathrm{e}\mathrm{t}\Gamma \mathrm{i}\mathrm{C}$$E_{i}$$\nabla^{*}$$\nabla_{\partial_{i}}^{*}\partial_{j}$$\mathrm{h}\mathrm{a}\backslash \cdot \mathrm{e}$$\nabla_{\partial_{j}}^{*}\partial_{j}\equiv-E_{i}P^{-}1E_{j}-EjP^{-1}E_{i}$where the symbol
follows.

$\equiv \mathrm{d}\mathrm{e}\mathrm{n}\mathrm{o}\mathrm{t}\mathrm{e}\mathrm{s}$,the above identification. Henc.e, the statements immediately
Q.E.D.

Especially, when $E_{0}=0$ , i.e.. is convex subcone of $PD(n)$ , the tangent space-autoparallel submanifold has a relation with Jordan subalgebra of $Sym(n)$ .
$\mathcal{L}$$\nabla^{*}$$\mathcal{L}$$\mathcal{V}$of80): Let us define thealgebra ofDefinition $[14, 9]$ (by means of usual matrix product as follows:
space$Syl?\mathit{1}(n)$$\mathrm{J}_{\mathrm{o}\mathrm{r}}\mathrm{d}\mathrm{a}\mathrm{n}$$\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{d}\mathrm{u}\mathrm{c}\mathrm{t}*\mathrm{o}\mathrm{n}$the vector$Sym(\uparrow?)$$X*]’:= \frac{1}{2}(Xl^{r}+Y\mathrm{x})$.

(4.19)

the productWe call the vector space $s_{y}7??(l?)$ equipped with the usual matrix.
$*Jordan$ algebra ofis an element of submanifold
Theorem 4.4: Assume $E_{0}=0$ and the identity
autoparallel in the sense(andduallyhence isof the form (4.3). Then is) if and ollly if
is Jordan subalgebra of $Sym(n).\cdot$of both and$A,$
be represented as
due to $E_{0}=0$ . Let
Proof: First note that$\mathrm{s}\mathrm{u}\mathrm{m}+\mathrm{a}\mathrm{n}\mathrm{d}$$Sym(\prime l)$$\mathrm{n}\mathrm{l}\mathrm{a}\mathrm{t}_{1\mathrm{r}}\mathrm{i}\mathrm{X}$$\mathcal{L}$$\nabla$$I$$\mathcal{L}$$\nabla^{*}-\mathrm{a}\iota\iota \mathrm{t}\mathrm{o}\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{e}1$$T_{P}\mathcal{L}(=\mathcal{V})$$\nabla^{*}\mathrm{c}\cdot \mathrm{o}\mathrm{n}\mathrm{n}\mathrm{e}\mathrm{C}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{S}$$B\in T_{P}\mathcal{L}=\mathcal{V}$$\mathcal{L}\subset \mathcal{V}$.
$A= \sum_{i=1}^{m}$

Suppose$\mathcal{L}$is$\nabla^{*}$$cl_{\backslash }^{i}Ei$,$B= \sum_{i=1}^{m}b^{i}Ei$.

-autoparallel, then, usihg Lemma 4.3, we have$arrow 4P^{-1}B+BP^{-1}A\in \mathcal{V}$. By setting $P=I$ . proves to be Jordan subalgebra of $Syt?l(n)$ .
for all
Since
and $A,$
Conversely. let be Jordan subalgebra and assume$P\in \mathcal{L}$$\mathcal{V}$$P\in \mathcal{L}$$\mathcal{V}$$B\in \mathcal{V}.$$arrow\cdot:*(_{arrow}- 1*B)=\frac{1}{4}(.4^{2}B+BA^{2}+2ABA)\in \mathcal{V}$and,$(_{\wedge}4* \mathrm{A}4)*B=\frac{1}{\mathit{2}}(arrow 42B+BA2)\in \mathcal{V}$it follows .4$B_{arrow}4\in \mathcal{V}$. Using this and$P^{-1}\in \mathcal{L}$(See [14]), we conclude$(A+B)P^{-1}(A+B)--4P-14--BP-1B=AP^{-1}B+BP^{-1}A\in \mathcal{V}$This ilnpli.es$\mathcal{L}\mathrm{i}.’.

\mathrm{s}\nabla^{*}$-autoparallel.

$\mathrm{Q}.\mathrm{E}$.D.

Example 1: The set of synumetric matrices whose eigenvectors are fixed is one of exam. Another example is the set of doubly symmetricples of Jordan subalgebra of
matrices, which is synmetric with respect with both main- and anti-diagonals [14]. Hence,
when coincicles to these set. SDP can be solved without any iteration for any vector
using the algorithm discussed above.
and initial point
Example 2: Consider the following SDP problenl,$S_{J^{\vee}}\iota m(n)$$c$$\mathcal{V}$$\backslash \tau(0)$$\min x^{1}$.

$\mathrm{s}.\mathrm{t}..P(x)$If we take any initial point
solved with the above algorithm.

$:=\geq 0$ .

$\mathrm{s}\mathrm{a}\mathrm{t}\mathrm{i}_{\mathrm{S}}\mathrm{f}.\mathrm{V}\mathrm{i}\mathrm{n}\mathrm{g}X2(0)=0$

or $x^{1}(0)=x^{2}(0)$ , the problem is readily

815

General Case

5.1

Predictor-Corrector type algorithm in Dual Coordinate

In this section, we consider a simple modification of the algorithm given in the section
4 to solve general SDP problems even in the case when is not-autoparallel. By
examining behaviors of the modified algorithm, we show its computational complexity is
directly related to a geometric quantity called the second fundamental form (or sometimes
called Euler-Schouten embedding curvature).
NVe here denote. by. an affine scaling trajectory or central path on , with a, and represent it by
given initial interior pointand coordinates rather thanto discuss its behavior in. Note that when $P\#(t)$ is the central path,is theanalytic center for . The relation between the coordinates and has been given in$\nabla^{*}$$\mathcal{L}$$P^{\#}(t)$$\mathcal{L}$$P_{0}\in \mathcal{L}$$\theta$$\eta$$PD(\uparrow?)$$x$$P_{0}$$\mathcal{L}$$\theta$$x$(4.10).

Let us partition coordinate vector
compatibly:

wllere$\overline{\theta}=(\theta^{i})$.

$\eta$$\eta=$ ,$\theta=!$$\underline{\theta}=(\theta^{\kappa}.),$$\overline{\eta}=(\eta_{i})$.

From (3.14) and the fact that
denoted byis the solution for$P^{t}(t)$and Rienlannian metric matrix $G=(g_{pq})$$\theta,$$C_{7}=$ ,$\underline{?|}=(\eta\kappa),$stays in$G_{1}=(g_{ij}),$$\mathcal{L}$(5.1)$C_{72}=(g_{i}\kappa),$

for all $t\geq 0$ , the$\theta$$C_{7}3=(g\kappa\nu)(5.2)$

coordinate of $P\#(t)$$\theta^{j}(t)$$\dot{\theta}==-$ ,
where
Since
equal to$\theta_{0}=(\theta_{0}^{i}.

$\theta(0)=\theta_{0}$

.

(5.3)

is coordinate of an initial point
for the affine trajectory on. the Jacobian matrix of the Legendre transformation from to
as in (2.10), coordinate ofdenoted byis the solution of\theta_{0}^{\prime_{\tilde{\mathrm{t}}}})$$\theta$$P_{0}$$(\partial t|p/\partial\theta^{q})$$\eta$$C_{7}$$P^{l}(t)$$\eta$$\mathcal{L}$$\theta$.

, is$\eta(\# t)$$\dot{\eta}=C_{7}\dot{\theta}=-(C_{7}^{T}\eta 2()c^{-1}\tau 1(\eta)cC)$,$\eta(0)=\eta 0$

.

(5.4)

where
is coordinate of an initial point for .
Now we show a rough sketch of a lllethod to follow the path $P\#(t)$ . Assume we are
given a certain point
on $P\#(t)$ corresponding to the parametervalue $t=t_{cl}$ . Let
be the-geodesic of $PD(n)$ which passes throughwith thedirection there equal to. Ifdefine constantas$?|0=(\eta_{i0}.

\eta_{\kappa 0}.)$$P_{0}$$\eta$$P_{o^{i}}’:=(\theta^{t_{()}}t_{a})=(\eta^{d}’(ta))$$\nabla^{*}$$P^{\mathrm{x}}(t)$$P_{a}\#$$\dot{P}^{t}(t_{o})$$\backslash \cdot \mathrm{e}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}\underline{c}=(c_{\kappa})\in \mathrm{R}^{N-m}$$\backslash \backslash \cdot \mathrm{e}$$\underline{c}:=-c_{\tau\underline{\supset}}.‘(\eta^{t}’(t_{a}))C^{-1}71(\eta^{\#}(t_{a}))c$

then$\eta$

coordinate of. i.e.,$c_{\kappa}:=.

\sum_{i\mathrm{j}=1}^{m}g_{\kappa}j(\eta^{\#}(t_{a}))g1(ij\eta^{\#}(t_{a}))ci$

,

where

$(g_{1}^{ij})=G_{1}^{-1}$

,

(5.5)
$P^{*}(t)$.

denoted by$\eta^{\mathrm{x}}(t)$$\dot{\eta}=-$ ,is the solution of$\eta(.t_{a})=$.

$\eta^{\mathfrak{p}}(ta)$

.

(5.6)

82

as a linvia coordinate, we can regard
andThus. by viewing
on the affine scal. Hence, the pointat the point
earization of
ing trajectory corresponding to the new paranleter $t=t_{b}$ has first order approximation
path $P\#(t)$ . However, when is. This is the predicting step to follow
todue to the approxnot -autoparallel. we need a correcting step returning from
imation error. Iterating each step alternatively leads us to so-called predictor-corrector
is outside of the feasible region .
type algorithm. Note that the predictor
is obtained as
because the
The predicting step is easilvv$P^{t}(t)$$P^{*}(t)$$P^{i}(t)$$P^{*}(t)$$\eta$$P_{b}^{\#}:=P\#(t_{b})$$P_{a}^{t}$$P_{b}^{*}:=P^{*}(t_{b})$$\mathcal{L}$$\mathrm{t}_{1}\mathrm{h}\mathrm{e}$$\nabla^{*}$$P_{b}^{*}$$P_{b}^{\#}$$\mathcal{L}$$P_{b}^{*}$$\eta^{*}(t_{b})$$\mathrm{e}\mathrm{x}\mathrm{e}\mathrm{C}\mathrm{u}\mathrm{t}\mathrm{e}\mathrm{d}$(5.7)$\eta^{*}(t_{b})=\eta^{t_{(}}f_{\mathit{0}})-(t_{b}-t_{a})$or in a matrix fornl$P^{*-1}(t_{b})=P^{\#-1}(t_{o})-C\delta t$,.
is a constant lnatrix. the coordinate of which coincides with
Next, before
state about the correcting step, it is convenient to introduce thefoilowing subnlanifold:Definition: Given $P\in PD(r\iota)$ . define
as follows:

where

$C$

$(c^{T}\underline{c}^{T})^{T}$$\eta$$\backslash \backslash \cdot \mathrm{e}$$\mathcal{L}^{\perp}(P)\in PD(n)$$\mathcal{L}^{\perp}(P):=\{P(\underline{\eta})|P^{-}1(\underline{\eta})=P^{-1}+\sum_{\kappa=m+1}\eta\kappa E\kappa, P(\underline{\uparrow_{1)}}N.\in PD(n)\}$.

Note that is a coordinate system of this submanifold. See [18] for various properties of. For the correcting step. we have the following result:
Theorem 5.1: [18] The corrector
is the unique solution for the problem of minimizing,: $PD(n)\cross PD(n)arrow \mathrm{R}$ , i.e.,the quantity so-called divergence$\underline{\prime 7}$$\mathcal{L}^{\perp}(P)$$P_{b}^{\#}$$D(\bullet$$\bullet$$P_{b}^{d}’=\arg \mathrm{n}1\mathrm{i}\mathrm{n}P\in c\perp \mathrm{t}P_{b}^{*})D(P^{i}0’ P)$

$)$

.

(5.8)

where $D(P_{1}, P_{2}):=\log\det P_{2}$ –log det$P_{1}+\mathrm{t}\mathrm{r}(P.-1P21)-n$(5.9)

By representing
by and log det
is a constant, the above minimization
problenl is
to convex programming problem of$P\in \mathcal{L}^{\perp}(P_{b}^{*})$$P_{0}^{\#}$$\underline{\eta}$$1^{\cdot}\mathrm{e}\mathrm{d}\mathrm{t}\mathrm{l}\mathrm{C}\mathrm{e}\mathfrak{c}1$$\eta^{t}(tb)=\arg \mathrm{m}\mathrm{i}\mathrm{n}\underline{\eta}\mathrm{p}(\underline{\eta})$

where

,

$\mathrm{s}.\mathrm{t}$.

$P(\underline{\eta})\in \mathcal{L}^{\perp}(P_{b}^{*})$(5.10),.

$\forall’\wedge(\underline{||}):=-\log\det(P_{b}^{*-1}+\kappa=n?\sum_{+1}^{N}\eta\kappa E^{\kappa})-\sum_{\kappa=m+1}^{r}\eta\kappa\theta^{\#\kappa}0\mathrm{A}$(5.11)

Since the first terlll of the objective function is self-concordant and the second one islinear with respect to . the function is also self-concordant due to (3.8). Hence, we
can solve efficiently this convex optimization problem by dumped Newton nlethod [16].
Since
by its definition, we can say, to sum up, this nlodified algorithm is alternating predictors and correctors in the submanifold. Notethat the above predicting and correcting procedures can be completely executed with only
coordinate without calculating coordinate or matrix inversion.
$\varphi$$\varphi$$\underline{\eta}$$\mathcal{L}^{\perp}(P_{b}^{\mathrm{x}})=\mathcal{L}^{\perp}(P_{b}^{\alpha})\mathrm{h}$$\bigcup_{P\in P\# t}(\mathrm{f}),0\leq \mathcal{L}\perp(P)$$\theta$$\eta$

83
5.2

Step Length

let us discuss a estimate of the possible long step we can take in each predic.tingof iterations less than some prescribed upper boundin the succeedillg corrector step. In our settings this is equivalent to disc.uss how large
increment
we can take at each predicting step. Our analysis may be useful
in design a long-step type algorithm.
XVe first show
coordinate representation of the predicting error can be expressedby so-called the second fundalnental form. Let us define new coordinates
on $PD(n)$sllch that their vector fields are defined as”$\mathrm{F}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{l}\mathrm{l}.\backslash \backslash$directlon, while keeping the$\mathrm{n}\mathrm{u}\mathrm{I}\mathrm{n}\mathrm{b}\mathrm{e}\mathrm{r}$$\delta t:=t_{b}-t_{o}$$\mathrm{t}\mathrm{h}\mathrm{e}/_{7}$$\tilde{\eta}_{p}$(5.12),$\frac{\partial}{\partial_{|i}^{\sim}},:=\sum_{j=1}^{m}g^{ij}1\frac{\partial}{\partial\theta^{j}}$$\frac{\partial}{\partial\tilde{\eta}_{h}}$$:= \frac{\partial}{\partial\eta_{\kappa}}$.

Note that at any point on. because eachdue to (2.11). Since
lllatrices:$\mathrm{r}\mathrm{e}\mathrm{s}_{1})\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{i}\backslash ^{r}\mathrm{e}11v$$\mathcal{L},$$\partial/\partial\tilde{\eta}_{i}$.

(5.13). are tangential and orthogonal toand,is alillear colnbination ofand
as is shown in (2.10), we have the following Jacobian$\partial/\partial l^{\sim}|i$$\partial/\partial\tilde{\eta}_{\kappa}$$\mathcal{L}$$\partial/\partial\theta^{i}$$g(\partial/\partial\theta^{i}, \partial/\partial\eta_{\kappa})=\delta_{i}^{\kappa}$$(\partial l|_{p}/\partial\theta^{q})=C_{7}$$( \frac{\partial_{l|_{\mathit{4}})}}{\partial_{1|_{\mathrm{r}_{\mathit{1}}}}^{\sim}})=.$(5.14)$( \frac{\partial\tilde{\eta}_{q}}{\partial\eta_{p}})=\backslash$,and$( \frac{\partial\theta^{p}}{\partial_{1_{q}}^{\sim}},)=$,

where $S:=G_{3}-c^{\tau}\tau 2c^{-1}C_{72}1$ .

Let us denote. Sinceandare respectively tangential and orthogonaltoat every. we can represent the components of the second fundamental form
-connection, denoted by[13] of for, as a Christoffel’s symbol of)withto coordinate system:$\tilde{\partial}^{i}$$\tilde{\partial}^{p}:=\partial/\partial\uparrow 7_{I^{J}}\sim$$\tilde{\partial}^{\kappa}$$P\in \mathcal{L}$$\mathcal{L}$$\mathcal{L}$$\nabla^{\mathrm{x}}$$\overline{H}_{\kappa}^{*ij}.$$\nabla^{*}- \mathrm{c}.\mathrm{o}\mathrm{n}\mathrm{n}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{i}_{\mathrm{o}\mathrm{n}}$$\mathrm{e}C\mathrm{t}$$\mathrm{r}\mathrm{e}\mathrm{s}_{1}$$’|\sim$$\overline{H}_{h}^{\mathrm{x}}.\mathrm{i}j=\tilde{\Gamma}_{fi}\mathrm{x}jj\sum_{p=}=\nwarrow^{\mathcal{T}}1\tilde{g}_{\kappa p}\tilde{\Gamma}*ijP$Here$\tilde{g}_{pq}$.

$i.j=1,$$\ldots$

is the conlponents of the inverse matrix of, $m$ ,$(\tilde{g}^{pq})$$\kappa=m+1,$$\ldots$, N.

(5.15)

such that(5.16)$g\sim\eta=g(\tilde{\partial}^{p},\tilde{\partial}q)$alld$\overline{\Gamma}^{*pqr}=cJ(\nabla_{\overline{\partial}}*\tilde{\partial}q\tilde{\partial}^{r})p’$.

(5.17))The qllantities
information about how locally curved the shape of is in$PD(n)$ in the sense of-connection.
The following result shows coordinate of the error
can be represented by.
$\overline{H}_{h}^{*ij}1$$\Gamma \mathrm{O}\mathrm{V}\mathrm{i}\mathrm{d}\mathrm{e}$$\mathcal{L}$$\nabla^{*}$$\uparrow 7$$\overline{H}_{\kappa}^{\cross ij}.$$P_{b}^{*}-P_{b}^{\#}$

84
Lemma 5.2: For all
predicting error, thesuch that
expression:
has the following$\delta t>0$$t_{b}=t_{o}+\delta t$’$P_{b}^{\mathrm{x}}-P_{b}’$$\eta_{i}^{\mathrm{x}}(t_{b})-\eta_{i}^{4}(t_{b}\{)=0$$\eta_{\kappa}^{*}(t_{b})-\eta^{\oint}h.\{tb$Proof: Using (5.4) and (5.5),$\eta_{i}^{\mu}’(t_{o}+\delta t)=\eta_{i(t_{a}}’\{$)$\backslash \backslash \cdot \mathrm{e}$$-c_{i}\delta t$)$\eta$

coordinate representation of the,$= \frac{\delta t^{2}}{2}\sum_{i,j=1}^{m}\overline{H}_{\kappa}*.ij(t_{0}+\xi\delta t)ci^{C_{j}}$have the Taylor series of$\eta^{\mathrm{J}}(t)$$i=1,$,.

(5.18)

for some $\xi\in(0,1)$$\ldots$

, $m$

$\{$
$\uparrow l_{\kappa^{\wedge}}^{b}(t_{a}+\delta t)=’|_{fi}^{t_{(t_{o}}})-c_{\mathfrak{i}},\delta t+\frac{1}{2}i_{\dot{|}_{\kappa}}^{l}.(t0+\xi\delta t)\delta t^{2}$,$\kappa=’?l+1,$$\ldots$, $N$ ,

(5.19)

Hence, fronl (5.6).

.

$\prime_{7_{i(t_{a}}^{*}}+\delta t)-\eta’i.(t+\zeta\{\delta t)=0$$l|_{i}^{\mathrm{x}},(t_{a}+ \delta t)-\uparrow 7_{\kappa}^{\nu}’(t_{a}+\delta t)=-.\frac{1}{2}\ddot{\eta}_{\kappa}^{\nu}’.(t_{0}+\xi\delta t)\delta t^{2}$

Since(5.20)

for all . its derivative for the direction orthogonal to is zero, i.e.,$h=|??+1\ldots$.
. Accordingly, has the following expression:.
on$P^{t}(t)$$\tilde{\eta}_{\kappa}=0$.

stays in$t$$\mathcal{L}$$-’\backslash ^{-}$$\mathcal{L}$$P^{t}(t)$$\ddot{\eta}^{\#}$$,$.

(5.21)$ii, \iota_{i}=\sum_{i=1}\frac{\partial\eta^{\mu},^{\wedge}\prime\backslash }{\partial\tilde{\eta}_{j}}\prime 7:\sum_{=l1}^{m}\frac{\partial g_{\kappa l/}C_{1}lj}{\partial_{7i}^{\sim}1}Cj’\sim|1l\sim=-i,j.li$

By nleans of the forlllula (A.1). it folloxvs that the relation between
symbols with respect to and 17 coordinates, is$\tilde{\Gamma}_{\kappa}^{*ij}$and$\Gamma_{r}^{*pq}$, Christof-$\mathrm{f}\mathrm{e}\mathrm{l}\mathrm{s}$$\uparrow_{7}^{\sim}$.

$\overline{H}_{h}^{-jj}.=\overline{\tau}\star ij=\prime ip.q.=\sum_{\Gamma}\mathrm{i}\backslash ^{-}1\frac{\partial\eta_{p}}{\partial_{l|}^{\sim}i}\frac{\partial\eta_{q}}{\partial t^{\sim}7j}\frac{o_{1}^{\sim}|_{\kappa}}{\partial\eta_{r}}\Gamma_{r}*pq+\sum_{q=1}^{\mathrm{V}}\frac{\partial^{2}\eta_{q}}{\partial\tilde{\eta}_{i}\partial^{\sim}||j}\frac{\partial\tilde{\eta}_{\kappa}}{\partial\eta_{q}}A$

Recall is -affine. then it follows
the above equation. xve obtain$\nabla^{\mathrm{x}}$$\eta$$\sum_{l=1}^{l\mathit{1}}‘\frac{\partial_{j_{i},l/}c_{1}^{lj}}{o_{||_{?}}^{\sim}}\gamma=\overline{H}_{\kappa}^{*ij}$,$\Gamma_{l^{\backslash }}^{\mathrm{x}}pq=0$

for. Using this fact and substituting (5.14) into

$i,j=1,$$\ldots$, ?,$\kappa=7??+1,$ $\ldots$

Since. $i=1\ldots$ . , on
, the statement holds.
Remark: Due to (5.2) and the fornlula (A.1),
can bewith respect to coordinate.
$\uparrow_{7_{i}}^{\vee}=\prime_{\dot{7}i}=-\mathrm{c}_{i}$$m$$P^{j}(t)4$$\overline{H}_{t\mathfrak{i}}^{\mathrm{x}}ij$$\mathrm{c}.\mathrm{a}1_{\mathrm{C}}\mathrm{u}\mathrm{l}\mathrm{a}\{\mathrm{e}\mathrm{d}$$\theta$$\overline{H}_{\kappa}^{*ij}=\tilde{\Gamma}_{\kappa}^{\star 1}.j=\sum_{l.k=1/\downarrow=}^{m}\sum_{m+1}g_{1/_{1\mu}}^{il}c^{jk}s\kappa\Gamma_{\iota}1\mathrm{v}*.\mu k$

’

where
$(s_{\kappa\mu})=S.$$\tau_{l\iota}^{*\mu},=\sum^{\backslash ^{7}}p=\mathit{1}1g\mu p\Gamma_{l}^{*};_{i}p$

.

, N.

(5.22).D.
using the quantities$\mathrm{Q}.\mathrm{E}$85

Fronl Lelnllla 5.2. when the second fundamental form . is small in some sense, thein coordinate proves to be small and, consequently, we canpredicting error
expect longer predictor step.
Next.
will discuss the possible long increment under the following assumptions:Al) On. the second fundamental form is small in the sense that$\overline{H}_{h^{*\dot{\mathrm{i}}j}}$$\mathrm{r}\mathrm{e}_{1^{)\Gamma \mathrm{e}}}\mathrm{S}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{d}$$\eta$$\delta t$$\backslash \backslash \cdot \mathrm{e}$$P^{t}(t)\in \mathcal{L}$,$f \hat{\mathrm{u}}=m+\max_{- ,1,.-\backslash }\ldots\{|\sum_{i.j=1}\overline{H}^{*i}j|m\kappa C_{ij}C\}\leq\Lambda\prime I$

A2) The corrector returns toexactly.
A2)
The assumption
is not practical but just for the sake of simplicity. This is un$P^{u}’(t)\in \mathcal{L}$necessary if we replace$P^{t}(t)\in \mathcal{L}$by some suitable neighborhood along$P^{b}(t)\in \mathcal{L}$

in

Al).

The crucial point is keeping
in the neighborhood of(preferably the quadratic) not to increase computational cost in the subsequent correcting step.
convergellce
The suitable lneasures for this purpose are the error of the objective function$P_{b}^{\#}$$P_{b}^{*}$$1^{\cdot}\mathrm{e}\mathrm{g}\mathrm{i}\mathrm{o}\mathrm{n}$$\epsilon(\underline{\eta}):=^{\gamma}(\underline{\prime|})-\min_{\mathcal{L}^{\perp}(P_{b}^{*})}\mathrm{y}’\eta(\underline{\eta})=\varphi(\underline{\eta})-\varphi(\underline{\eta^{\#}})$

Since the dumped-ton nlethod can decrease the value of self-concordant functions
constant,
greater than somecan be a nleasure for nunlber of iterations in corrector step.
Another nleasure is Newton decrement [16] for:$\mathrm{A}^{-}\backslash |\mathrm{e}1\backslash$$\epsilon$$(_{\hat{\prime}}(\underline{\eta})$$\lambda(\underline{\eta}):=(’\{(\hat{r}\underline{||})^{\tau}[\varphi^{\prime/}(\underline{\eta})]-1\varphi(’\underline{\eta}))1/2$

where
and
are the gradient vector and the Hessian matrix of, respectively. Snlaller vallle of, which is evaluated at, implies fewer (dumped)
Newton steps to reach , nlinimizer of . Both measures are of course equivalent in thefollowing sense [16]:$\Psi^{\eta}(/\underline{\eta})$$[_{\hat{Y}^{\prime/}}(\underline{tl})]$$\varphi(\underline{\eta})$$\lambda(\eta(*t_{b}))$$P_{b}^{*}$$P_{ly}^{\mu}$$\varphi$$\lambda<1/3\Rightarrow\epsilon\leq’\frac{\mathrm{L}v2(\lambda)(1+\omega(\lambda))}{2(1-\ ’(\lambda))},$$\lambda\leq\rho^{-1}(\epsilon)$,

To evaluate these measures, define
introduce the following quantity:

,

where

$\omega(\lambda):=1-(1-3\lambda)1/3$

where $\rho(\lambda):=\lambda-\ln(1+\lambda)$ .
$e=(e_{\kappa})$, where$e_{\kappa}(\delta t):=\eta_{\kappa}^{*}(t_{a}+\delta t)-\eta_{\kappa}^{\#}(ta+\delta t)$$r(\underline{\eta}):=(eS^{-}\tau 1(\underline{\eta})e)^{1}/2$

Lemma 5.3: If$1^{\cdot}(\underline{||}^{*})<1$$’\cdot(\underline{l|}^{\mathrm{x}})<1/2$

and.

. then$\epsilon\leq\frac{r^{2}(\underline{\eta}^{*})}{2(1-r(\underline{\eta}*))2}$

Further. if,.

(5.23)

then$\lambda\leq\frac{r(\underline{\eta}^{*})(1-r(\underline{\eta}^{*}))}{(1-2r(\underline{\eta})\mathrm{x})2}$.

(5.24)

86

Proof: Since’$\underline{\eta}’$

is the minimizer of$\varphi(\underline{\eta})$, we have the following Taylor series at,$\varphi(\underline{\eta}^{*})=\varphi(\underline{\eta}^{\mathrm{r}}r)+\frac{1}{2}e^{T}\varphi(//\underline{7^{\#}?}+\xi e)e$Combining Theorenl 2.1.1 of [16] and$\varphi^{\prime;}(\underline{\eta})=S^{-1}(\underline{\eta})$$\exists\xi\in(0,1)$,$\underline{\eta}\#$.

(5.25), we obtain$\epsilon=\iota’(r^{\tau}\underline{ll}-)-\hat{}(\underline{l}’,r)=.\frac{1}{2}e^{T}‘\varphi^{\prime/}(\underline{\eta}*+(\xi-1)e)e=\frac{1}{2}r(\underline{\eta}^{*}+(\xi-1)e)\leq\frac{r^{2}}{2(1-r)^{2}}$(5.26),For (5.24), we first recall the following result by [16, p. 24]:$\lambda\leq\rho(r(\underline{\mathrm{t}7}^{1}\aleph)):=\frac{r(\underline{\eta})\#}{(1-r(\underline{\eta}\#))^{2}}$Since thenot larger than($\mathrm{f}\mathrm{u}\mathrm{n}\mathrm{c}\mathrm{t}\mathrm{i}_{0}\mathrm{n}arrow \mathrm{o}$$\bullet \mathrm{I}$.

(5.27)

is monotone increasing on the interval [0,1), the right hand side isdue to Theorem 2.1.1 of [16]. Hence, we have (5.24).
Q.E.D.

$o(\vee\gamma(\underline{\eta}^{*})/(1-r(\underline{\eta}^{*})))$

Thus, both measures can be bounded by. The right-hand sides of (5.23) and(5.24) are nlonotone increasing with respect to when $r<1$ and $r<1/2$ , respectively.
Hence, by setting a suitable constant $r^{*}\leq 1/2$ and solving,
such that$r(\underline{\eta}^{*})$$r$$\delta t$

we can obtain the long predictor$r(\underline{\eta}^{*}(t_{a}+\delta t))\leq r^{*}$), where the number of iterations necessary
ill the succeeding corrector phase is bounded by $i(r^{*})$ , a certain number decided by .
$\mathrm{S}\mathrm{t}\mathrm{e}_{\mathrm{P}\underline{\eta}^{*}(t}a+\delta t$$r^{*}$

Since$S^{-\perp}=(.\mathrm{s}^{\kappa\mu})$

is a submatrix of$C_{\tau}^{-1}$,

we have the following expression [18]:$s^{\kappa\mu}(\underline{\eta}^{*}(t_{a}+\delta t))=\mathrm{t}\mathrm{r}\{P^{*}(t_{a}+\delta t)E^{\kappa}P^{*}(t_{a}+\delta t)E^{\mu}\}$Recall that $P^{*}(t_{5}‘+\delta t)=(P_{o}^{i-1}+\delta tC)^{-1}$ and let$P_{a}^{\#-1}=T\Sigma_{a}T^{T}$

where$\Sigma_{a}=\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}\{G1, \ldots , \alpha_{11}\}>0$

and

.

$T$

.

be nonsingular matrix such that

$C=T\Sigma_{c}T^{\tau}$,$\Sigma_{c}=\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}\{\gamma_{1}, \ldots, \gamma_{n}\}$. Then we have$s’(\backslash \cdot\mu\underline{\eta}^{*}(t_{o}+\delta t))=\mathrm{t}\mathrm{r}\{(\Sigma_{a}+\delta t\Sigma_{c})-1\tilde{E}^{\kappa}(\Sigma_{a}+\delta t\Sigma_{c})^{-1}\tilde{E}^{\mu}\}$where
inlplies$\tilde{E}^{ti}:=T^{-1}E^{t\hat{\iota}}T^{-\tau}$$0$$m+1,$. Since (5.28) is a quadratic form of$\mathit{0}_{i}+\wedge t_{/i}^{\wedge}>0.i=1\ldots.,$$\ldots.-\backslash ^{\mathrm{v}}$$\uparrow$, there exist$n$$1/(\alpha_{i}+\delta t\gamma_{i})$,and(5.28)$P^{*}(t_{a}+\delta t)>$by ’? symnletric matrices$A_{\kappa\mu},$$k\mathrm{t}_{},$$\mu=$

such that$|s^{\kappa\mu}(\underline{\eta}*(t_{a}+\delta t))|=|A_{\kappa\mu}|$$\leq|A_{\kappa\mu}|$ ,(5.29)

87

is a lllatrix. eac.hcolnponent of. Note that
Let us definewhere$|-4_{\kappa\mu}|$$– 1_{\kappa’ l}$of which is the absolute value of corresponding
is dependent only on
and not on .

$\mathrm{C}.\mathrm{o}\mathrm{m}_{\mathrm{P}}\mathrm{o}\mathrm{n}\mathrm{e}\mathrm{n}\mathrm{t}$$\tilde{E}^{\mu}$$arrow 4_{t\mathfrak{i}}.\mu$$\delta t$$\backslash (\delta t):=\{(=\sum_{\kappa,\mu m+1}^{N}|\mathrm{s}4|\kappa\mu \mathrm{I}\}^{1/2}$

Theorem 5.4: Assunle Al and A2. XVhen the increment$\delta t\leq\delta t^{*}$$\delta t$,(5.30)

in the predicting step satisfies,

the number of iterations necessary in the suc.ceeding corrector phase is less thanHereis the largest solution for the inequality$i(r^{*})$$\delta t^{*}$$\frac{\delta t^{2}}{2}\backslash (\delta t)\lrcorner\eta I\leq r^{*}$.

Proof) Straightforward fronl the following inequalities:.

$\uparrow’(q^{*})\leq(_{\kappa.=m}\sum_{\mu+1}^{A}|e_{\kappa}||e_{\mu}||s\kappa\mu|)^{1/2}\backslash -\leq\frac{\delta t^{2}}{2}\searrow(\delta t)t\mathfrak{h}I$

Q.E.D.

References[1] S. Anlari. Differential-Geometrical Methods in, (1985).

$stat\prime i_{St}i_{CS\mathrm{S}\mathrm{i}\mathrm{v}\mathrm{e}}\mathrm{p}\mathrm{r}\mathrm{n}\mathrm{g}\mathrm{e}\mathrm{r}- \mathrm{r}\mathrm{l}\mathrm{a}\mathrm{g}$[2] D. A. Bayer and J. C. Lagarias. The Nonlinear
of Linear ProgrammingI,. Amer. Math. Soc., 314. 499-526 (1989), II, Trans. Amer. Math. Soc., 314,$\mathrm{G}^{\mathrm{t}}\mathrm{e}\mathrm{o}\mathrm{m}\mathrm{e}\mathrm{t}\mathrm{r}\mathrm{y}$$B^{\backslash }ans$527-581 (1989).

[3] S. Boyd, L. El Ghaoui, E. Feron, V. Balakrishnan, Linear Matrix Inequalities in
System and Control Theory. SIAM (1994).
[4] R. . Brockett, Dynamical Systems That Sort Lists and Solve Linear Programming
Problems, Proc. 27th IEEE CDC, 779-803 (1988)$\backslash \mathrm{h}^{r}$[5] D. den Hertog, Interior Point Approach to Linear, Quadratic and Convex Programming, Kluwer Academic Publishers (1994)[6] A. Fujiwara and S. Amari, Gradient Systems in view of Information Geometry, Physica. D80.
(1995)$31\overline{/}- 327$

[7] L. Faybusovich. A Hamilton Structure for Generalized
J. Nonl\prime inear Science, 5, 11-28 (1995)$Al\{\mathrm{f}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{e}- \mathrm{S}\mathrm{c}.\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{n}\mathrm{g}$Vector Fields,.

88[8] L. Faybusovich, Jordan Algebras, Symmetric Cones andpreprint, (1995)[9] J. Faraut$\mathrm{S}_{\vee^{-}}$

Int.erior-point Methods,

A. Koranyi, Analysis on Symmetric Cones, Oxford (1994)[10] M. Iri. Integrability of Vector and Multivector Fields Associated with Interior Point
Methods for Linear Programming,
ematical Programming, 511-525 (1991)$Mat\acute{h}$[11] N. I\v{c}armarliar. A New Polynonial-Time Algorithm for Linear Programming, $C_{om}-$binatorica. 4. 373-395 (1984)[12] N.
. Rienlannian Geometry Underlying Interior-Point Methods for Linear
Progranlnling. Contemporary Mathematics, 114, 51-75 (1990)$\mathrm{I}\backslash \mathrm{a}\mathrm{r}\prime \mathrm{l}\mathrm{n}\mathrm{a}\mathrm{r}\mathrm{k}\mathrm{a}\mathrm{r}$[13] S. Kobayashi and K. Nolnizu, Foundation of Differential
and Sons (1963).

Geo.m etry I,. John Wiley[14] S. D.
. The Role of Abstract Algebra in Structured Estimation Theory, IEEE
Trans. on Inf. Theory, 38-3, 1053-1065 (1992)$1\backslash \mathrm{I}_{\mathrm{o}\mathrm{r}}\mathrm{g}\mathrm{e}\mathrm{r}\mathrm{a}$[15] Y.
for Linear$\mathrm{N}\mathrm{a}1_{\overline{\mathrm{c}}\mathrm{a}}\mathrm{m}\mathrm{u}\mathrm{r}\mathrm{a}$,Lax Pair and Fixed Point Analysis of Karmarkar’s Scaling Trajectory, Japan J. Indust. Appl. Math., 11, 1-9 (1994)$\mathrm{p}_{\mathrm{l}\mathrm{o}\mathrm{g}\mathrm{r}}\mathrm{a}\mathrm{m}\mathrm{l}\mathrm{n}\mathrm{i}\mathrm{n}\mathrm{g}$[16] Yu. Nesterov and A. Nemirovsky, Interior-Point Polynomial Algorithms in Convex
Programming, SIAM (1994).

[17] F. Jarre, Interior-Point AIethods for Convex
Optim\prime iZat,ion. Vo1.26,(1992)$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{g}\mathrm{r}\mathrm{a}\mathrm{m}\mathrm{n}\dot{\mathrm{u}}\mathrm{n}\mathrm{g}$, Applied Mathematics and$28\overline{/}- 311$

[18] A. Ohara. N. Suda and S. Amari, Dualistic Differential Geometry of Positive Definite
Matrices and Its Applications to Related Problems, Linear Algebra and Its Applications, 247, 31-53 (1996)[19] K. Tanabe. Centered Newton Method for Mathematical Programming, System Modeling and Optimization (eds. M. Iri. et al.) Springer-Verlag (1988)[20] K. Tallabe and T.

$\mathrm{T}_{\mathrm{S}\mathrm{u}\mathrm{C}}\mathrm{h}\mathrm{i}_{\mathrm{V},\mathrm{c}}\mathrm{a}$, New Geometry for Linear Programming, Mathematical

Science, 303. .32-37 (1988) in Japanese[21] T. Terlaky. Interior Point Methods of Mathematical Programming, Kluwer Ac.ademic Publishers (1996)$ed_{\mathrm{t}}\mathrm{q}.$[22] S. J. Wright. $Pr^{t}imal$ -Dual Interior Point Methods, SIAM, (1997)

89

A

Appe.ndix-

be local coordinate systems on a manifold equipped with a linear connection.
Let.
When tlle coordinate system is changed fronl x to . associated Christoffel’s sylnbol issubject to the following transformation rule:$\tau \mathrm{a}\mathrm{n}\mathfrak{c}1.\tilde{\mathrm{T}}$$\tilde{x}$.

$\overline{\Gamma}_{c\iota l_{)}}^{C}=\sum_{i,j.k\cdot=1}\frac{\partial x^{i}}{\partial\tilde{\tau}_{\mathrm{t}}^{a}}\backslash \frac{\partial_{l^{j}}}{\partial_{1^{\backslash b}}^{\sim}}n.\frac{\partial\tilde{x}^{c}}{\partial_{\backslash }x^{k}}\Gamma_{j}|k+\sum_{1j=}^{?1}\frac{\partial^{2}x^{j}}{\partial\tilde{x}^{a}\partial\tilde{x}^{b}}.\frac{\partial\tilde{\mathfrak{r}}^{c}}{\partial x^{j}}$(A. 1)