数理解析研究所講究録
1004 巻 1997 年 128-137

128

AFFINE SCALING ALGORITHM FAILSFOR SEMIDEFINITE PROGRAMMING
Masakazu MURAMATSU1
Sophia University
Abstract

paper, we introduce an affine scaling algorithm for semidefiniteIn
programming, and give an example of a semidefinite program such thatthe affine scaling algorithm converges to a non-optimal point. Both ourprogram and its dual have interior feasible solutions, and unique optimal
strict complementarity, and they are nondegenersolutions which
ate everywhere.
$\mathrm{t}\mathrm{h}_{1\mathrm{s}}^{-}$$\mathrm{s}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{S}\Psi$

1Introduction

When both primal and dual problems have interior feasible solutions, semidefinite programming (SDP) has, e.g., both problems have optimal solutions and satisfy
remarkable resemblance with linear programmingstrong duality. In this case, it is known that several interior point methods for LP and their polynomialconvergence analysis can be naturally extended to SDP (Alizadeh [1], Alizadeh, Haeberly and Overton [2],Helmberg, Rendl, Vanderbei and Wolkowicz [9], Jarre [10], Kojima, Shindoh, and Hara [12], Kojima, Shidaand Shindoh [13], Lin and Saigal [14], Lou, Sturm and Zhang [15], Monteiro [16], Monteiro and Zhang [18],Nesterov and Nemirovskii $[19, 20]$ , Nesterov and Todd $[21, 22]$ , Potra and Sheng [23], Sturm and Zhang [24],Vandenberghe and Boyd [28], and Zhang [30] .
:The affine scaling algorithm for LP is originally proposed by Dikin [5], and rediscovered by Barnes [4], andVanderbei, Meketon and Freedman [29] after Karmarkar [11] proposed the first polynomial-time interior point
method . The affine scaling algorithm has been widely implemented and extensively studied, but unlike manyother interior point methods, the question of whether the affine scaling algorithm is polynomially convergent
is still an open problem. The strongest convergence result so far is due to uchiya and Muramatsu [27], whoestablish global convergence of the affine scaling algorithm where the step is taken as a fixed fraction lessthan 2/3 of the whole step to the boundary of the feasible region. Simpler proofs of this global convergence
results can also be found in Monteiro, Tsuchiya and Wang [17], and Saigal [25].
The affine scaling algorithm can also be naturally extended to SDP. Faybusovich [6] investigated the affinescaling vector field for SDP, Faybusovich [7] proposed the discrete version of the affine sclaing algorithm,
and Goldfarb and Scheinberg [8] proved the global convergence of the associated continuous trajectories. So
far, there exists no convergence analysis for the discrete version of the affine scaling algorithm for SDP.
In this paper, we give an instance of SDP such that the affine scaling algorithm converges to a non-optimal
point. We prove that for both the short and the long step version of the affine scaling algorithm, there exists
a region of starting points such that the generated sequence converges to a non-optimal point. Our programand its dual have interior feasible solutions, unique optimal solutions which satisfy strict complementarity,and both programs are nondegenerate everywhere. (For degeneracy in SDP, see Alizadeh, Haeberly, andOverton [3]. )This paper is organized as follows. In Section 2, we introduce the affine scaling algorithm for SDP. In
Section 3, we give an instance of SDP and prove that the affine scaling algorithm converges to a non-optimal
point-In Section 4, we give some concluding remarks.
$(\mathrm{L}\mathrm{P})$$)$$\mathrm{T}\dot{\mathrm{s}}$2

The Affine Scaling Algorithm for SDP

Let $S(n)$ denote the set of$n\cross n$real symmetric matrices. Consider the SDP problem$\min C\cdot X$

subject to $A_{i}\cdot X=b_{i}$ ,17-1 Kioi-cho, Chiyoda-ku, Tokyo 102 Japan. muramatume.sophia.

$i=1,$$\mathrm{a}\mathrm{c}$.jp$\ldots,$$m$,$X\succeq \mathrm{O}$

,

(1)

129

where $C,$ $X,A_{i}\in S(n)$ , the operator denotes the standard inner product in $S(n)$ , i.e.,, and $X\succeq 0$ means that $X$ is positive semidefinite. The induced norm $||X||_{F}=\triangle\sqrt{X\cdot X}=$is called the Frobenius norm. The dual of (1) is$C\cdot X=\triangle \mathrm{t}\mathrm{r}(Cx)=$$\bullet$$\sum_{i},{}_{j}C_{ij}x_{ij}$$\sqrt{\mathrm{t}\mathrm{r}(X^{t}X)}$$\max b^{t}u$subject to $S+ \sum_{i=1}^{m}uiA_{i}=C$ ,$S\succeq \mathrm{O}$.

