数理解析研究所講究録
1004 巻 1997 年 138-152

138

Polynomiality of Primal-Dual Algorithms for
Semidefinite Linear Complementarity Problems Basedon theFamily of Directions$\mathrm{K}\mathrm{o}\mathrm{j}\mathrm{i}\mathrm{m}\mathrm{a}-\mathrm{S}\mathrm{h}\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{o}\mathrm{h}- \mathrm{H}\mathrm{a}\Gamma \mathrm{a}$Renato$\mathrm{D}.\mathrm{C}$. Monteiro*

Takashi$\mathrm{T}\mathrm{s}\mathrm{u}\mathrm{C}\mathrm{h}\mathrm{i}\mathrm{y}\mathrm{a}\dagger$

August 6, 1996

Abstract

Kojima, Shindoh and Hara proposed a family of search directions for the semidefinite linear
complementarity(SDLCP) and established polynomial convergence of a feasible shortstep path-following algorithm based on a particular direction of their family. The question ofwhether polynomiality could be established for any direction of their family thus remained an
open problem. This paper answers this question in the affirmative by establishing the polynomiality of primal-dual interior-point algorithms for SDLCP based on any direction of the
Kojima, Shindoh and Hara family of search directions. We show that the polynomial iterationcomplexity bounds of two well-known algorithms for linear programming, namely the short-step
path-following algorithm of Kojima et al. and Monteiro and Adler, and the predictor-corrector
algorithm of Mizuno et al., carry over to the context of SDLCP.
$\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{b}\grave{\mathrm{l}}\mathrm{e}\mathrm{m}$keywords: Semidefinite programming, interior-point methods, polynomial complexity, pathfollowing methods, primal-dual methods.
AMS 1991 subject classification:.
$65\mathrm{K}05,90\mathrm{C}25,90\mathrm{c}30$

1Introduction

Several authors have discussed generalizations of interior-point algorithms for linear programming
to the context ofprogramming (SDP) and the more general semidefinite linear
complementarity problem (SDLCP). The landmark work in this direction is due to Nesterov andNemirovskii $[19, 20]$ where a general approach for using interior-point methods for solving convex
programs is proposed based on the notion of self-concordant functions. (See their book [22] fora comprehensive treatment of this subject.) They show that the problem of minimizing a linear
function over a convex set can be solved in “polynomial time” as long as a self-concordant barrier
function for the convex set is known. In particular, Nesterov and Nemirovskii show that linear$(\mathrm{L}\mathrm{P})$$\mathrm{s}\mathrm{e}\mathrm{m}\mathrm{i}\mathrm{d}\mathrm{e}\mathrm{f}\mathrm{f}\mathrm{i}\dot{\mathrm{u}}\mathrm{t}\mathrm{e}$*School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332, USA.

( -mail: monteiro@isye.gatech.edu). The work of this author was based on research supported by the Office of$\mathrm{e}$Naval Research under grant $\mathrm{N}00014- 94- 1- 0340$ .
\dagger The Institute of Statistical Mathematics, 4-6-7 Minami-Azabu, Minato-Ku, Tokyo, 106, Japan. (e-mail:tsuchiya@sun312.ism.ac.jp). This research is supported in part by the Grant-in-Aid for Encouragement of Young
Scientists (A) 08780227 of the Ministry of Science, Education and Culture of Japan.

139

programs, convex quadratic programs with convex quadratic constraints, and semidefinite programs
all have explicit andily computable self-concordant barrier functions, and hence can be solved$\mathrm{e}\mathrm{a}s$in “polynomial time”. On the other hand, Alizadeh [1] extends Ye’s projective potential reduction
algorithm [30] for LP to SDP and argues that many known interior point algorithms for LP canalso be transformed into algorithms for SDP in a mechanical way. Since then many authors haveproposed interior-point algorithms for solving the SDP problem and SDLCP, including Alizadeh,
Haeberly and Overton [2], Reund [3], Helmberg, Rendl, Vanderbei and Wolkowicz [4], Jarre [5],Kojima, Shida and Shindoh [8], Kojima, Shindoh and Hara [10], Lin and Saigal [11], Luo, Sturm andZhang [12], Monteiro $[14, 15]$ , Monteiro and Zhang [18], Nesterov and Nemirovskii [21], Nesterov
and Todd $[24, 23]$ , Potra and Sheng [25], Sturm and Zhang [26], Tseng [28], Vandenberghe and Boyd[29], and Zhang [31]. Most of these more recent works are concentrated on primal-dual methods.
The first algorithms for SDP and SDLCP that are extensions of primal-dual algorithms for, such as the long-step path-following algorithm of Kojima, Mizuno and Yoshise [7], the shortstep path-following algorithm of Kojima, Mizuno and Yoshise [6] and Monteiro and Adler $[16, 17]$ ,and the predictor-corrector algorithm of Mizuno, Todd and Ye [13], use one of the following three
search directions: i) the Alizadeh, Haeberly and Overton (AHO) direction proposed in [2], \"u)thedirection independently proposed by Kojima, Shindoh and Hara [10] andHelmberg, Rendl, Vanderbei and Wolkowicz [4], and later rediscovered by Monteiro [14] via aformulation based on a scaling and symmetrization of the Newton equation, and iii) the Nesterov
and Todd
direction introduced in $[23, 24]$ .
To unify the above directions, two family of search directions have been proposed in the literature. The first family, proposed by Kojima, Shindoh and Hara [10], is known to contain theand NT directions but not the AHO direction. The second family, namely theMonteiro and Zhang
family, formally introduced by Zhang [31] to generalize a symmetricformulation of thedirection proposed by Monteiro [14], contains all three search
directions above. Proofs that the NT direction is a member of both the KSH family and the
MZ family can be found in Kojima, Shida and Shindoh [9] and Todd, Toh and T\"utiinc\"u [27],respectively.
Unified convergence analyses for the MZ family have been given by Monteiro and Zhang [18]and Monteiro [15]. In the paper [18], iteration-complexity bounds are derived for long-step primaldual path-following methods based on a subclass of the MZ family of search directions, whichcontain theand NT directions but not the AHO direction.
particular, it isshown that the corresponding algorithms based on theand NT directions perform
anditerations, respectively, to reduce the duality gap by a factor of at least $2^{-O(L)}$ .
(The $O(n^{3/2}L)$ iteration-complexity bound for the
direction was in fact obtained
earlier by Monteiro [14].) More recently, Monteiro [15] proves the polynomiality of short-step
path following algorithms and Mizuno-Todd-Ye
type algorithms based on any
member of the MZ family, thus obtaining as a by-product the important result that Frobenius-norm
type algorithms based on the AHO direction are polynomial.
Unified analysis for the KSH family of search directions are provided in Kojima, Shindoh andHara [10]. This paper deals with primal-dual path-following algorithms for the semidefinite linear
complementarity problem based on the KSH fammily of search directions and establishes the polynomiality of. 1) a feasible short-step path-following method based on a special member of theirfamily, namely the
direction and; 2) a (feasible and infeasible) potential reduction
algorithm based on any search direction of their family. The question of whether polynomiality$\mathrm{L}\mathrm{P}$$\mathrm{K}\mathrm{S}\mathrm{H}/\mathrm{H}\mathrm{R}\mathrm{v}\mathrm{W}/\mathrm{M}$$(\mathrm{N}\mathrm{T})$$\mathrm{K}\mathrm{S}\mathrm{H}/\mathrm{H}\mathrm{R}\mathrm{v}\mathrm{W}/\mathrm{M}$$(\mathrm{M}\mathrm{Z})$$\mathrm{K}\mathrm{S}\mathrm{H}/\mathrm{H}\mathrm{R}\mathrm{V}\mathrm{W}/\mathrm{M}$$\mathrm{K}\mathrm{S}\mathrm{H}/\mathrm{H}\mathrm{R}\mathrm{V}\mathrm{W}/\mathrm{M}$$\mathrm{s}$$\mathrm{h}$$\mathrm{K}\mathrm{S}\mathrm{H}/\mathrm{H}\mathrm{R}\mathrm{v}\mathrm{W}/\mathrm{M}$$\mathcal{O}(n^{3/2}L)$$\mathcal{O}(nL)$$\mathrm{K}\mathrm{S}\mathrm{H}/\mathrm{H}\mathrm{R}\mathrm{v}\mathrm{W}/\mathrm{M}$$\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{d}\mathrm{i}\mathrm{C}\mathrm{t}_{0}\mathrm{r}-\mathrm{C}\mathrm{o}\mathrm{r}\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{t}_{0}\mathrm{r}$$\cdot$$\mathrm{K}\mathrm{S}\mathrm{H}/\mathrm{H}\mathrm{R}\mathrm{V}\mathrm{W}/\mathrm{M}$140

