A PREDICTOR CORRECTOR METHOD FOR SEMI-DEFINITE LINEAR PROGRAMMING Chih-Jen Lin and Romesh Saigal Department of Industrial & Operations Engineering The University of Michigan Ann Arbor, Michigan 48109-2117 Technical Report 95-20 October 1995 Revised December 1995

A Predictor Corrector Method for Semi-definite Linear Programming* Chih-Jen LIN Romesh SAIGAL Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, Michigan 48109-2117, USA October 30, 1995 ( revised December 10, 1995 ) Abstract In this paper we present a generalization of the predictor corrector method of linear programming problem to semidefinite linear programming problem. We consider a direction which, we show, belongs to a family of directions presented by Kojima, Shindoh and Hara, and, otie of the directions analyzed by Monteiro. We show that starting with the initial complementary slackness violation of to, in O(llog( -)[/in) iterations of the predictor corrector method, the complementary slackness violation can be reduced to less than or equal to e > 0. We also analyze a modified corrector direction in which the linear system to be solved differs from that of the predictor in only the right hand side, and obtain a similar bound. We then use this modified corrector step in an implementable method which is shown to take a total of O(Ilog( -)|/inlog(n)) predictor and corrector steps. Key words: Linear programming, Semidefinite programming, Interior point methods, Path following, Predictor corrector method. *Supported by the grant number CCR-9321550 from the National Science Foundation. 0

Abbreviated title: Semi-definite linear programming 1

1 Introduction This paper considers the dual pair of semidefinite linear programs: minimize C * X Ai X = bi for everyi =1,, m (1) X -O and, minimize Z=1 biyi Eim Aiyi + S = C (2) where Ai for i = 1,, m and C are n x n symmetric matrices, A * B = trace(ATB) and X >- 0 means that X is a symmetric and positive semidefinite matrix while X > 0 means that it is a symmetric and positive definite matrix. There is considerable interest in generating algorithms, and, understanding the duality, optimality conditions and the facial structure of the feasible region of the semidefinite linear programming problem. The landmark work in the former area is the paper of Nesterov and Nemirovskii [12] and their book [13], where they present a general theory based on self concordant barrier functions, and their relation to interior point methods for convex programs. Some references for the later are Alizadeh, Haeberly and Overton [2], Pataki[15] and Ramana, Tuncel and Wolkowicz [17]. Also, several extensions of the primal-dual potential reduction methods to semidefinite programming have been made and some notable papers in this regard are [1, 6, 7, 21]. There is also recent success in extending the primal-dual path following algorithms of linear programming to semidefinite linear programming. In the linear programming situation, the scaling matrices involved are diagonal, and can thus commute. The matrices involved in semidefinite programming do not necessary commute and thus the computed direction may not be symmetric. One of the main variations in these algorithms is the process adapted to achieve symmetry. Nesterov and Todd [14] and Kojima, Shindoh and Hara [8] have developed some of the earlier ones. Recently Monteiro [11] has presented algorithms, that follow a neighborhood of the central path, and, which differ in the direction adapted. 2

He considered the two directions determined by the equations X-2(XAS + XS) + X (XS + X SX SAX)X- = 2({aI- X2SX2) (3) St (XAS + AXS)S-2 + S-2 (zXSX + SAX)S = 2(aUiI- SXS ) (4) from a family presented by Kojima, Shindoh and Hara [8]. The direction determined from these systems is unique and symmetric. He analyzed algorithms using these two directions. Based on his analysis, Zhang[22] subsequently analyzed algorithms based on the direction (4). For this direction, Zhang also presented a result on the generalization of the predictor corrector method of Mizuno, Todd and Ye [10]. In this paper we present a feasible start predictor-corrector method based on the talk of Saigal [18] which presented a similar result for the linear programming problem ( see also section 5.10 of the book Saigal[19] ). Here we assume that the primal and the dual problems have interior feasible points, and thus the strong duality theorem holds, see for example, Alizadeh [1]. Freund [3] has presented an algorithm without such an assumption. Recently, Potra and Sheng [16] and'Kojima, Shida, and Shindoh [9] have presented an infeasible start predictor corrector method with some local convergence analysis. The direction we use is determined by the equation XAS + AXS = UPI - XS (5) and the direction used in the method is (-(AX + 4XT), Ay, AS) ( it can be shown that AS is symmetric ). A direction computed by such a symmetrization has been used by Helmberg, Rendl, Vanderbei and Wolkowicz [6]. We can show that the direction given by (5) also solves (4). Substituting this direction into (4), we obtain the identity below 1 AX~+AXT 1 1 AX + AXT 1 S2 (XASS + XS)S F + S-' (SX + S X )S2 2 2 S(XAS + + S SAX +ASX + S XAS AXTS ( 2 )S 2 s( 2 )s2 +s( 2 +S( ASX+S AX)S 2 (I- S XS) + XAS + AXTS) 1 1 SAXT + ASX = (aI - St2XS2 ) 2 + S. — 2( )S 2 2 1 1 2(U PI- S XS=) 3

and we see that (4) is satisfied. We use the same neighborhood of the central trajectory as one used by many papers, including Monteiro [11] and Zhang [22]. This is N(to,/3) = {(X,y,S): X >- O,S - O,t < to, 1S2XS2 - tI\F < flt} (6) where \lBII\ = E 1 E=1 B?2 is the Forbenius norm of the matrix B and 3 > 0 is a constant. We obtain the result that starting with initial complementary slackness violation of to > 0, it can be reduced toe > 0 in O(Ilog(Q-)|x/n) iterations of the predictor corrector method as considered by Saigal [18].. Such a result is also asserted in Zhang [22] for the generalization of the Mizuno, Todd and Ye [10] method. In another direction, we extend this result to a modified algorithm in which the corrector step solves a system of linear equations that differs from that of the predictor only in the right hand side. In addition, we present a variant of this method that achieves larger step sizes and solves the problem in at most O(log(Q-)\/llnog(n)) sum total of iterations of the predictor and the corrector steps. This paper is organized as follows. In section 2 we present the method. In section 3 we present some basic lemmas. In section 4 we analyze the predictor and corrector steps and obtain the main result. In section 5 we present the modified corrector step and analyze it. In section 6 we discuss some implementation issues. 2 The Method We now present the predictor corrector method we will discuss in this paper. Step 0 Let 0 < a < 1 and 0 < / < 1 be given constants and Xo > 0, y~ and So >- 0 satisfy the dual systems (1) and (2) respectively. Also, assume they belong to N(to, /) for to = 2O. Set k = 0. Step 1 Predictor Step: Solve Ai AXk = 0 for all i 1, *,m Eim AiAAyi + ASk = 0 (7) AXkSk + XkASk = -XkSk 4

for (AXk, Ayk, ASk), and define Xk = Xk + a(AXk + AXT) -k = yk + acAyk =_Y~~~~ ~~yk ~~~c~~(8) Sk = Sk + aASk tk- Xk*Sk tk n Step 2 Corrector Step: Solve Ai AXk = 0 for all i = 1, *,m Ei= AiAyk + \Sk = O (9) AXkSk + XkASk = tk -XkSk for (AXk, Ayk, ASk), and define Xk+l Xk + (AXk + AXkf) yk+l = Yk+AYk Sk+1 = k + ASk tk+1 Xk+l Sk+l tk+1 - Step 3 Set k = k + 1, and go to step 1 Some comments are in order here. Both the systems (7) and (9) have a unique solution. Also, the solution ASk and ASk are readily seen as symmetric ( a consequence of our assumptions on the matrices of the problem ), but AXk or AXk need not be symmetric. Thus we use the symmetric part of these directions in the predictor or corrector steps. 3 Basic Results We present here the basic results we need about matrices and norms. Given an n x n matrix B we define its 2 - norm as |IBI12 = maxtlr111= IIBxll2, and it is easily seen that if the matrix B is symmetric, then IIB112 = maxlAiI where Ai for i = 1,, n are the n real eigenvalues of B. For a given n x n matrix B, we define vec(B) = (B., BT,..., B.T)T and note that I[vec(B)112 = IIBIIF, where B.j is the jth column of the matrix B. 5

Lemma 1 Let A and B be arbitrary n x n matrices, with B nonsingular. Then I|ABI|| < IIAIII|IBTB112 and IIAB II < IIATAII|21BII. Proof: Note that AB = (AB.1,, AB.n) where B.j is the jth column of B. Thus l|AB||F = Z-1 ||AB.|32 ||A||E j=1 ||B.3||2 IIAII2II2BIF~ II ATA11211BII. The last inequality follows from Theorem 2.3.1 of Golub and Van Loan [5]. To see the other inequality, note that AB = ((A1.B)T, ~., (An.B)T)T where Aj. is the jth row of A, and IIAB II = Ej=1 IIAj3BR\2 < (ZEJ1 IIAj I)2)HRT2 - IIAIIIRTIBI2. ( Note, we have used here the fact that for non-singular B, I BTII2 = AmX,(BBT) = Am,,(BTBBTB-T) = Am,,(BTB) = IIB I2). For a given n x n matrix B which has all eigenvalues real, we define Ai(B) for i = 1,., n the n real eigenvalues of B, and ma,x(B) = max2Ai(B) and similarly A.nn(B). We can prove Lemma 2 Let A, B and C be n x n symmetric matrices with A = B + C. Then Anin(A) > Arnin(B)- IIC|IF and max(A) < Amax(B) + IIClIF. Proof: Follows readily by noting that IICII1 = trace(C2) = E=1 Ai(C)2 > Am,(C)2 and A~max(C)2 < IICII2 m The following result was proved by Monteiro [11]. Lemma 3 Let A and B be n x n matrices with A symmetric and B nonsingular. Then [AIIHF < IIBAB-1 + (BAB-1)TIIF. Another technical lemma follows: Lemma 4 Let A, B and C be n x n matrices such that A = B + C, and trace(BTC) > 0. Then IIBIIF < IIAIIF and IICIIF < IIAIIF. Proof: First note that IIAIIF = Ilvec(A)||2. Then, as trace(BTC) = vec(B)Tvec(C) > 0, the result follows from the fact that the largest side of a triangle is opposite its largest angle.E 6

4 Analysis and Convergence of Method In this section we will prove that the method generates a sequence of points such that t goes to zero linearly at the rate (1 - a), and a = 0( ). We now prove two simple propositions about the solutions of the systems (7) and (9). Proposition 5 For every k = 0,1, with AX = AXk or AX = AXk and AS = ASk or AS = ASk it follows that Ai * AX A i * AXT -= AX AS= AS AX = 0. Proof: The first identity is readily confirmed by simple algebra and the symmetry of Ai, and the second identity is readily confirmed by using the first two equations of the systems (7) and (9). Proposition 6 For each k = 0, 1,, tk = (1 - )tk and tk+l = tk. Proof: Note that 1(AXk + AX) * Sk + Xk * ASk = 1((AXk Sk + Xk * ASk) + (Sk e 2k~" 2 ( k 2 AXT+ASk.Xk)) = - (XkeSk+SkeXk) = -ntk. Now, tk = k - X + a(AXk Sk + AXTO * Sk + 2Xk * ASk) = (1 - a)tk. The remaining part follows by a similar argument. We now prove an important proposition. 1 1 Proposition 7 For each k = 0,1,.., let Ek SS2XkS - tkI. Then I 1 1. IIXkAXkSk IIF V< 1 _1 2. IIX ASkSk2 IF Vntk. 3. yT 2 Xk IA XS ~ |+llF n t.\Xk /\k Sk \IF < y/- tEkj IEIV ' Proof: From the third equation of the system (7) we can derive 1 1 1 _1 1 1 Xk 2 AXkS2 + Xk ASkSk = Xk 2 X,"ax k k Xk Sk 7

1 1 1 1 and, using Lemma 4, Proposition 5 along with the fact that IIX2 Sl | = trace(S kS2 ) = ntk, we thus obtain the first two results. To see the third, we note that from 1, IIXk,2 AXk S I I(Sk X)Xk k(S I 1IF 1 1. 1 1 1 1 1 1 < Sk XkS 112 IlXk ll XkSl IIIFIIS Xk-1 S 11 The result follows from the definition of Ek and part 1. 4.1 Analysis of Predictor Step We now investigate the predictor step and the resulting iterate (Xk, yk, Sk, tk). For every k, let 1 1 Ek = S2XkS -tkI 1 _ 1 Ek = S2 XkSk -kI. We can show that Lemma 8 If IIEk\\F < /tk and 1 - y,/ > O0 then Xk and Sk are symmetric and positive a1-/ definite. Proof: We will show the result for Xk. The same argument will apply to Sk as well. Since 1 I1 1 AI +AT 1 Xk is symmetric, and is positive definite if and only if Xk 2 XkXk 2 = I+aXk 2 (Xk )Xk 2 is, we note that from the Lemma 2, 1 x TXX1 + AXX T 1 Amin(I X1( 2 )Xk))~l2lX + A 2 +>AXk~Xk 2 A mA( ~I +X > 1 - 1IIX 2 2 Xk i I11FUsing the result of Lemma 1, 4 and Proposition 7 in the inequalities that follow II Ak _______A T _ 1 1 1 1 _1 - 1 AX I\\F ~ (XVkAXkXk +x1 1 Xk1 1XX F) < 1(XIIVsAXk k sX 2 II IIXkSkxSf IA1I < V.ntk tk - IIEk\1F < V~6 -_ -,~ 8

we obtain our result.. We are now ready to establish a bound on the error after the predictor step. Lemma 9 If IEklIF < ptk, 1 - a > 0, then 1 c 2n IIEklIF < ((1- a)o + (1 + 1 - a 2 _1 )) I r ))4k Proof: Note that I 1 sk (XkSk - tk)sk I + AX _ ____T + X ) = sk (XkSk + - -2 - Sk + QXkASk + 2a X Sk - tkI)Sk = S -k XZSk + oAXkXSSk kS XkASk + AX 'SkATC o = S (XkSk- 2-XkSk + (-XkSk + (AX - AX)Sk) + (Ax + AX[)A'S - tkI)Sk = (1 - a)(S XkSk -tkI) + Sk ( \X - AXk)) (AX + XT)X + SkSk From Lemma 8, Sk is symmetric and positive definite and hence its square root exists. The inequalities below follow from the Lemma 3 and the above identity. Ek\F = S2 Xk S2 -tkI IF I 1 1 S1 1S S 1 1 < S2II S2(2XS2 - tkI)S i- 2 - 2 k k k Sk + 1 S SX1 1 tk 1 Sk Xk tk S~ Ic ~ l IL/F = SS(XkSk -tkI)Sk + Sk (SkXk - tkI)SkIF -1121 -a)(S2X S t I ) + 2(S2 AX + SS + Sk AS Sk S (1 -)|Ek||F + 2y c (S 2 + CSkSSk 2 Sk 2)IIF. 2 2 2 Note that, from Proposition 7, we obtain \S2XASkSV\F ~ \\SX X FAXTXVX SkS F<ntk, II S A SkAXkS kF = S AXk SkSk F ntk, 1 1 1 1 1 1 1 1 1 1 IIS2 2T 2 T 2 2 X2 2S~ 2 ISI SAXkASkSk I2F = SXXk XkSk SXk X k IF tk+IIEkl IF - t — 1 FIIkIntkItk- \IEk\\F 9

Hence za2 tk +IIEklIF IIEklIF < (1 -a lEklF + (1 + -I )ntk 2 tk - EkIIF cy2n ~11+/ < 1 ((1 - ) + (1+ ))tk - 1-a - - - and we are done. U 4.2 Analysis of Corrector Step We now prove two important lemmas about the corrector step. Lemma 10 If IIEkIIF < 3tk and -- < 1, then Xk+l and Sk+l are symmetric and positive definite. Proof: By a similar argument to that of Proposition 7, we obtain II X SkSk 2 IF < I\tkXk Sk -k Sk F 1 1 1 1 I= (tkI - x SkX)(Xk Sk 1)F, (11) 1 1 1 Itk 1k - S IF 1 1 1 1 = (tklI -Xk SkXk )(Xk Sk )IIF. (12) Then this lemma follows by an argument identical to that of Lemma 8. U The next Lemma provides the error after the corrector step. Lemma 11 If IIEkllF < tk = /(1 -O )tk, and 1 — < 1 then I I+ 1 -/2(1)tk. IIEk+lllF < -(1 + -l( - )tk Proof: The following relations follow from Lemma 3, and by an analysis similar to that in Lemma 9, IEk+1IlF = II(Sk+l) Xk+l(Sk+l) - tkIlF 10

< - S ( Sk+l) 2 ((Sk+l) Xk+ (Sk+l) - tkI)(Sk+ )2 Sk 2 1 I 1 1 I 1 Sk 2 (Sk+l) 2 ((Sk+l) 2 Xk+l(Sk+l) - kI)(Sk+l)- 2s IIF = (X+Sk+lk - tkI)Sk + S;k (Sk+lXk+1 - kI)S2 IF 1;AXkAk + +.~ AXk 1+/A SZF. = ll k +sks 2 + S-k2 ASk + Xk S2- IIF = Ik 2 k 2 Then, using arguments similar to the proof of Lemma 9 and inequalities (11), (12), it follows that 1 SAXk SkSk 2F 1 1 1 I1ASkS F ~ II(tkI- X2 SkXk)(Xk 2k )IF S 1 _ 1 21 _ < Itki - X SkXkI i Xk 112 1 - II-II'lEkI tk~ tk- IIEkklF | Sk 2 SkAXk Sk2 |F = k2 k SkSk ||F <- t- I IjEk11 IEkI F and, using Lemma 1 and Lemma 2, IS2XkSkSk F I 1_ X k1 AXk SkSk kX k 1 1x ISXk xk I 1 2 1 X X sk sFk X tk + |IEkI||F -- iX X k IIiiA$ X IF \4- 11EkcllF <k + lI, /i 2F 1 i11 tk \ I-11 F 1 7 tk - IIEk1F tk - IIcl IF Thus IEk+l 1 <F tk+ IIEkIIF 1 |IIEk+I||F < (I+ — 1 )+- — II^kHF 2 tk - IIEkllF tk - II-EkIF i 1+P I_ < -(1 + -) (1 - a)t and we are done.1 -and we are done. U 11

4.3 The Main Result We are now ready to prove the main convergence theorem. and tk+1 = (1 - a)tk. Thus, for every e > 0, after at most O(llog( -)Iv\n) iterations of the predictor-corrector method, a solution (X(e), y(e), S(e)) will be found with X(c) * S(e) < ne. Proof: It is readily confirmed that the above choice satisfies the properties required in 1 1 the hypothesis of the Lemmas 8, 9, 10, 11, and that IIEkIIF = IIS2XkS2 - tkI IF < /tk, and IlEk~+1 F < /tk = Otk+1, and thus the sequence belongs to the neighborhood N(tk, ). The required property on tk follows from Proposition 6. Now let e > 0 be arbitrary, and define k sufficiently large so that (1 - a)to < e. With a < 1, then log( ) > klog(l - a) > -k. Thus, for k ~> -21g(-), tk < e. So for 8 n to 2 - 3ck t -k k = O(llog(O-)jl/T), the value of tk is less than equal to e. Thus the required solution is obtained. U 5 Modified Corrector Step The predictor corrector method presented in Section 2 requires that a new system of equations be solved during the corrector step. Implementations generally use the same linear -system during both the steps. In this section, we will analyze the resulting method. Thus, we replace Step 2 of the method of Section 2 by the following: Step 2': Corrector Step. Solve Ai AXk = 0 for all i = 1,,m Ei= AiA + ASk = 0 (13) AXkSk + XkASk = tkI-XkSk 12

for (AXk, Ay Sk), and define Xk+l = Xk + (AXk + AX) yk+l = k k (1 (14) Sk+ = Sk + ASk tk+l =Xk+I Sk+l Note that the matrix of the system of equations to be solved in (13) is the same as in (7). We now prove the convergence of this method. Before we do this we establish some needed lemmas. Lemma 13 For each k = 1, 2, *, tk+l = (1- a)tk. Proof: Follows by a straightforward calculation. Proposition 14 For each k = 1,2,.. lXkAXkSkI2 IF M(a)Vt), IIX-zSkSklF < M(a)Vk, 1Z AX~Xk2IF ~llF < 112XkS2 lX- -AXkS% llFllSk1 XkSkI112 < ^f + ^Vtk where fi I1a + 1+2 I+? n M(a) = (1-Ca) + -(1+ + /)(+ (1+ 1 -1 1 Proof: We will only show this for IIXk2 AXkSk2 F. The inequalities that follow use the same arguments as those of Proposition 7. 1 1 IIXk 2;AXkS I F S _I ( 1 I1 1 I= )\X~2S~ - a)(tk<I- XkS + Xk ( ((1 - a)XkSk - XkSk)Sk 2 \ F Xk Sk k~~~~~~~~~k k + Xk k~~~~~~II 13

1, AXk + AXx (1 - a)IEk\IIF + lk 2(( - a)XkSk - (Xk + a 2 )(S + aASk))Sk 2F (1 - a) - + IIX k2((XkASk + AXkSk) - X S - aXkASk, J1 -7- ||2 _a AXk2 + k / Sk)Sk IF 2 <(1 - j X -,, ( AXk -AX2 AXk+AX,)s 1-f k 2 2 (1 - a) + - (1 + < ((1 - a) / + a-(1 ' -1J -3 2 tk + IIEkIIF )2,+ tk + IIEkllF || ntk fltk -~+ -(1 _________ ) tk tk - IIEklIF t 2 + tk - IIEkllF t- IEk A1-)+ 2t (1 + 1-)) -1+^ r- 5-( /1+- v'. and we are done.. We now establish the two required lemmas that show that the resulting matrices after the modified corrector step are positive definite and that they belong to the neighborhood N(tk+l, ). Lemma 15 If IIEkllF < t,, 1 - a/ - M(c_ ) > O, then Xk+l and Sk+l are symmetric Lemma 15 If IIEkl[F _< Otk, I - a 1-/ and positive definite. Proof: Using the identity Xk+l = Xk + (AX/ k + AXT) + (AX, + AX'T), this lemma 2 2 (A L~~C k + A~~C T ~~k ),'this lemmaII follows by an argument identical to that of Lemma 8 and 10.. Lemma 16 If IIEklIF < tk, 1 - a _ - M > 0 then /l-/3 11Ek+11F < \(\_( 1 + -I- a _ )M(ca)x/n + -(1 1-/3 2 + J)M(a) )tk+l. I1-/3 Proof: Note that I 1 1 _ 2 1 Sk (Xk+l Sk+l — tkI)Sk -= S (XkSk AXk + (XSk) AXk + AXT )As + (Xk + c -- 2 - )A~ 14

+ 2 Sk-tkI)Sk I. +XkASk + AXkSk -= S2(XkSk + ( X) +Xk( ) + CAS( AX k Xk ) X)ASk 2 2 z +aAXk +AX + 2 AXk +- xASk - T I)Sk 2 I - I- AXk + A.XT = S (XkSk - +(tkXkSk) + (tk - kSk + (AXk - AXk)Sk) + a ASk Aa 2 2 2 + AXk +A2 A X.S+k +A +a' --- -— AI +s. — -Ask - tkI)Sk- S2f, IAik + 'Af^Jk + a k)SX, AXk+A~ k 2 2 2 2 + k k (A X - A k ). Then IIEk+1IlF = ||(Sk+l)2Xk+l(S k+l) - tklI|F < s|| S(Sk+l)- 2 ((Sk+l)2 Xk+l(Sk+l) -t)(Sk+l)2 Sk IF + IISk 2 (Skl )2 ((Sk ) 2 Xk+l(Sk+l)2 -tkl)(Sk+l1) 2 S2 IF 1 1 1 1 1 += -||IS2(XkSk+l((k+l)Sk +l (Sk+l +- tk)(tk+l)SkF = j|S|(X l k+l - t-+)S; S2 (Sk+lXk+l - tk\)S F 2I AXk + AX[ a AXk + AX' = S(a AS-k t+ C-2 ASk + a2 + 2 ASk )Sk 2 1 1 ( 2A 2 2AXkAk ) AX, + ^ AXIT Ax A 17 - +( /( ASk + a- ASk + ~A/)~ | < IS2- AXfjAX Ias + AX k + k A AXk + AXk A)S) 2 2 2have - II1e(Q' — - 2 /x + have$;+ -- -F ll. We have IS S 1 I S Xk /k Sk Sk I I F = |Sk AXkXk Xk ASkSk 11F 1 1 1 1 ~2II SAXkx 2IIIXASkSV IIF 1 1 I 1 1 1 - I tk- I lEkF ll = \Sk XXk Xk ASkSk F IISk AXk X k II XIk ASkSk I F I 1AXA kI[ ffc XkLZ- I'LJIF 15

I 1 I\Sk2 XkSk.Sk 11F IlSk q-k /\ Sk Sk I I F IlIS 2X Skk2IIF 1 < -ntkM(a) X/t, = IIS aXk2Xk XASkSk |2IF 1 1 1 1 1 1 1 1 < M(a)tkIS XkSk I IXk Xk XkS 2 IIFIISk 2 Xlk 2112 tk + IIEkIIF ) M ( a) It- - i/ <tk - IIEkllF 1 1 _1 1 _ 1 IIS2ZXTX- k IIFIIX / 2SkSk2 IF ( Sk AXk x IF xkASkSk'k IF < /(1+ -kMa)(a)t t < (JSk IXkAF + II XX A /k kSk; IIF) ~ _ 2AX 2 1IIX 1 _2IIF -zI x2N xtTx IIFIIX2/s s 2~11F) 2 1,)-/~ Hence IIEk+l \F < 1 (a(1 + )M(a)/ + I (1 + i/ )M(a)2)tk+l. - 1-a I - 2 1-/. Theorem 17 Let a < 2o,',/ = 0.1. Then for every k = 1,2,.., (Xk, yk,Sk) e N(tk, /) and tk+ =-(1 - a)tk. Thus, for every e > 0, after at most O(llog( )x/ni) iterations of the predictor-corrector method, a solution (X(e), y(e), S(e)) will be found with X(e) * S(e) < ne. Proof: Using the Lemmas 15 and 16, the proof is identical to that of Theorem 12.. 6 An Implementable Method In this section we will present an implementable method that generates a larger step size than the theoretical one determined by Theorems 12 and 17. And some numerical issues of implementation will also be discussed. 16

6.1 A Practical Method The step size a obtained in Theorems 12 and 17 is generally too small for practical implementation. We present below a practical predictor corrector method based on these theorems. Step 1' Predictor Step: Solve Ai AXk = 0 for all i =1,, m E=_1 AiAyi + ASk = 0 (15) AXkSk + XkASk = -XkSk for (AXk, Ayk ASk). Step 2" Step Selection: Set I = 0 and ao = max{a: Xk + 2(AXfk + AX[ ) > 0, Sk + aASk > 0 and a < 1}. If co = 1 stop, otherwise set oo = 0.99aco. Step 3' Set 1 Xk,l = Xk + al(AXk + AX ) yki = yk + Ayk Sk,l - Sk + CalASk Step 4' Corrector Step: Set Xk = Xk,l, yk = yk,l, Sk = Sk,l, tk = (1- al)tk and solve system (13). Step 5' Set Xkl,l Xk + -(AXk + A ) yk+l,l yk +Ak Sk+l,l = Sk + ASk Step 6' If (Xk+l,, yk+1,l, ISk+l,l) E N((1 - Ql)tk, f), then set Xk+ = Xk+l,l, yk+1 = Y k+l, and Sk+l = Sk+l,l, tk+l = (1 - ca)tk, k = k + 1 and go to Step 1'. Otherwise, set cl+l = al, =1 + 1, and go to step 3'. 2 1 'l 17

We can show that: Lemma 18 If ao = 1 in Step 2", then Xk + (AXk + AXk), yk + Ayk, Sk + ASk solves the semidefinite programming problem. Proof: The result follows from Lemma 13. 1 We are now ready to prove the main theorem. Theorem 19 Let / = 0.10. Then for every e > 0, after at most O(Ilog( -)Ilog(n)/n) total predictor and corrector iterations of the above method, a solution (X(e), y(e), S(e)) will be found with X(e) * S() < ne. Proof: We first observe that after at most I = O(log(n)) corrector iterations of Step 2' to Step 6', al < 2O' and thus the resulting iterate will lie in N(tk+1, /) by Theorem 17, and the result follows. d 6.2 Some Implementation Issues We discuss here the linear system to be solved in determining the directions, and a method for exploiting the sparsity of the matrices involved. Instead of the system (7) solved in section 2, we will solve AX'T by replacing the third equation of the system with the following: SkAX[ + ASkXk = -SkXk. Then similar to the system for linear programming, the corresponding linear system can be represented as follows: A 0 0 vec(AXk) 0 0 AT I Ay = 0 Fk 0 Gk vecASk vec(-SkXk) where vec(A1)T A =,Fk = I Sk, Gk = Xk I. vec(Am)T 18

Note that A 0 B = [AijB] is Kronecker product. We now show that Fk lGk is a symmetric and positive definite matrix. Lemma 20 F; lGk is a symmetric and positive definite matrix. Proof: Note that Gk = PGkPT where P is a permutation matrix and Gk = I Xk. Since Gk is symmetric and positive definite, Gk is symmetric positive definite. F lGk = Xk ~ Sk1 is symmetric. With the fact that Fk is symmetric and positive definite, since Fk lGk has 1 1 the same eigenvalues as G F7 1G,, the required property follows. 1 Then the linear system can be solved by Ayk = (AFk.lGkAT)-1 (-A)Fk lvec(-SkXk) (16) m ASk = - E yA i=l AX[ = S (-SkXk - ASkXk) As can be readily confirmed, it will require 0(mn3) multiplications to compute GkAT, O(mn3) multiplications to compute F11 (GkA), O(m2n2) multiplications to compute A(FrF1GkA), and 0(m3) multiplications to compute (AF/TlGkAT)-1. A consequence of Theorem 19 is the following Corollary 21 Let / = 0.10. Then for every e > 0, after at most Ilog(i )l(O(mn35 + O(m2n2'5) +O(m3n0"5)) total multiplications, a solution (X(e), y(e), S(e)) will be found with X(e) * S(e) < ne. Proof: This multiplication count can be obtained by observing that in Step 4', only the right hand side changes between the predictor and corrector steps. Also, between the at most O(log(n)) corrector steps, the only change in the right hand side is the value of a, and thus the new solution can be found in 0(n2) multiplication for each of the subsequent corrector steps. Thus the total multiplications is at most Jlog(f)l(0(mn35)+ O(m2n25) +0(m3n05)) for all the predictor steps, and, at most Kl(mn3'5 + m2n2'5 + m3n0-5) + K2n251log(n) multiplications for all the corrector steps. U 19

The computational burden in above system is in the calculation of (AF-lGkAT) l. The matrix AFIiGkAT is dense even when A, F7l' and Gk are sparse. This then renders the methods of sparse Cholesky factorization, George and Liu [4], ineffective. But the method presented in Saigal [20] may be able to exploit this sparsity. We now show how this may be so. Choose 0 > 0 sufficiently large so that I - 1FlGk 1 0. Also let L be the Cholesky factor of A ( i.e., AAT = LLT ). Then it is readily confirmed that (L-'A)(L-'A)T = I. In that case if Avec(Xk) = b, the linear system of (1), is modified to the equivalent system L-1Avec(Xk) = L-lb, the resulting matrix in the system (16) will be L- AF- 1Gk(L-1A)T Let Hk = L-1AFkl Gk(L-1A)T = Ok(I- Nk) where Nk = L-1A(I - LFk Gk)(L-1A)T We can then show that 1 1 Lemma 22 For all 0 > Amax(Fk 2GkFk 2), Nk is a symmetric and positive definite matrix with spectral radius strictly less than 1. Proof: The first part follows from the choice of 0. Since Fk-1Gk is positive definite so is Hk. Thus 1ZTHkZ = 1 - ZTNkZ > 0 for every ||Z112 = 1, and we have the second part of the lemma since zTNkz > 0. 1 The idea now is to solve the system by writing HJ1 = -(I + Nk + Nk + *. ) and Saigal [20] shows how this infinite series can be summed iteratively. The application of this methodology requires the multiplication of a vector q by the matrix Nk. To see how sparsity is preserved by this technique, consider generically multiplying a vector q by Nk to obtain the vector p. Then the following is simple to generate: Step 1 Solve LT q q. Step 2 Define = A(I - 1 Fk-Gk)AT1 Gk)A q. Step 3 Solve Lp = In steps 1 and 3, sparse triangular systems are solved ( provided the Cholesky factor of A is sparse ), and in step 2 multiplication by the sparse matrices A, AT, Gk and F7-l is 20

involved. Note that in Step 1 and 3, 0(m2) multiplications are required and in Step 2, 0(mn2) + O(n3) multiplications are required. 7 Acknowledgement We thank Professor Masakazu Kojima for pointing out an earlier error in Lemma 2. References [1] F. Alizadeh, "Interior point methods in semidefinite programming with application to combinatorial optimization", SIAM Journal on Optimization, 5(1995), 13-51. [2] F. Alizadeh, J. P. Haeberly, and M. Overton "Complementarity and nondegeneracy in semidefinite programming", manuscript, March 1995, submitted to Mathematical Programming. [3] R. M. Freund, "Complexity of an algorithm for finding an approximate solution of a semi-definite program with no regularity assumption", Technical Report Number OR 302-94,Operations Research Center, Massachusetts Institute of Technology, Cambridge, MA, December 1994. [4] A. George and J. W-H. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall Inc., New Jersey, 1981. [5] G. H. Golub, and C. E. V. Loan, Matrix computations, Second edition, The John Hopkins University Press, Baltimore, MA 21211, 1989. [6] C. Helmberg, F. Rendl, B. Vanderbei, and H. Wolkowicz, "An interior-point method for semidefinite programming", Manuscript, Programming in Statistics and Operations Research, Princeton University, 1994. To appear in SIAM Journal on Optimization. [7] F. Jarre, "An interior-point method for minimizing and maximum eigenvalue of a linear combination of matrices," SIAM Journal on Control and Optimization, 31(1993), 1360-1377. 21

[8] M. Kojima, S. Shindoh, and S. Hara, "Interior-point methods for the monotone linear complementarity problem in symmetric matrices", Research Reports on Information Sciences, Ser. B: Operations Research B-282, Dept. of Information Sciences, Tokyo Institute of Technology, 2-12-1 Oh-Okayama, Meguro-ku, Tokyo 152, Japan, April 1994(revised October 1995). To appear in SIAM Journal on Optimization. [9] M. Kojima, M. Shida, S. Shindoh, "Local convergence of predictor-corrector infeasible-interior point algorithms for SDPs and SDLCPS", Research Reports on Information Sciences, Ser. B: Operations Research B-306, Dept. of Information Sciences, Tokyo Institute of Technology, 2-12-1 Oh-Okayama, Meguro-ku, Tokyo 152, Japan, December 1995. [10] S. Mizuno, M. J. Todd, and Y. Ye, "On adaptive step primal-dual interior-point algorithms for linear. programming," Mathematics of Operations Research 18 (1993), 964-981. [11] R. D. C. Monteiro, "Primal-dual path following algorithms for semidefinite programming", Manuscript, School of Industrial and System Engineering, Georgia Tech., Atlanta, GA 30332, September 1995. [12] Y. Nesterov and A. Nemirovskii, "Self-concordant functions and polynomial time methods in convex programming", preprint, Central Economic & Mathematical Institute, USSR Acad. Sci., Moscow, USSR, 1989. [13] Y. Nesterov and A. Nemirovskii, Interior Point Polynomial Methods in Convex Programming: Theory and Applications, Society for Industrial and Applied Mathematics, Philadelphia, 1994. [14] Y. E. Netsterov, 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, 18453-3801, 1995. 22

[15] G. Pataki, "On the facial structure of cone-LP's and semidefinite programs", Management Science Research Report # MSRR-595, Graduate School of Industrial Administration, Carnegie Mellon University, February 1994. [16] F.A. Potra and R. Sheng, "A superlinearly convergent primal-dual infeasible-interiorpoint algorithm for semidefinite programming", Department of Mathematics, University of Iowa, Iowa City, IA 52242, October 1995. [17] M. Ramana,L. Tuncel, and H. Wolkowicz, " Strong duality for semidefinite programming", Technical Report CORR 95-12, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada, May 1995. [18] R. Saigal, "Tracing homotopy paths in polynomial time". Talk given at ORSA/TIMS Joint National Meeting in Washington, D. C., Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, MI 48109, 1988. [19] R. Saigal, Linear Programming: A Modern Integrated Analysis, Kluwer Academic Publishers, Norwell, MA, 1995. [20] R. Saigal, "An infinitely summable series implementation of interior point methods", Mathematics of Operations Research, 20(1995) 570-616. [21] L. L. Vandenberghe, and S. Boyd, "Semidefinite programming," manuscript, Information System Laboratory, Stanford University, CA, 1994, to appear in SIAM Review. [22] Y. Zhang, "On extending primal-dual interior point algorithms from linear programming to semidefinite programming", Technical Report TR95-22, Dept. of Mathematics and Statistics, University of Maryland Baltimore County, Baltimore, MA 21228-5398, October 1995. 23