(2)

We assume that an interior (i.e., positive definite) feasible point of the primal problem (1) exists, nd the$m$ are linearly independent.
matrices
There are several equivalent characterization of the affine scaling direction for . Similarly, we can define
the affine scaling direction for SDP in different ways. Following the original derivation proposed by Dikin[5], here we define the affine scaling direction for SDP by first defining the as sociated dual estimate. For a, we recommend the textbook by Saigal [26] which
detailed motivation of the affine scaling algorithm fordeals with this algorithm extensively.
, we define the dual estimate $(u(x), s(X))$ as the unique solution
Given an interior feasible solutionof the following optimization problem:$.\mathrm{a}$$A_{i},\dot{i}=1,$$\ldots,$$\mathrm{L}\mathrm{P}$$\mathrm{L}\mathrm{P}$$X\succ \mathrm{O}$$\min||X1/2Sx1/2||^{2}p$Solving the$\mathrm{K}\mathrm{a}\mathrm{r}\mathrm{u}\mathrm{s}\mathrm{h}- \mathrm{K}\mathrm{u}\mathrm{h}\mathrm{n}-\mathrm{T}\mathrm{u}\mathbb{C}\mathrm{k}\mathrm{e}\mathrm{r}$subject to $S+ \sum_{i}u_{i}A_{i}=C$ .

(3)

condition, we have the explicit formula$u(X)=c(X)-1(px)$ ,$S(X)=C- \sum iu_{i}(X)Ai$ ,(4)where $G(X)\in S(m)$ and $p(X)\in R^{m}$ are such that $c_{ij(X)}=\mathrm{t}\mathrm{r}(A_{i}XAjX)$ and $p_{j}(X)=\mathrm{t}\mathrm{r}(A_{j}XCX)$ for all$\dot{i},j=1,$$m$ , respectively. Here, the linear independence of theensures that $G(X)$ is invertible. In
fact, we have the following lemma.
$A_{j}’ \mathrm{s}$$\ldots,$

Proposition 1 If

$X\succ \mathrm{O}$, then $G(X)\succ 0$ .

Proof : First, we note that for any matrices$\mathrm{t}\mathrm{r}(M_{2}M_{31}M)=\mathrm{t}\mathrm{r}(M_{\mathrm{s}^{M_{1}M)}}2$

For any $v\in R^{m}$ , we have$M_{1},$ $M_{2},$ $M_{3}$which have appropriate sizes,$\mathrm{t}\mathrm{r}(M_{1}M_{2}M_{3})=$holds.