of algorithm 1) can be established for any direction of the KSH family was thus left as an open
problem.
In this paper, we answer the above question in the affinnative. Using new techniques recently
proposed by Monteiro [15], we prove the polynomial convergence of two feasible primal-dual algorithms based on a narrow (or Frobenius norm) neighborhood of the central path, namely: ashort-step path-following method which is an extension of the LP method of Kojima, Mizuno andYoshise [6] and Monteiro and Adler $[16, 17]$ , and a predictor-corrector algorithm similar to the LP
one of Mizuno, Todd and Ye [13].
This paper is orgamized as follows. In Section 2, we introduce the SDLCP problem and motivate
the search directions used by the algorithms studied in this paper. In Section 3, we state and prove
the techmical results used in the polynomial convergence analysis of the algorithms of Section 4.
In Section 4, we establish the polynomiality of two primal-dual feasible algorithms: the short-step
path-following algorithm in Subsection 4.1 and the predictor-corrector algorithm in Subsection 4.2.
We give some concluding remarks in Section 5.
$-$

Notation and terminology

1.1

The following notation is used throughout the paper. The superscript denotes transpose.
denotes the p–dimensional Euclidean space. The set of all
matrices with real entries is denotedby. The set of all symmetricmatrices is denoted by . For $Q\in S^{p},$meansis positive semidefinite andmeans is positive definite. The trace of a matrix
is denoted by Tr. For a matrix
with all real eigenvalues, we denoteits eigenvalues by, and its smallest eigenvalue by. Given $P$ and in, the inner product between them in the vector spaceis defined as $P$.
The Euclidean norm and its associated operator norm are both denoted by; hence,$\max_{||u|}|=1||Qu||$ for any. The Frobenius norm ofis.
anddenote the set of all matrices inwhich are positive semidefinite and positive definite,
respectively.
denote the set of all skew-symmetric matrices in. Sinceand$V=0$ for every $U\in S^{p}$ and, it follows thatis the orthogonal complement ofwith respect to the inner product .
$T$$\Re^{p}$$p\mathrm{x}q$$\Re^{P^{\cross q}}$$S^{p}$$p\mathrm{x}p$$Q\in\Re^{p\cross}P$$Q \equiv\sum_{i=1}^{n}Q_{i}i$$Q\in\Re^{p\mathrm{x}p}$$\lambda_{i}[Q],\dot{i}=1,$ $\ldots,p$$Q$$\lambda_{\min}[Q]$$\Re^{p\cross q}$$\Re^{p\cross q}$$\bullet$$Q\equiv r_{\mathrm{b}}P^{T}Q$$||Q||\equiv$$||\cdot||$$Q\in\Re^{p\cross p}$$Q\in\Re^{p\cross p}$$||Q||_{F}\equiv$$(Q \bullet Q)^{1/2}$$S_{+}^{p}$$S^{p}$$S_{++}^{p}$$\Re^{p\cross p}$$S_{\perp}^{p}$$U\bullet$$Q$$Q\succeq \mathrm{O}$$Q$$Q\succ \mathrm{O}$$V\in S_{\perp}^{p}$$S^{p}+S_{\perp}^{p}=\Re^{p\cross p}$$S^{p}$$S_{1}^{p}$$\bullet$2

Description of the problem and preliminary discussion

In this section, we introduce the semidefinite linear complementarity problem and the assumptions
made in our presentation. We also describe the family of search directions introduced by Kojima,
Shindoh and Hara [10] and give a short proof for the existence and umiqueness of these
Let be an affine subspace of
whose dimension is $n(n+1)/2$ . Let$\mathrm{d}\mathrm{i}\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{i}_{\mathrm{o}\mathrm{n}\mathrm{S}}\vee\cdot$$\mathcal{L}$$S^{n}\mathrm{x}S^{n}$,$\mathcal{L}_{+}$$\equiv$$\mathcal{L}\cap(s_{+}^{n}\cross S_{+}n)$$\mathcal{L}_{++}$$\equiv$$\mathcal{L}\cap(s^{n}S^{n}++^{\mathrm{x}}++)$.

In this paper, we deal with the semidefinite linear complementarity problem (SDLCP) of finding apair (X, ) such that$S$

(X, $S$ )$\in \mathcal{L}_{+}$

Throughout our presentation, we assume that,

$X\bullet s=0$

.

(1)

141

[A1]

$\mathcal{L}$[A2]

is monotone, that is $(X_{1}-X_{2})$for any$(S_{1}-S_{2})\geq 0$$\bullet$$(x_{1}, s_{1})\in \mathcal{L}$and$(x_{2}, s_{2})\in \mathcal{L}$.

is onempty:$\dot{\mathrm{n}}$$\mathcal{L}_{++}$

This problem is a generalization of SDP which has numerous applications in systems and control
theory and combinatorial optimization. Given $C\in S^{n}$ andfor$\ldots,m$ , a
primal-dual pair of SDP problems is defined as$(A_{i}, b_{i})\in S^{n}\mathrm{x}\Re$$(P)$$\min\{C \bullet X : A_{i} \bullet X=b_{i}, i=1, \ldots,m, X\succeq \mathrm{O}\}$$(D)$$\max\{b^{\tau_{y}} :\sum^{m}y_{i}Aii=1+S=C, S\succeq \mathrm{O}\}$$\dot{i}=1,$

,

,

where
. Under the assumption that problems $(P)$ and $(D)$ have interior feasible
solutions, that is feasible solutions $X$ andand $S\succ 0$ , it is known that(X, ) is a solution of (1) with$b\equiv(b_{1}, \ldots, b_{m})^{T}$$(S,y)\mathrm{s}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{S}\Phi^{\mathrm{i}}\mathrm{n}\mathrm{g}X\succ 0$$S$$\mathcal{L}=${ $(X,$$S)\in S^{n}\mathrm{x}S^{n}$:$A_{i}$$\bullet$$X=b,$ $\sum^{m}i=1y_{i}Ai+S=C$ for some $y\in\Re^{m}$ },if and only if (X, $S,y$ ) is a solution of $(P)$ and $(D)$ for some $y\in\Re^{m}$ .
this case, it is easy to see$(S_{1}-S_{2})=0$ for any $(x_{1}, s_{1})\in L$ andthat is a monotone affine space$\mathrm{h}$$\mathcal{L}$$\mathrm{S}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{S}\mathrm{p}_{\mathrm{i}\mathrm{n}\mathrm{g}}(X_{1}-X_{2})$$(X_{2}, s_{2})\in \mathcal{L}$$\bullet$.

Under assumptions [A1] and [A2], it is known that problem (1) has at least one solution. Since$X$$S=0$ if and only if $XS=0$ , problem (1) is equivalent to find afor (X, )’ we havepair (X, ) such that(X, ), $XS=0$ .
$S$$\in S_{+^{\mathrm{X}}}^{n}S^{n}+$$\bullet$

$S$

$S$

$\in \mathcal{L}_{+}$

It has been shown by Kojima, Shindoh and Hara [10] that the perturbed system(X, $S$ )$\in \mathcal{L}_{+}$,$XS=\mu$ ,(2), denoted by
has a umique solution in, for every $\mu>0$ , and thatexists’and is a solution of (1). The set $\{(X_{\mu}, S_{\mu}) : \mu>0\}$ isthe central path associated with (1)and plays a fundamental role in the development of interior point algorithms for solving SDP and
SDLCP. Another equivalent formulation of (2) is$(X_{\mu}, S_{\mu})$$\mathcal{L}_{++}$$\lim_{\muarrow 0}(XS_{\mu})\mu$$\mathrm{c}\mathrm{a}\mathrm{U}\mathrm{e}\mathrm{d}$

(X, )
$S$

$\in \mathcal{L}_{+}$,$X1/2SX1/2=\mu I$(or, $s1/2XS1/2=\mu I$ ),which motivates the following measure of closeness of (X, )the central trajectory:$S$$\in S_{+}^{n}\mathrm{x}S_{+}^{n}$to the point$d_{\mu}(X, s)\equiv||X1/2SX1/2-\mu I||F=||S^{1/2}Xs^{1}/2-\mu I||_{F}$and the following (feasible) neighborhood of$(x_{\mu}, s_{\mu})$$N_{F(\mu,\gamma})=\{(X, S)\in \mathcal{L}_{+} :$(X_{\mu}, S_{\mu})$

of

,

:
d_{\mu}(X, s)\leq\gamma\mu\}$,

where $\gamma>0$ is a given constant. Both algorithms described in Section 4 generate their iterates in
the neighborhood of the central path defined by$N_{F}( \gamma)\equiv\bigcup_{\mu>0N_{F}}(\mu,\gamma)$.

142
Path-following algorithms for solving (1) are based on the idea of approximately tracing thecentral path. Application of Newton method for computing the solution of (2)leads tothe Newton search direction
which solves the linear system$\mathrm{w}\mathrm{i}\mathrm{t}\mathrm{h}..\mu=\hat{\mu}$$(\overline{\Delta X},\overline{\Delta s})$$X\overline{\Delta S}+\overline{\Delta X}S=\hat{\mu}$

I–XS,$(X+\overline{\Delta X}, S+\overline{\Delta S})\in \mathcal{L}$.

(3)

Unfortunately, this system does not always have a solution. To overcome this difficulty, Kojima
and Shindoh and Hara proposed the following modified Newton system of equations:$X(\Delta S+\overline{\Delta S})+(\Delta X+\overline{\Delta X})S=\hat{\mu}$$(X+\Delta X, s+\Delta s)\in \mathcal{L}$

where
[A3]

$\mathcal{L}_{\perp}$

is a linear subspace of$\mathcal{L}_{1}\subseteq S_{\perp}^{n}\mathrm{x}S_{\perp}^{n},$$(U, V)\in \mathcal{L}_{\perp}$,$\Re^{n\cross n}\cross\Re^{n\cross n}\mathrm{s}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{s}q_{\mathrm{i}\mathrm{n}\mathrm{g}}$$\dim(\mathcal{L}\perp)=n(n-1)/2$.

and$\mathcal{L}_{1}$I-XS,$(\overline{\Delta X},\overline{\Delta s})\in \mathcal{L}_{\perp}$

the$\mathrm{f}\mathrm{o}\mathrm{U}_{0}\mathrm{W}\mathrm{i}\mathrm{n}\mathrm{g}$

(4a)

,

(4b)

condition:is monotone, that is$U$$\bullet$$V\geq 0$

for every

It was shown in Corollary 4.3 of [10] that system (4) always has a unique solution. The symmetric componentof this solution is then used as a search direction to generate the next.
In what follows we give another short proof of the existence and uniqueness of’which gives some intuition for the need to introduce the subsp.ace.
$(\Delta X, \Delta s)$$\mathrm{p}\underline{\mathrm{o}\mathrm{i}\mathrm{n}}\mathrm{t}$$(\Delta X,\overline{\Delta x}, \Delta S, \Delta s)\vee$$\mathcal{L}_{\perp}$

Lemma 2.1 Let (X, )
and
be an
dimensional affine subspace of
which is monotone, that is $(U_{1,\sim}-U2)$ $(V_{1}-V_{2}.)\geq 0$ for every. Then, the.
$S$$n^{2}$$\mathcal{W}$$\in s_{++^{\mathrm{X}}}^{n}s_{++}^{n}$$\Re^{n\cross n}\mathrm{x}\Re^{n}\cross n$$(U_{1}, V_{1}),$ $(U_{2}, V_{2})\in \mathcal{W}$$\bullet$system$XV+US=H$ ,has a unique solution for any$H\in\Re^{n\cross n}$$(U, V)\in \mathcal{W}$

,

(5)

.

Proof. Consider the map :defined by $\Phi(U, V)=XV+US$ for every.
is an affine map between spaces of the same dimension since $\dim(\mathcal{W})=n^{2}$ by as sumption.
Hence, it suffices to show that is. Indeed, assume that $\Phi(U_{1}, V_{1})=\Phi(U_{2}, V_{2})$ for some$\DeltaU\equiv
U_{1}-U_{2}$. Lettingand, and using the monotonicity of, we see thatand $X\Delta V+\Delta US=0$ . Multiplying the last relation on the left by$X^{-1/2}$
and on the right by $S^{-1/2}$ , squaring both sides and using the fact that
, weobtain$\Phi$$\mathcal{W}arrow\Re^{n\cross n}$$(U, V)\in \mathcal{W}$$\Phi$$\Phi$$\mathrm{o}\mathrm{n}\mathrm{e}- \mathrm{t}_{\mathrm{o}^{-}\mathrm{o}\mathrm{n}\mathrm{e}}$$(U_{1}, V_{1}),$ $(U_{2}, V_{2})\in \mathcal{W}$$\Delta U$$\mathcal{W}$$\bullet$$\Delta V\equiv V_{1}-V_{2}$$\Delta V\geq 0$$\Delta U$$\bullet$$\Delta V\geq 0$$0–||X1/2\Delta Us-1/2+X-1/2\Delta Vs^{1/2}||_{F}^{2}\geq||X1/2\Delta US-1/2||_{F}^{2}+||X^{-}1/2\Delta Vs1/2||^{2}F^{\cdot}$

Hence, $\Delta U=\Delta V=0$ , or equivalently $(U_{1}, V_{1})=(U_{2}, V_{2})$ .

Lemma
solution$\blacksquare$

the main reason for system (3) to not always have a solution, namely: theis required to belong to the affine subspace, which only has dimension$n(n+1)/2<n^{2}$ . Adding the subspace
to results in an affine subspace of dimension
asrequired by Lemma 2.1. This fact is exploited in the proof of the following result which establishes
the existence and uniqueness of the solution of (4).
$2.1_{\underline{\mathrm{P}^{\mathrm{r}\mathrm{o}\mathrm{V}}}}\mathrm{i}\mathrm{d}\mathrm{e}\mathrm{s}$$(\overline{\Delta X}, \Delta s)$$\mathcal{L}-(X, S)$$\mathcal{L}_{\perp}$$\mathcal{L}$Theorem 2.2 System (4) has a unique solution.