$v^{t}Gv$$=$$\sum_{i,j}G_{ij}v_{i}vj$$=$$\sum_{i,j}\mathrm{t}\mathrm{r}(A_{i}XAjX)v_{i}vj$$=$$\mathrm{t}\mathrm{r}((\sum_{:}viA_{i})x(\sum_{j}vjAj\rangle X)$$=$$\mathrm{t}\mathrm{r}(X1/2(\sum:v_{i}A_{i})x(\sum_{j}vjA_{j})X1/2)$$=$$||X1/2( \sum iviA_{i})x1/2||_{F}20\geq$,(5)

in which the equality holds if and only if $\sum_{i}v_{i}A_{i}=0$ . The linear independence of$A_{i}’ \mathrm{s}$implies $v=0$ .

$\square$

In (3), any decomposition of $X=RR^{t}$ can be used instead of, because $||R^{t}SR||_{F}^{2}=\mathrm{t}\mathrm{r}(sxSx)=$. Namely, the dual estimate is independent of the choice of decomposition. We. however use.
for notational simplicity.
The affine scaling direction $D(X)$ is defined as$X^{1/2}$$||x^{1/2}sx^{1}/2||_{F}2$$X^{1/2}$$D(X)^{\triangle}=XS(X)x=X(o- \sum ui(xi)A_{i})X$The following proposition gives some properties of $D(X)$ .

.

(6)

130

Proposition 2 We have{7)

$A_{i}\cdot D(X)=0$

for all$\dot{i}=1,$$\ldots,$

$m$

, and
$C\cdot D(X)=||x^{1/2}sX^{1}/2||2F$.

(8)

Proof: The first equation follows from.

$A_{j} \cdot D(X)=\mathrm{t}\mathrm{r}(A_{j}X(C-\sum_{=i1}mu_{i}(X)Ai)X)=pj-\sum_{i=1}^{m}Gjiui(X)=0$(9)$\mathrm{t}\mathrm{r}(.x^{1/2}(C-\sum:ui(x)A_{i})XAjX1/2)=0$(10)

Hence,

holds for all , and we have$j$$C\cdot D(X)$

$=$

$=$

$\mathrm{t}\mathrm{r}(CX(o-\sum_{i}uiAi)X)$$\mathrm{t}\mathrm{r}(x^{1/}2(C-\sum u_{i}Ai)XCx^{1/2})i$$=$$\mathrm{t}\mathrm{r}(X1/2(c-\sum_{:}u_{i}Ai)X(C-\sum_{\check{J}}ujA_{j})x^{1}/2)$$=$$||x^{1/2}(C- \sum.

u_{i}A_{i})x1/2||_{F}^{2}|$

.

(11)

$\square$

For the affine scaling algorithm, there are two major strategies to define the stepsize: short step strategy
and long step strategy.
In the short step strategy, the stepsize parameter is determined with respect to the Dikin’s ellipsoid.
Specifically, the iteration of the short step affine scaling algorithm can be written as(12)$X_{k+1}=X_{k}- \lambda\frac{D(X_{k})}{||X_{kk}^{1//2}s2kX^{1}||F}=X_{k}-\lambda\frac{D(X_{k})}{\sqrt{C\cdot D(X_{k})}}$

is a stepsize parameter. It is easily seen that the condition
ensures that the next pointis feasible.
The long step strategy, which is widely used in practice, means that the next iterate is chosen by moving afixed ratio of the whole step to the boundary of the feasible region in the direction of affine scaling direction,
namely,$X_{k+1}=X_{k}-\mu\rho(x_{k})D(X_{k})$ ,
(13)
where
$\rho(X)=\sup \mathrm{t}\rho>0|x-\rho D(X)\succ 0\}$ ,(14)
and $\mu<1$ is the ratio.
In the following section, we give an instance of (1) for which both the long step and the short step affinescaling algorithm fail to converge to an optimal solution.

where$\lambda\leq 1$$\lambda\leq 1$$X_{k+1}$

3

An Example

Consider the following SDP problem,$\min\cdot X$ subject to $\cdot X=2$ ,$X\succeq 0$

,

(15)

131

and its dual$\max 2u$ subject

to$S+u=$,$S\succeq 0$

,

(16)

where $X,$ $S\in S(2)$ and $u\in R$ . We note that both the primal and dual have interior feasible solutions. By
defining$X=$ ,(17)

it is easy to see that the problem (15) is equivalent to$\min x+y$ subject to $x\geq 0$ ,$y\geq 0$,$xy\geq 1$

,

(18)

whose optimal solution is $(x, y)=(1,1)$ . Hence, it can also be easily verified that

$X^{*}=$ ,and $(u^{*}, S^{*})=(1,$

$)$

(19)

are the unique optimal solutions of the primal (15) and the dual (16), respectively, that the optimal values
coincide, and thatandsatisfy strict complementarity, namely, we can decompose
andas$X^{*}$$(u^{*}, S^{*})$$X^{*}$$X^{*}=QQ^{t}$ , and $S^{*}=QQ^{t}$ ,
where
$Q=($

$-1/\sqrt{2}1/\sqrt{2}$$1/\sqrt{2}1/\sqrt{2}$is the orthogonal matrix whose columns are the eigenvectors of
eigenvalues.
We can calculate the dual estimates by (4) as follows.
$G(X)$$=$$2(xy+1)$ ,$p(X)$$=$$2(x+y)$ ,$u(.X)$$=$$G(X)^{-1}p(x)= \frac{x+y}{xy+1}$$S(X)$$=$$(u^{*}, S^{*})$

(20)

)

(21)

and

$X^{*}$$S^{*}$

corresponding to each nonzero

(22)
(23)

,

$-u(X)=$

(24)

.

(25)

By a straightforward calculation, we have the affine scaling direction$D(X)= \frac{xy-1}{xy+1}$ .

(26)

Hence an iteration of the general affine scaling algorithm can be written as

for some scaler$\alpha^{k}>0$. Thus we have$x^{k+1}$$y^{k+1}$$=$$x^{k}-\alpha^{k}((x^{k})2-1)$$=$$y^{k}-\alpha^{k}((y^{k})2-1)$

,
,

(28)
(29)

which is the expression of the affine scaling algorithm in the $(x,y)$ -space. In other words, the sequence
generated by the affine scaling algorithm for the SDP (15) corresponds to the sequence $\{(x^{kk}, y)\}$ generatedby (28) and (29).
Let us define $\mathcal{F}=\triangle\{(x, y)|xy>1, x<1, y>1\}$. We have the following proposition.
$\{X_{k}\}$132

Proposition 3 Assume that we do one iteration (28) and (29) of the affine scaling algorithm from.
to produce the next iterate $(x^{+},y^{+})$ . Then we have $x^{+}\geq x,$ $y^{+}\leq y$ , and$(x, y)\in \mathcal{F}$$(x^{+},y^{+})\in \mathcal{F}$

Proof: The former relations are obvious from (28), (29) ,$\mathrm{a}\mathrm{n}\mathrm{d}$the definition of F. Lett.ing$x(\alpha)$$=$$x-\alpha(x^{2}-1)$$y(\alpha)$$=$$y-\alpha(y^{2}-1)$

,
,

(30)
(31)

below we prove theone by showing that if $y(\alpha)=1$ then $x(\alpha)<1$ , which implies that $x(\alpha)<1$ at theboundary.
From $y(\alpha)=1,$ $\alpha=1/(y+1)$ follows. Substituting this relation into (30), we have
$1\mathrm{a}s\mathrm{t}$$x( \alpha)-1=x-1-\frac{(x^{2}-1)}{y+1}$

,

(32)

and
$\frac{1-x(\alpha)}{1-x}=1-\frac{(x+1)}{y+1}=\frac{y-x}{y+1}>0$

Therefore, the proposition follows.

.

(33)

$\square$Corollary 4 If the initial point $(x^{0},y)0$ is contained in $F$ , the sequence generated by affine scal.ing algoconverges regardless of stepsize.

Proof:

is monotonically increasing and bounded above by 1, thus has a limit point. Similarly,
is monotonically decreasing and bounded below by 1. Thusalso has a limit point, and$\{x^{k}\}$$\{y^{k}\}$$\{(x^{k}, y^{k})\}$$\{y^{k}\}$converges.

$7^{\cdot}ithm$$\square$Proposition 5 Let $(x, y)\in F$ andThen we have$(x^{+}, y^{+})$

be the next iterate of the affine scaling algo$\frac{x^{+}y^{+}-1}{xy-1}=1-\alpha(x+y)-\alpha\frac{(1-X^{2})(y2-1)}{xy-1}2<1$$r\dot{\mathrm{u}}thm$

with$\alpha^{k}=\alpha$

.

.

(34)

This relation follows from (28) and (29) by a straightforward calculation, thus we omit the proof.
Now we consider the long step affine scaling algorithm. Note that if the left hand side of (34) is , then$(x^{+},y^{+})$ is on the boundary of the feasible region. Let
be the positive solution of$0$$\sigma(x,y)$$1- \sigma(_{X}+y)-\sigma^{2}\frac{(1-X^{2})(y2-1)}{xy-1}=0$

.

(35)

Noting that$\sigma(x, y)$(36)

is the whole step of the way to the boundary of the feasible region in the $(x,y)$ -space, we see that the iterationof the long step affine scaling algorithm can be written as follows:,,$x^{k+1}-$$=$$x^{k}-\mu\sigma(x, ykk)((x)k2-1)$$y^{k+1}$$=$$y^{k}-\mu\sigma(x^{kk},y)((y^{k})^{2}-1)$

where $\mu<1$ is a stepsize parameter. We denote$\sigma(x^{k}, y^{k})$by$\sigma^{k}$

(37)
(38)

in what follows.

Theorem 6 Assume that we use the long step affine scaling $algo\dot{\eta}thm$ with stepsize $\mu<1$ for (15). Fix any
positive number , and choose the initial point
to satisfy$(x^{0},y)0\in \mathcal{F}$$\epsilon$$\sqrt{x^{0}y^{0_{-}}1}<\frac{\mu}{2}\sqrt{\frac{1-(x0)^{2}}{(y^{0})^{2}-1}}(y^{0}-1-\epsilon)$

Then the sequence$\{(x^{k},y^{k})\}$

converges to a non-optimal point.

.

(39)

133

Note that the inequality (39) is always possible since for fixed, while the right hand side remains positive.

$\mu$$\epsilon,$, and$y^{0}$, the left hand side goes to

$0$

as

$x\downarrow 1/y^{0}$

Proof: Assume by contradiction that $(x^{k},y^{k})arrow(1,1)$ , which is the optimal solution. Then $y^{k}<1+\epsilon$ for
sufficiently large . Let
be the iteration number such that $y^{L}\geq 1+\epsilon$ and $y^{L+1}<1+\epsilon$. Sinceismonotonically decreasing, such is unique.
In view of (34) with, and (35), we have
$k$

$L$

$y^{k}$$L$$\alpha=\mu\sigma^{k}$$\frac{x^{k1}y^{k}++1-1}{x^{k}y^{k}-1}$$=$$1-\mu\sigma^{k}(x+ykk)-\mu 2(\sigma^{k})^{2_{\frac{(1-(_{X^{k}})2)((y^{k})^{2}-1)}{x^{k}y^{k}-1}}}$$=$$1-\mu\sigma^{k}(Xk+yk)-\mu^{2}(1-(_{X^{k}}+y^{k})\sigma^{k})$$=$$1-\mu^{2}-(_{X}k+yk)\mu\sigma(k1-\mu)$$<$$1-\mu^{2}$

.

(40)

Furthermore from (35), it follows that$( \sigma^{k})^{2}=\frac{x^{k}y^{k}-1}{(1-(_{X^{k}})2)((y^{k})^{2}-1)}(1-(x^{kk}+y)\sigma^{k})\leq\frac{x^{k}y^{k}-1}{(1-(_{X^{k}})2)((y^{k})2-1)}$

,

(41)

and
$\sigma^{k}\leq\sqrt\frac{x^{k}y^{k}-1}{(1-(_{X^{k}})2)((y^{k})^{2}-1)}$

.

(42)

Now we have$y^{0}-yL+1$$=$$\sum_{k=0}^{L}(y-ky)k+1$$=$$\mu\sum_{k=0}^{L}\sigma^{k}((y^{k})2-1)$$\leq$$\mu\sum_{k=0}\sqrt{\frac{(x^{k}y^{k}-1)((y^{k})^{2}-1)}{1-(x^{k})^{2}}}L$$\leq$$\mu\sqrt{\frac{(y^{0})^{2}-1}{1-(x0)^{2}}}\sum_{k=0}^{L}\sqrt{x^{k}y^{k}-1}$$\leq$$\mu\sqrt{\frac{((y^{0})2-1)(_{X}0_{y^{0_{-}})}1}{1-(x^{0})2}}\sum_{k=0}^{L}\sqrt{(1-\mu^{2})}^{k}$$\leq$$\mu\sqrt{\frac{((y^{0})2-1)(_{X}0_{y^{0_{-}})}1}{1-(X^{0})2}}\sum_{k=0}^{L}(1-\frac{\mu^{2}}{2})^{k}$$\leq$$\frac{2}{\mu}\sqrt\frac{((y^{0})2-1)(_{X}0_{y^{0_{-}})}1}{1-(x^{0})2}$

.

(43)

Due to the choice (39) of the initial point, we have$y^{0}-yL+1\leq y^{0}-1-\epsilon$,

which contradicts the relation that $y^{0}-y^{L}+1>y^{0_{-1-}}\epsilon$ . Therefore, the limit point is not optimal.

(44)$\square$Next we turn to the short step affine scaling algorithm. From (12) and (26), the iteration of the shortstep affine scaling algorithm can be written as follows:$x^{k+1}$$y^{k+1}$

$=$

$=$

,
$y^{kkk}-\lambda\theta(x, y)((y^{k})^{2}-1)$ ,$x-k\lambda\theta(Xk, y)k((Xk)2-1)$

(45)
(46)

134

$.\mathrm{w}$here$\theta(x, y)=\sqrt\frac{xy-1}{(xy+1)(X^{2}+y-22)}$

We denote$\theta(x^{k}, y^{k})$by$\theta^{k}$

.

(47)

in what follows.

Theorem 7 Assume that we use the short step affine scaling$\eta>4$ ,$algo\dot{\mathcal{H}}thm$with stepsize$\mathcal{G}\langle\eta)^{\triangle}=\{(_{X}, y.)\in \mathcal{F}|xy\leq 2, \eta\geq y\geq 4\}$Choose the initial point$(x^{0}, y)0\in \mathcal{G}(\eta)$$\{(x^{k}, y^{k})\}$.

for (15). Let for(48)

to satisfy$\sqrt{x^{0}y^{0_{-}}1}<\frac{15\sqrt{7}\lambda}{4\eta^{4}}(y^{0_{-}}4)$

Then the sequence$\lambda\leq 1$

.

(49)

converges to a non-optimal point.

Note that the inequality (49) is always possible since for fixed
hand side by choosing appropriate .

$\lambda$$\eta,$, and$y^{0}$, we can arbitrarily reduce the left

$x^{0}$

Proof: Assume by contradiction that
3 and 5, the sequence must be in, which is the optimal solution. Then by Propositions
in finite number of iterations. Let be
is monotonically decreasing,and $(x^{L+1L+1},y)\in \mathcal{H}$ . Since$(x^{k}, y^{k})arrow(1,1)$$\mathcal{H}=\triangle\{(x, y)\in \mathcal{F}|xy\leq 2, y<4\}$$L$

the iteration number such thatand are disjoint, such is unique.
and, we have
From Proposition 5, substituting$(x^{L}, y^{L})\in \mathcal{G}(\eta)$$\mathcal{G}(\eta)$$y^{k}$$L$$\mathcal{H}$$\alpha=\lambda\theta^{k}$$\frac{x^{k1}y^{k}++1-1}{x^{k}y^{k}-1}$$=$$\leq$

When$(x^{k}, y^{k})\in \mathcal{G}(\eta)$$1- \lambda\theta^{k}(X^{k}+yk)-\lambda^{2}(\theta k)^{2}\frac{(1-(_{X^{k}})2)((y^{k})^{2}-1)}{x^{k}y^{k}-1}$$1- \lambda^{2}\frac{(1-(_{X^{k}})2)((y^{k})^{2}-1)}{(x^{k}y^{k}+1)((X)k2+(y^{k})2-2)}$

(50)

.

, we see that,$(y^{k})^{2}-1\geq 15$,$1-(x^{k})^{2}\geq 3/4$

$x^{k}y^{k}+1\leq 3$,$(x^{k})^{2}+(y^{k})^{2}-2\leq\eta^{2}-1\leq\eta^{2}$

.

(51)

Substituting these relations into (50), we have for $k\leq L$ ,

.

(52)

$\frac{x^{k+1}y^{k1}-+1}{x^{k}y^{k}-1}\leq 1-\lambda^{2}\frac{45/4}{3\eta^{2}}=1-\frac{15\lambda^{2}}{4\eta^{2}}$Now we have$y^{0}-y^{L+}1$$=$$\sum_{k=0}^{L}(y-ky)k+1$$=$$\lambda\sum_{0k=}^{L}\sqrt\frac{x^{k}y^{k}-1}{(x^{k}y^{k}+1)((X)k2+(y^{k})2-2)}((y)k2-1)$$\leq$$\lambda\sum_{k=0}^{L}\frac{\sqrt{x^{k}y^{k}-1}}{\sqrt{28}}\eta 2$$\leq$$\leq$(Because$(x^{k},$ $y^{k})\in \mathcal{G}(\eta)\subset F.$$\frac{\lambda\eta^{2}\sqrt{x^{0}y^{0}-1}}{2\sqrt{7}}\sum_{k=0}^{L}(\sqrt{1-\frac{15\lambda^{2}}{4\eta^{2}}})^{k}$$\frac{\lambda\eta^{2}\sqrt{x^{0}y^{0_{-}}1}}{2\sqrt{7}}\sum_{k=0}^{L}(1-\frac{15\lambda^{2}}{8\eta^{2}})^{k}$(Use (52))

)

135

$\leq$$\frac{\lambda\eta^{2}\sqrt{x^{0}y^{0_{-}}1}}{2\sqrt{7}}\frac{8\eta^{2}}{15\lambda^{2}}$$=$$\frac{4\eta^{4}\sqrt{x^{0}y^{0_{-}}1}}{15\sqrt{7}\lambda}$

.

(53)

Due to the choice (49) of the initial point, we have$y^{0}-yL+1<y^{0}-4$ ,which contradicts the relation that $y^{0}-yL+1\geq y^{0}-4$ because
optimal.

4(54)$y^{L+1}\in \mathcal{H}$. Therefore, the limit point is not$\square$Concluding Remarks

In our example, the dual estimates also converge to an infeasible point. In fact, we have from (24),$\lim_{karrow\infty}u(x^{kk},y)=\lim_{karrow\infty}\frac{x^{k}+y^{k}}{x^{k}y^{k}+1}=\frac{x^{\infty}+y^{\infty}}{x^{\infty}y^{\infty}+1}$

and by noting that$x^{\infty}y^{\infty}=1$

,

(55)

, we have,$\frac{x^{\infty}+y^{\infty}}{x^{\infty}y^{\infty}+1}=\frac{x^{\infty}+1/x\infty}{2}>1$(56)

where theinequality follows from. Hence, we have
, which implies that the limitof the dual estimates is infeasible. Note that the dual estimate is continuous everywhere on the feasible
region. In, nondegeneracy assumption implies this condition, which produces a much simpler proof of
the global convergence of the affine scaling algorithm. Our example however, shows that this condition is
not effective in proving the global convergence of the affine scaling algorithm for SDP.
By choosing an initial point to satisfy (39) of Theorem 6 in the long step strategy or (49) of Theorem
7 in the short step strategy, we can easily do a numerical experience such that the sequences of the affinescaling algorithm converge to a non-optimal point. For example, in the short step affine scaling algorithmwith stepsize $\lambda=0.5$ , the sequence generated from $(x^{00}, y)=$ (0.20001, 5.0) converges to approximately$1\mathrm{a}s\mathrm{t}$$x^{\infty}<1$$u(x^{\infty}, y^{\infty})>1$$\mathrm{L}\mathrm{P}$(0.2078065619, 4.8121675791), a non-optimal point.
Even though our example shows that the global convergence from arbitrary starting point is impossible,
it may still be possible to prove global convergence from well-chosen starting points, or by allowing variable
stepsizes.

Acknowledgements
The author wishes to thank Prof. Takashi Tsuchiya, Prof. Renato Monteiro, and Prof. Shinji Mizuno of theInstitute of Statistical Mathematics for having many helpful conversations with the author, and for pointing
out several improvements of the first draft of this paper.
This work was partially supported by the Grant-in-Aid for Encouragement of Young Scientists of Ministryof Education, Science, Sports and Culture of Japan, and the Grant-in-Aid for Developmental Scientific
Research (B) of Ministry of Education, Science, Sports and Culture of Japan.

References[1] F. Alizadeh, Interior point methods in semidefinite programming ith application to combinatorial.
optimization, SIAM J. Optim. 5, (1995) 13-51.
[2] F. Alizadeh, J. P. A. Haeberly, and M. L. Overton, Primal-dual interior-point
methods.for semidefinite
programming, Technical report, (1994).

136[3] F. Alizadeh, J. P. A. Haeberly, and M. L. Overton, Complementarity and nondegeneracy in semidefinite
programming, Technical report, (1995).
[4] E. R. Barnes : A Variation on Karmarkar’s Algorithm for Solving Linear Programming Problems.
Mathematical Programming, Vol. 36, (1986) 174-182.
[5] I. I. Dikin, Iterative solution of problems of linear and quadratic programming, Sov. Math. Doklady 8,(1967) 674-675.
[6] L. Faybusovich, On a matrix generalization of affine-scaling vector fields, SIAM J. Mat. Anal. Appl. 16,
No. 3, (1995) 886-897.
[7] L. Faybusovich, Dikin’s algorithm for matrix linear programming problems, Lecture notes in control
and information sciences, J. Henry and J. Pavon editors, Springer-Verlag, Vol. 197, (1994) 237-247.
[8] D. Goldfarb and K. Scheinberg, Interior point trajectories in semidefinite programming, Technical report, (1996).
[9] C.
lmberg, . Rendl, R. J. Vanderbei, and H. Wolkowicz, An interior-point method for semidefinite
programming, SIAM J. Optim. 6, (1996) 342-361.
$\mathrm{H}\dot{\mathrm{e}}$$\dot{\mathrm{F}}$[10] F. Jarre, An interior-point method for minimizing the maximum eigenvalue of a linear combination of
matrices. SIAM J. Cont. and Optim. 31, (1993) 1360-1377.

[11] N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica 4, No. 4,(1984) 373-395.
[12] M. Kojima, S. Shindoh and S. Hara, Interior point methods for the monotone semidefinite linear complementarity problems, Research Report #282, Dept. of Mathematical and Computing Sciences, Tokyo
Institute of Technology, Oh-Okayama, Meguro, Tokyo 152, Japan, (1994, Revised 1995).
[13] M. Kojima, M. Shida and S. Shindoh, Local convergence of predictor-corrector infeasible-interior-point
algorithms for SDPs and SDLCPs, Research Report #B-306, Dept. of Mathematical and Computing
Sciences, Tokyo Institute of Technology 2-12-1 Oh-Okayama, Meguro-ku, Tokyo 152, Japan, (1995).
[14] C-J. Lin and R. Saigal, A predictor-corrector method for semi-definite programming, Working paper,
Dept. of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, Michigan
48109-2177, (1995).

[15] Z-Q. Lou, J. F. Sturm and S. Zhang, Superlinear convergence of a symmetric primal-dual path-following
algorithms for semidefinite programming, Working paper, (1996).
[16] R. D. C. Monteiro, Primal-dual path-following algorithms for semidefinite programming, Working paper,(1995). To appear in SIAM J. Optim.
[17] R. D. C. Monteiro, T. Tsuchiya and Y. Wang, A simplified global convergence proof of the affine scaling
algorithm, Ann. Oper. Res. 47, (1993) 443-482.
[18] R. D. C. Monteiro, and Y. Zhang, A unified analysis for a class of path-following primal-dual interiorpoint algorithms for semidefinite programming, Working Paper, (1996).

[19] Y. E. Nesterov and A. S. Nemirovskii. Optimization over positive semidefinite matrices: Mathematicalbackground and user’s manual. Technical report, Central Economic&Mathematical Institute, USSR
Acad. Sci. Moscow, USSR, (1990).
[20] Yu. E. Nesterov and A. Nemirovskii, Interior-point Polynomial Algorithms in Convex Programming,
SIAM, Philadelphia, PA, USA.
[21] Y. E. Nesterov and M. J. Todd, Self-scaled barriers and interior-point methods for convex programming,
Technical Report 1091, School of Operations Research and Industrial Engineering, Cornell University,
Ithaca, New York, 14853-3801, (1995).

137[22] Y. E. Nesterov and M. J. Todd, Primal-dual interior-point methods for self-scaled cones, Technical
Report 1125, School of Operations Research and Industrial Engineering, Cornell University, Ithaca,
New York, 14853-3801, (1995).

[23] F. A. Potra and R. Sheng, A superlinearly convergent primal-dual
algorithm
for semidefinite programming. Reports on Computational Mathematics, No.78, Department of Mathematics, The University of Iowa, (1995).
$\mathrm{i}\mathrm{n}\mathrm{f}\mathrm{e}\mathrm{a}\mathrm{s}\mathrm{i}\mathrm{b}\mathrm{l}\mathrm{e}- \mathrm{i}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{i}_{0}\mathrm{r}-\mathrm{P}^{\mathrm{o}}\mathrm{i}\mathrm{n}\mathrm{t}$[24] J. F. Sturm and S. Zhang, Symmetric primal-dual path-following algorithms for semidefinite program, Ecometric Institute, Erasmus University Rotterdam, The Netherlands, (1995).
ming, Report$9554/\mathrm{A}$[25] R. Saigal, A simple proof of primal affine scaling method, Technical Report, Department of Industrial
and Operations Engineering, University of Michigan, Ann Arbor, MI, USA, (1993). (To appear inAnn. Oper. Res.)[26] R. Saigal, Linear programming: A modern integrated analysis, Kluwer Academic Publishers, USA,
(1996).

[27] T. Tsuchiya and M. Muramatsu, Global convergence of along-step affine scaling algorithm for degeneratelinear programming problems, SIAM J. Optim. 5, No. 3, (1995).
[28] L. Vandenberghe and S. Boyd, A primal-dual potential reduction method for problems involving matrix
inequalities, Mathematical Programming Vol.69, (1995) 205-236.
[29] R. J. Vanderbei, M. S. Meketon and B. A. Freedman, A Modification of Karmarkar’s Linear Programming Algorithm. Algorithmica, Vol. 1, (1986) 395-407.
[30] Y. Zhang, On extending primal-dual interior-Point algorithms from linear programming to semidefi, University of Maryland Baltimore
nite programming, Technical Report TR95-20, Dept. ofCounty, Baltimore, MD 21228, USA, (1995).
$\mathrm{M}\mathrm{a}\mathrm{t}\mathrm{h}/\mathrm{S}\mathrm{t}\mathrm{a}\mathrm{t}$