$n^{2}$

143

Proof. It issee thatis a solution of (4) if and only if $(U, V)\equiv$
is a solution of (5) with. Sinceandare monotone and orthogonal, $\dim(\mathcal{L})=n(n+1)/2$ and $\dim(\mathcal{L}\perp)=n(n-1)/2$ , we easily
see thatis a monotone affine subspace ofof dimension . The result now follows.
&om Lemma 2.1.
$(\Delta X,\overline{\Delta X}, \Delta s,\overline{\Delta s})$$\mathrm{e}\mathrm{a}\mathrm{s}\underline{\mathrm{y}\mathrm{t}\mathrm{o}}$$(\Delta X+\overline{\Delta X}, \Delta s+\Delta s)$$\mathcal{W}\equiv(L-(X, \mathrm{Y}))+\mathcal{L}_{\perp^{\mathrm{a}\mathrm{n}\mathrm{d}H}}\equiv\hat{\mu}I-XS$$\mathcal{L}$$\mathcal{L}_{\perp}$$\mathcal{W}$$\Re^{n\mathrm{x}n}\mathrm{X}\Re^{n\cross n}$$n^{2}$$\blacksquare$3

Technical Results

In this section we provide some technical results which will be used to establish the polynomialconvergence of the algorithms presented in Section 4.
We assume throughout this section that (X, )and thatis a solutionof system (4) withfor some $\mu>0$ and $\sigma\in[0,1]$ . Moreover, we let$S$$(\Delta X,\overline{\Delta X}, \Delta s,\overline{\Delta s})$$\in \mathcal{L}_{++}$$\hat{\mu}=\sigma\mu$$W_{x}\equiv X^{-1/2}[\Delta xs+X\Delta s+xS-\sigma\mu I]x1/2$

and, for every$\alpha\in\Re$

,

(6)

,
$X(\alpha)$$\equiv$$\mu(\alpha)$$\equiv$,$X+\alpha\Delta X$$S(\alpha)\equiv S+\alpha\Delta S$$(1-\alpha+\sigma\alpha)\mu$

,

(7)

.

(8)

Lemma 3.1 We have
$W_{x}=-X-1/2[\overline{\Delta X}S+X\overline{\Delta s}]X^{1/}2$

and, for every$\alpha\in\Re$

,

(9)

,

$X^{-1/.2}2[X(\alpha)s(\alpha)-\mu(\alpha)I]X^{1}/$$=$$(1-\alpha)(X1/2Sx1/2-\mu I)+\alpha Wx$$+\alpha x^{-}21/2\Delta x\Delta sX1/2$

.

(10)

Proof. Relation (9) follows immediately from (6) and (4a). Relation (10) follows ffom (7), (6) and(8) by simple algebraic manipulation.

$\blacksquare$as

For a a nonsingular matrix$P\in\Re^{n\cross n}$, consider the following operator$H_{P}(M) \equiv\frac{1}{2}[PMP^{-1}+(PMP-1)\tau],$$H_{P}$$\forall M\in\Re n\cross n$:$\Re^{n\cross n}arrow S^{n}$defined.

The operator
has been recently used by Zhang [31] to characterize the central path of SDP
problems. The next two lemmas, due to Monteiro (see Lemma 2.1 and Lemma 3.5 of [15]), play a
crucialin our nalysis.
$H_{P}$ro.le$.\mathrm{a}$..

Lemma 3.2 Suppose that (X, )every, we have$S$$\in S_{++}^{n}\mathrm{x}S_{++}^{n}$$\mu\in\Re$

and$Q\in\Re^{n\cross n}$

is a nonsingular matrix. Then, for$||X1/2SX1/2-\mu I||F\leq||H_{Q}(XS-\mu I)||_{F}$ ,with equality holding if $QXSQ-1\in S^{n}$ .

144Lemma 3.3 Let$W\in\Re^{n\cross n}$

be such that $H_{Q}(W)=0$ for some nonsingular$||H_{I}(W)||$$\leq$$||W||_{F}$$\leq$

In particular, if $W=U_{1}+U_{2}$ for some$\frac{1}{2}||W-W^{T}||p$and$U_{2}\in\Re^{n\cross n}$$||W||_{F}\leq\sqrt{2}||U_{2}||F$. Then,(11)’$\frac{\sqrt{2}}{2}||W-W^{\tau}||_{F}$$U_{1}\in S^{n}$$Q\in\Re^{n\cross n}$

.

(12)

, then.

With the aid of the last lemma, we can now prove the following result.

Lemma 3.4 For every$\theta\in\Re$

and $a\in[0,1]$ , we have$||X^{-1/2}[X(\alpha)S(\alpha)-\mu(a)I]\mathrm{x}1/2||_{F}$$\leq$$(1-\alpha)||X^{1/2}Sx1/2-\mu I||F+\alpha^{2}\delta_{x}\delta_{s}$$+ \alpha(1+2\sqrt{2})\max\{\delta_{x},\tilde{\delta}_{x\}}||X^{1//2}2SX^{1}-\theta\mu I||,(13)$where$\delta_{x}\equiv||X-1/2\Delta xx-1/2||_{F}$,$\tilde{\delta}_{x}\equiv||X^{-1/2}\overline{\Delta x}X-1/2||_{F}$,$\delta_{s}\equiv||X1/2\Delta SX1/2||_{F}$

.

(14)

Proof. By (10) and (14), we have for every $\alpha\in[0,1]$ that.

$||X^{-1/2}[X(\alpha)S(a)-\mu(\alpha)I]X^{1/2}||F\leq(1-\alpha)||X1/2sX1/2-\mu I||_{F}+\alpha||W_{x}||_{F}+\alpha^{2}\delta_{x}\delta_{s}$Given$\theta\in\Re$, define.

$W\equiv W_{x}+X-1/2\overline{\Delta X}x^{-}1/2(x^{1/2}Sx1/2-\theta\mu I)$

(15)

(16)

Using (9), we easily see that
$W=-X^{1/2}\overline{\Delta S}x^{1}/2-\theta\mu x-1/2\overline{\Delta x}x-1/2$, due to the fact thatand hence thateasily see that $W=U_{1}+U_{2}$ , where$W\in S^{\perp}$$U_{1}$$\equiv$$U_{2}$$\equiv$$U_{1}$$||W||F$. Moreover, using (6) and (16), we$X1/2\Delta sx1/2+\theta\mu X^{-1//2}2\Delta Xx-1+X1/2Sx1/2-\sigma\mu I$$X^{-1/2}(\Delta X+\overline{\Delta X})X^{-1/}2(X^{1/2}Sx1/2-\theta\mu I)$

Clearly,since
andthat $W,$(17) and (14), we obtain$U_{2}\mathrm{s}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{s}\Psi$. Noting that

,

.

(17)

is equivalent to $H_{I}(W)=0$ , it follows
the assumptions of Lemma 3.3 with $Q=I$ . Hence, by Lemma (3.3),$\Delta X,$ $\Delta S\in S^{n}$$U_{1}\in S^{n}$$\overline{\Delta X},\overline{\Delta S}\in S^{\perp}$,$W\in S^{\perp}$$\leq$$\sqrt{2}||U_{2}||F\leq\sqrt{2}||X^{-1/2}(\Delta X+\overline{\Delta X})x^{-}1/2||_{F}||X1/2sx1/2-\theta\mu I||$$\leq$$\sqrt{2}(\delta_{x}+\tilde{\delta}_{x})||X^{1//}2SX^{1}2-\theta\mu I||$

,

145

which together with (16) and (14) imply$||W_{x}||$$\leq$$||W||F+||x^{-1/2-^{\iota/}}\overline{\Delta X}x2||F||X^{1//}2SX^{1}2-\theta\mu I||$$\leq$$[\tilde{\delta}_{x}+\sqrt{2}(\delta_{x}+\tilde{\delta}x)]||x^{1/2}sx1/2-\theta\mu I||$$\leq$$(1+2 \sqrt{2})\max\{\delta_{x},\tilde{\delta}_{x\}}||X^{1//}2SX^{1}2-\theta\mu I||$.

This inequality together with (15) now yield (13).

$\blacksquare$

The proof of next lemma is straightforward and therefore we omit the details.
Lemma 3.5 If (X, )$S$$\in N_{F(\mu,\gamma})$for some $7\in(0,1)$ , then$||x^{1}/2S1/2||^{2}$$||x-1/2s-1/2||2$$||X^{1/2}Sx1/2-\theta\mu I||_{F}$$(1-\gamma)n\mu$$S$$\in N_{F(\mu,\gamma})$$\leq$$[(1-\gamma)\mu]^{-1}$$\leq$$(\gamma+(1-\theta)rn)\mu$$\leq$$X$

for some$\max\{\delta_{x},\tilde{\delta}_{x}\}$$\delta_{s}$where$\delta_{x},\tilde{\delta}_{x}$and$\delta_{s}$(18)$(1+\gamma)\mu$$\bullet$

,

(19)

,

$S\leq(1+\gamma)n\mu$

The next result gives bounds on the quantities

Lemma 3.6 If (X, ),$\leq$$\delta_{x},\tilde{\delta}_{x}$$\gamma\in(0,1)_{f}$and.

$\delta_{s}$for any$\theta\in[0,1]$

,

(20)
(21)

defined in (14).

then,$\leq$$\frac{\gamma+(1-\sigma)\sqrt{n}}{1-\gamma}$$\leq$$\frac{\gamma+(1-\sigma)\sqrt{n}}{1-\gamma}\mu$,

are defined in (14).

Proof. Multiplying (4a) on the left by $X^{-1/2}$ and on the right by $S^{-1/2}$ , squaring both sides of, we obtain
the resulting equation and noting the fact that$(\Delta X+\overline{\Delta X})$$\bullet$$(\Delta S+\overline{\Delta S})\geq 0$$||X^{-1/2}(\Delta x+\overline{\Delta X})S^{1/2}||_{F}2+||X^{1/2}(\Delta s+\overline{\Delta S})s^{-1}/2||^{2}F\leq||X^{1/2}s^{1}/2-\sigma\mu x-1/2s^{-}1/2||_{F}2$

Using the fact that for any$M\in\Re^{n\cross n}$,$\frac{||M+M^{\tau}||_{F}}{2}\leq||M||_{F}$,$\frac{||M-MT||_{F}}{2}\leq||M||_{F}$,relations (14) and (22), and Lemma 3.5, we obtain$\delta_{s}$$=$$||X1/2\Delta sx1/2||_{F}\leq||x^{1/2}(\Delta S+\overline{\Delta S})X^{1}/2||_{F}$$\leq$$||X1/2(\Delta S+\overline{\Delta s})s-1/2||F||S^{1/}2x1/2||$$\leq$$||X^{1/2}S^{1}/2-\sigma\mu x-1/2s-1/2||p||S^{1/}2x1/2||$$\leq$$||x^{1/2}SX^{1/}2-\sigma\mu I||_{F}||X^{-1/2}s^{-1}/2||||X^{1/2}s1/2||$$\leq$$( \frac{1+\gamma}{1-\gamma})^{1/2}(\gamma+(1-\sigma)\mathrm{V}\eta n\mu\leq\frac{\gamma+(1-\sigma)\sqrt{n}}{1-\gamma}\mu$,, (22)

146
and$\max\{\delta_{x},\tilde{\delta}_{x}\}$,$\leq$$\max\{||X^{-1//}2\Delta XX^{-1}2||F$$\leq$$||X-1/2(\Delta X+\overline{\Delta x})x-1/2||F$$\leq$$||X^{-1/}2(\Delta x+\overline{\Delta X})S^{1}/2||_{F}||s^{-1/2}x-1/2||$$\leq$$||x1/2S1/2-\sigma\mu X^{-}1/2s-1/2||F||x^{-}1/2S-1/2||$$\leq$$||X^{1/2}SX^{1}/2-\sigma\mu I||_{F}||X^{-1//}2s^{-}12||^{2}$$\leq$$\frac{\gamma+(1-\sigma)\sqrt{n}}{1-\gamma}$$||X^{-1/}2\overline{\Delta x}x-1/2||_{F}\}$.
$\blacksquare$

Now we are ready to state-the main result of this section.

Lemma 3.7 Suppose that (X, )solution of (4). Then,$S$$\in N_{F(\mu,\gamma})$for some $7\in(0,1)$ and let$(\Delta X,\overline{\Delta X}, \Delta s,\overline{\Delta s})$be the$||x^{-1}/2[X(\alpha)s(\alpha)-\mu(\alpha)]x1/2||F$$\leq$.

$\{(1-\alpha)\gamma+a(1+2\sqrt{2})\gamma\frac{\gamma+(1-\sigma)\sqrt{n}}{1-\gamma}+a2(\frac{\gamma+(1-\sigma)\sqrt{n}}{1-\gamma})^{2}\}\mu$

Proof. Follows immediately
Lemma 3.6.

4$\mathrm{h}\mathrm{o}\mathrm{m}(13)$with $\theta=1$ , the assumption that (X, )$S$$\in N_{F(\mu,\gamma})$

md$\blacksquare$

Algorithms

In this section, we establish polynomial iteration-complexity bounds for two primal-dual feasible
interior-point algorithms for SDLCP based on the KSH family of search directions given by (4).
Both algorithms are extensions of well-known algorithms for linear programming: the first one isa short-step path-following method which generalizes the algorithms presented in Kojima, Mizuno
and Yoshise [6] and Monteiro and Adler $[16, 17]$ ; the second one is a predictor-corrector algorithm
simmilar to the predictor-corrector LP method of Mizuno, Todd and Ye [13].

4.1

Short-step path$\mathrm{f}\mathrm{o}\mathrm{U}\mathrm{o}\mathrm{W}\mathrm{i}\mathrm{n}\mathrm{g}$algorithm

In this subsection, we analyze the polynomial convergence of a short-step pathbased on the KSH family of search directions.
We start by stating the algorithm that will be considered in this subsection.

$\mathrm{f}\mathrm{o}\mathbb{I}_{0}\mathrm{W}\mathrm{i}\mathrm{n}\mathrm{g}$algorithm

147

Algorithm-I:
Choose constants
below and let$\gamma$and$\delta$in$\sigma\equiv 1-\delta/\sqrt{n}$$(X^{0}, s^{0})\in N_{F(\mu 0,\gamma})$$(\mathrm{o}, 1)\mathrm{s}\mathrm{a}\mathrm{t}\mathrm{i}_{\mathrm{S}\mathrm{w}\mathrm{n}\mathrm{g}}\mathrm{i}$. Let$\mu_{0}>0$. Let $L>1$ .

Repeat until, do(1) Choose a linear subspace(2) Compute the solution

andthe conditions of Theorem 4.2
be such that$(X^{0},s^{0})\in \mathcal{L}_{++}$$\mu_{k}\leq 2^{-L}\mu_{0}$$\mathcal{L}_{\perp}^{k}\mathrm{S}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{S}6^{r\mathrm{i}\mathrm{g}}\mathrm{n}$[A3].

$(\Delta X^{k},\overline{\Delta x}^{kk}, \Delta S^{k},\overline{\Delta s})$(X, $S$ ) $=(Xk, sk),$$\mathcal{L}\perp=\mathcal{L}_{\perp}^{k}$and$\hat{\mu}=\sigma\mu k$of system (4) with;

(3) Set $(x^{k+1}, s^{k}+1)\equiv(X^{k}, S^{k})+(\Delta X^{kk}, \Delta S)$ and(4) Increment by 1.

$\mu_{k+1}=\sigma\mu_{k}$

;

$k$

End
When the constant defined in (23) is such that, the lemma below implies that thesequence $\{(x^{k}, s^{k})\}$ generated by Algorithm-I is contained in the neighborhood. Thislemma is also used in the analysis of the corrector (or centering) steps of the predictor-corrector
algorithm presented in the next subsection.
$\Gamma$$\Gamma\leq\gamma$$N_{F}(\gamma)$

Lemma 4.1 Let $7\in(0,1)$ and$\delta\in[0, n^{1/2})$

be constants satisfying$\Gamma\equiv 5(\frac{\gamma+\delta}{1-\gamma})^{2}(1-\frac{\delta}{\sqrt{n}})^{-}1<1$

.

(23)

Suppose that (X, )is the solution of system
for some $\mu>0$ , and(4) with
and $\sigma=1-\delta/\sqrt{n}$ . Then, $(X+\Delta X, S+\Delta S)\in N_{F}(\sigma\mu, \Gamma)$ .
$S$$\in N_{F(\mu,\gamma})$$(\Delta X,\overline{\Delta X}, \Delta s,\overline{\Delta s})$$\hat{\mu}=\sigma\mu$Proof. It follows from Lemma 3.7, the definition of$\sigma$and (23) that for every $a\in[0,1]$ ,$||x^{-1}/2[X(a)s(a)-\mu(a)]X1/2||_{p}$$\leq\{(1-a)\gamma+a(1+2^{\sqrt{2})}\gamma\frac{\gamma+(1-\sigma)\sqrt{n}}{1-\gamma}+a2(\frac{\gamma+(1-\sigma)\Gamma n}{1-\gamma})^{2}\}\mu$$=(1-a) \gamma\mu+\{\alpha(1+2^{\sqrt{2}2})\gamma\frac{\gamma+\delta}{1-\gamma}+a(\frac{\gamma+\delta}{1-\gamma})^{2}\}\mu$$\leq(1-a)\gamma\mu+5\alpha(\frac{\gamma+\delta}{1-\gamma})^{2}\mu\leq(1-\alpha)\gamma\mu+5a\Gamma(1-\frac{\delta}{\sqrt{n}})\mu$$=\{(1-\alpha)\gamma+\sigma\Gamma\alpha\}\mu$,

and hence, in view of (8) and (23), we have$|| \frac{x-1/2X(a)s(\alpha)x1/2}{\mu(\alpha)}-I||_{p}\leq\frac{(1-\alpha)\gamma+\sigma\Gamma a}{1-a+\sigma a}\leq\max\{\gamma, \Gamma\}<1$

This implies that $x-1/2X(a)s(\alpha)x1/2$ is invertible for every
also invertible for every. Using the fact that (X, )$a\in(\mathrm{O}, 1]$$S$$a\in(\mathrm{O}, 1]$$\in \mathcal{L}_{++},$.

. Hence, $X(a)$ and$S(\alpha)$$(X+\Delta X, S+\Delta S)\in \mathcal{L}$

are
and

148

$S(a)$ )for everya simple continuity argument, we see (X$Q=X^{-1/2}$$=(X(a),S(\alpha))$
,
we
then
obtain)(X,
and
3.2 with$(\alpha),$$\in \mathcal{L}_{++}$$a$$\in(0,1]$. Applying Lemma$S$$||X(a)^{1}/2s(\alpha)x(a)1/2-\mu(\alpha)I||F$$\leq$$\leq$$||H_{x^{-1}/2}(X(\alpha)S(\alpha)-\mu(a)I)||F$$||X^{-1/1}2x(a)s(a)x/2-\mu(\alpha)I||_{F}\leq\{(1-\alpha)\gamma+\sigma\Gamma a\}\mu$

Setting $a=1$ in the last relation and using the fact that (X (1), $S(1)$ )(8), we conclude that (X (1), $S(1)$ ) $\equiv(X+\Delta X, S+\Delta S)\in N_{F(\sigma\mu},\Gamma)$ .

$\in \mathcal{L}_{++^{\mathrm{t}_{0}\mathrm{g}\mathrm{t}}}\mathrm{e}\mathrm{h}\mathrm{e}\mathrm{r}$.

with (7) and$\blacksquare$

As an immediate consequence of Lemma 4.1, we have the following convergence result for
Algorithm-I.
Theorem 4.2 Suppose that
. Then, every iterate$\gamma$and$(X^{k}, S^{k})$$\Gamma\leq\gamma$$X^{k}$

Moreover, Algo

$7^{\cdot}ithm- I$$\bullet$are constants in $(0,1)$ such thatgenerated by Algorithm-I is in$\delta$$\Gamma$defined by (23) satisfies)
and satisfies$N_{F(\mu_{k},\gamma}$$S^{k} \leq\frac{1+\gamma}{1-\gamma}(1-\frac{\delta}{\sqrt{n}})^{k}(X0 \bullet S^{0})$terminates in at most$\mathcal{O}(\sqrt{n}L)$$\subseteq N_{F}(\gamma)$

.

(24)

iterations.

is infollows immediately from Lemma
Proof. The proof that every iterateand
4.1 and a simple induction argument. Relation (24) follows from the fact that
relation (21).
$(X^{k}, S^{k})$$N_{F}(\mu k, \gamma)$$\mu_{k}=\sigma^{k}\mu_{0}$$\blacksquare$

Examples of constants 7 and

4.2$\delta_{\mathrm{S}}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{s}\mathfrak{g}r\mathrm{i}\mathrm{n}\mathrm{g}$the conditions of Theorem 4.2 are $\gamma=\delta=1/10$ .

Predictor-corrector algorithm

In this subsection, we give the polynomial convergence analysis of a predictor-corrector algorithm
which is a direct extension of the LP predictor-corrector algorithm studied by Mizuno, Todd andYe [13].
The algorithm considered in this subsection is as follows.

Algorithm-II:
Choose a constant $0<\tau<1$ satisping the conditions of Theorem 4.3 below.
)
be such that $(X^{0}, s^{0})\in N_{F}(\mu 0, \tau)$ ,Let $L>1$ and (X, do
Repeat until(1) Choose a linear subspace[A3];of system (4) with
(2.) Compute the solution$0,$ $S^{0}$$\in \mathcal{L}_{++}$$\mu_{k}\leq 2^{-L}\mu_{0}$$\mathcal{L}_{\perp}^{k}\mathrm{S}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{S}\mathfrak{g}r\mathrm{i}\mathrm{n}\mathrm{g}$$(\Delta Xk\overline{\Delta X}^{k}P’\Delta S\overline{\Delta}ks^{k}P’ P’ P)$(X, ) $=(X^{k}, S^{k}),$;(3) Let $\alpha_{\mathrm{k}}\equiv\max\{\alpha\in[0,1]:(X^{k}(a’), s^{k}(a’))\in N_{F((1}-\alpha’)\mu_{k}, 2\tau), \forall\alpha’\in[0, a]\}$ ,$S$$L_{\perp}=\mathcal{L}_{\perp}^{k}\mathrm{m}\mathrm{d}\hat{\mu}=0$

where $(X^{k}(a), sk(a))\equiv(X^{k}+\alpha\Delta X_{P}^{k}, s^{k}+a\Delta S_{P}^{k})$ ;(4) Letand $\mu_{k+1}.\equiv(1-a_{k})\mu_{k}$ ;(5) Choose a linear subspace[A3];(6) Compute the solutionof system (4) with
(X, )
;
and
(7) Set;(8) Increment by 1.
$(\hat{X}^{k},\hat{S}^{k})\equiv(X^{k}, S^{k})+a_{k}(\Delta x_{P’ P}k\Delta Sk)$$\hat{L}_{1^{\mathrm{S}}}^{k}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{s}\mathrm{p}_{\mathrm{i}\mathrm{n}\mathrm{g}}$$(\Delta X_{C}^{k},\overline{\Delta X}c’\Delta S_{c}^{k},\overline{\Delta S}_{C}^{k}k)$

$S$

$l$

$=(\hat{X}^{k},\hat{s}^{k}),\hat{\mu}=\mu_{k+1}$$\mathcal{L}\perp=\hat{\mathcal{L}}_{\perp}^{k}$$(x^{k+1}, s^{k}+1)\equiv(\hat{X}^{k},\hat{S}^{k})+(.\Delta X^{k}\Delta s^{k}.)C’ c$
$k$

End

149
The

$\mathrm{f}\mathrm{o}\mathrm{U}\mathrm{o}\mathrm{W}\mathrm{i}\mathrm{n}\mathrm{g}$result provides the polynomial convergence analysis of the above algorithm.

Theorem 4.3 Assume that $\tau\in(0,1/30]$ . Then, Algorithm-II satisfies the following statements:$a)$for every$k\geq 0,$ $(X^{k}, S^{k})\in N_{F}(\tau)$$b)$

for every$k\geq 0,$$c)$

the algorithm terminates in at most$X^{k}$$\bullet$and$(\hat{X}^{k},\hat{S}^{k})\in N_{F(}2_{\mathcal{T});}$$S^{k} \leq\frac{1+\tau}{1-\tau}(1-\overline{a})^{k}x0$$\mathcal{O}(\sqrt{n}L)$$S^{0}$$\bullet$, where$\overline{a}=1/O(\sqrt{n})$;iterations.

Proof. Statement (c) and the well-definedness of Algorithm-II follow directly from (a) and (b).
, these two statements follow by a simple induction argument, the two lemmas below andIn
relation (21).
$\mathrm{t}\mathrm{u}\mathrm{m}$$\blacksquare$

The following lemma analyzes the predictor step of Algorithm-II, namely the step described in
items (1) $-(4)$ of Algorithm-II.

Lemma 4.4 Suppose that (X, )for some $\tau\in(0,1/2)$ . For some subspacesatisfying, letdenote the solution of (4) with
. Let denote the uniquepositive root of the second-order polynomial $p(a)$ defined as$S$$\in N_{F}(\mu, \tau)$$\mathcal{L}_{\perp}$$(\Delta X,\overline{\Delta x}, \Delta s,\overline{\Delta s})$$fA\mathit{3}f$$\hat{\mu}=0$$\overline{\alpha}$(25)$p( \alpha)=(\frac{\tau+\sqrt{n}}{1-\tau})^{2}a^{2}+\mathcal{T}[(1+2\sqrt{2})(\frac{\tau+\sqrt{n}}{1-\tau})+1]a-\tau$Then, for any$a\in[0,\overline{\alpha}]$, we have:(X $(a),$Moreover,$\overline{\alpha}=1/\mathcal{O}(n^{1/2})$$S(\alpha)$) $\in NF((1-\alpha)\mu, 2_{\mathcal{T}})$ .

(26)

.

Proof. Using Lemma 3.7 with(25), we obtain$\gamma=\tau$$||x^{-1}/2[X(\alpha)s(a)-\mu(\alpha)]x^{1}/2||_{F}$and $\sigma=0$ , the fact that $p(a)\leq 0$ for$\alpha\in[0,\overline{\alpha}],$$\mathcal{T}\leq 1/2$

and$\leq$$\{(1-a)_{\mathcal{T}+}(1+2\sqrt{2})\mathcal{T}(\frac{\tau+\sqrt{n}}{1-\tau}\mathrm{I}\alpha+(\frac{\tau+\sqrt{n}}{1-\tau})^{2}\alpha^{2}\}\mu$$=$$2\tau\mu(\alpha)+p(a)\mu\leq 2\tau\mu(a)$.

An argument similar to the one used in Lemma 4.1 together with (8) and the fact that $2\tau<1$and(or equivalently, $\sigma=0$ ) can be used to show that (26) holds. The assertion that$\overline{a}=1/O(n^{1/2})$
follows by a straightforward verification.
$\hat{\mu}=0$$\blacksquare$

The following lemma analyzes the corrector step of Algorithm-II, namely the step described in
items (5) $-(7)$ of Algorithm-II.

Lemma 4.5 Suppose
solution of (4) with (X, )$(\hat{X},\hat{S})$

$S$

is in

$N_{F(\mu,2_{\mathcal{T}}}$$=(\hat{X},\hat{S}),\hat{\mu}=\mu$) for some $\tau\in(0,1/30]$ . Let

and$\mathcal{L}_{1}$$(\hat{X},\hat{S})+(\overline{\Delta X}c,\overline{\Delta S}c)$satisfying$\in$$(\overline{\Delta X}c,\overline{\Delta S}_{C})$]. Then,$N_{F(\mu,\tau})$.

Proof. Fouows inmmediately &om Lemma 4.1 with $\sigma=1$ (or equivalently,, and noting that defined by (23) satisfies
andwhen $\tau\leq 1/30$ .

$\delta=0$$\gamma=2\tau$$\Gamma$$\Gamma\leq\tau$denote the$fA\mathit{3}$), $(X, S)=(\hat{x},\hat{s})-$150
5Concluding remarks

For simplicity, we have analyzed two algorithms whose sequencein general differs ffom thesequence of normalized complementarity gaps
. At the expense of a slightly more
complicated analysis, it is possible to develop algorithms similar to the ones presented here in which
for every .
The algorithms of this paper are based on the bobenius neighborhoodof the central
path. An interesting topic for future research would be to establish polynomial convergence ofalgorithms based on the KSH family of search directions which use one of thetwo widerneighborhoods of the central path:$\{\mu_{k}\}$$\{(X^{k} \bullet S^{k})/n\}$$\mu_{k}=$$(X^{k} \bullet S^{k})/n$$k$$N_{F}(\gamma)$$\mathrm{f}\mathrm{o}\mathrm{U}\mathrm{o}\mathrm{w}\mathrm{i}\mathrm{n}\mathrm{g}$$\{(X, S)\in \mathcal{L}_{+}:$$||X1/2sX1/2-\mu I||\leq\gamma\mu${ $(X,$$\lambda_{\min}(Xs-\mu I)\geq-\gamma\mu$$S)\in \mathcal{L}_{+}:$, for some $\mu>0\}$ ,, for some $\mu>0$ }.

Acknowledgement
This work was done while the first author was visiting the Institute of Statistical Mathematics andthe Tokyo Institute of Technology in Japan. This author is grateful to the first institute for thefinancial support and, to both institutes, for the congenial scientific atmosphere provided during
his stay. The first author would also like to thank the second author and Prof. Masakazu Kojima
of the Tokyo Institute of Techmology for making his visit to Japan a very enjoyable experience.

References[1] F. Alizadeh. Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM Journal on Optimization, $5(1):13-51$ , 1995.
[2] F. Alizadeh, J.-P.A. Haeberly, and M.L. Overton. Primal-dual interior-point methods forsemidefinite programming. Techmical Report 659, Computer Science Department, Courant
Institute of Mathematical Sciences, New York University, 1994.

[3] R. M. Freumd. Complexity of an algorithm for finding an approximate solution of a semidefinite
program with no regularity condition. Working paper OR 302-94, Operations Research Center,.. Massachusetts Institute of Technology, Cambridge, December 1994.
[4] C. Helmberg, F. Rendl, R. J. Vanderbei, and H. Wolkowicz. An interior-point method
for semidefinite programming. Manuscript, Program in Statistics and Operations Research,
Princeton University, 1994. To appear in SIAM Joumal on Optimzation.

[5] F. Jarre. An interior-point method for minimizing the maximum eigenvalue of a linear combination of matrices. SIAM Joumal on Control and Optimization, 31:1360-1377, 1993.
[6] M. Kojima, S. Mizlmo, and A. Yoshise. A polynomial-time algorithm for a class of linear
complementarity problems. Mathematical Programming, 44:1-26, 1989.

151[7] M. Kojima, S. Mizuno, and A. Yoshise. A primal-dual interior point algorithm for linear
programming. In N. Megiddo, editor, Progress in Mathematical Programming : Interior Point
and Related Methods, pages 29-47. Springer Verlag, New York, 1989.
[8] M. Kojima, M. Shida, and S. Shindoh. Local convergence of predictor-corrector infeasibleinterior-point algorithms for SDPs and SDLCPs. Research Report #B-306, Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology, 2-12-1 O–Okayama, Meguroku, Tokyo 152, December 1996.
$\mathrm{h}$[9] M. Kojima, M. Shida, and S. Shindoh. A note on the Nesterov-Todd and the Kojima-ShindohHara search directions in semidefimite programming. Research report #B-313, Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology, 2-12-1 Oh-Okayama, Meguroku, Tokyo 152, Japan, Apri11996.
[10] M. Kojima, S. Shindoh, and S. Hara. Interior-point methods for the monotone
semidefimite
linear complementarity problem in symmetric matrices. Research Reports on Information
Sciences, Ser. B : Operations Research B-282, Dept. of hfomation Sciences, Tokyo Instituteof Technology, 2-12-1 Oh-Okayama, Meguro-ku, Tokyo 152, Japan, April 1994. To appear
in
SIAM Journal on Optimization.
[11] 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.

[12] Z-Q. Luo, J. F. Sturm, and S. Zhang. Superlinear convergence of a symmetric primal-dual
algorithm forprogramming. Report, Econometric Institute,
Erasmus University, Rotterdam, The Netherlands, January 1996.
$\mathrm{p}\mathrm{a}\mathrm{t}\mathrm{h}- \mathrm{f}0\mathrm{U}_{0\mathrm{W}\mathrm{i}}\mathrm{n}\mathrm{g}$$\mathrm{s}\mathrm{e}\mathrm{m}\mathrm{i}\mathrm{d}\mathrm{e}\mathrm{f}\mathrm{f}\mathrm{i}\dot{\mathrm{u}}\mathrm{t}\mathrm{e}$$9607/\mathrm{A}$[13] S. Mizuno, M. J. Todd, and Y. Ye. On adaptive step primal-dual interior-point algorithms
for linear programming. Mathematics of Opemtions Research, 18:945-981, 1993.

[14] R. D. C. Monteiro. Primal-dual path following algorithms for semidefinite
programming.
manuscript, School, Georgia Institute of Technology, Atlanta, GA 30332, USA, September 1995. To appear in SIAM J. on Optimization.
$\mathrm{o}\mathrm{f}\mathrm{I}\mathrm{s}_{\mathrm{y}}\mathrm{E}$[15] R. D. C. Monteiro. Polynomial convergence of primal-dual algorithms forsemidefinite programming based on Monteiro and Zhang family of directions. manuscript, School of ISyE,
Georgia Institute of Technology, Atlanta, GA 30332, USA, July 1996.

[16] R. D. C. Monteiro and I. Adler. Interior path-fouowing primal-dual algorithms. Part I:
Linearprogramming. Mathematical Programming, 44:27-41, 1989.

[17] R. D. C. Monteiro and I. Adler. Interior path-following primal-dual algorithms. Part II: Convex
quadratic programming. Mathematical Programming, 44:43-66, 1989.
[18] R. D. C. Monteiro and Y. Zhang. A umified analysis for a class of path-following primal-dual
interior-point algorithms for semidefinite programming. manuscript, School of ISyE, Georgia
Institute of Teclmology, Atlanta, GA 30332, USA, June 1996.

152[19] Y. E. Nesterov and A. S. Nemirovskii. A general approach to the design of optimal methods
for smooth convex functions minimization. Ekonomika i Matem. Metody, 24:509-517, 1988.
(h Russian; English transl. Matekon: banslations of Russian and East European Math.
Economics.).

[20] Y. E. Nesterov and A. S. Nemirovskii. Self-concordant functions and polynomial time methods
in convex programming. preprint, Central Economic&Mathematical Institute, USSR Acad.
Sci. Moscow, USSR, 1989.
[21] Y. E. Nesterov and A. S. Nemirovskii. Optimization over positive semidefinite matrices: Mathematical background and user’s manual. Techmical report, Central Economic&Mathematical
Institute, USSR Acad. Sci. Moscow, USSR, 1990.

[22] Y. E. Nesterov and A. S. Nemirovskii. Interior Point Methods in Convex Programming: Theory
and Applications. Society for Industrial and Applied Mathematics, Philadelphia, 1994.
[23] Y. E. Nesterov and M. 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.
[24] Y. E. Nesterov and M. Todd. Self-scaled barriers and interior-point methods for convex programming. Technical Report 1091, School of Operations Research and Industrial Engineering,
ComeU University, Ithaca, New York, 14853-3801, 1995.

-point[25] F. A. Potra and R. Sheng. A superlinearly convergent primal-dual
78,
Departalgorithm for semidefinite programming. Reports on Computational Mathematics
ment of Mathematics, The University of Iowa, Iowa City, Iowa, October 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}$[26] J. F. Sturm and S. Zhang. Symmetric primal-dual path-following algorithms for semidefinite, Econometric Institute, Erasmus University, Rotterdam, The
programming. Report
Netherlands, November 1995.
$9554/\mathrm{A}$[27] M. J. Todd, K. C. Toh, and R. H. T\"ut\"unc\"u. On the Nesterov-Todd direction in semidefinite
programnuing. Technical Report, School of Operations Research and Industrial Engineering,
Comell University, Ithaca, NY 14853, USA, 1996.

[28] P. Tseng. Search directions and convergence analysis of some infeasible path-following methods
for the monotone semi-definite LCP. manuscript, Department of Mathematics, University ofWashington, Seattle, Washington, 98195, USA, June 1996.
[29] L. Vandenberghe and S. Boyd. A primal-dual potential reduction method for problems involving matrix inequalities. Mathematical Programming, 69:205-236, 1995.
[30] Y. Ye. A class of projective transformations for linear programming. SIAM Joumal on Computing, 19:457-466, 1990.
[31] Y. Zhang. On extending primal-dual interior-point algorithms &om linear programming to, University ofsemidefinite programming. Technical Report TR 95-20, Dept. of
Maryland Baltimore County, Baltimore, MD 21228, USA, 1995.
$\mathrm{M}\mathrm{a}\mathrm{t}\mathrm{h}/\mathrm{S}\mathrm{t}\mathrm{a}\mathrm{t}$