POLYNOMIALLY BOUNDED ELLIPSOID ALGORITHMS FOR CONVEX QUADRATIC PROGRAMMING TECHNICAL REPORT 80-3 by Sung J. Chung and Katta G. Murty Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, Michigan 48109, USA Research effort partially supported by the Air Force Office of Scientific Research, Air Force Systems Command, USAF, under grant No. AFOSR 78-3646. The United States Government is authorized to reproduce and distribute reprints for governmental purposes, notwithstanding any copyright notation hereon. This paper was typed by Mrs. Geraldine Cox. June 1980

ABSTRACT We show that the ellipsoid algorithm of N. F. Shor and L. G. Khachiyan, can be applied to solve convex quadratic programming problems with integer data in polynomially bounded time. KEYWORDS Convex quadratic programming, linear complementarity problem, nearest point problem, positive semi-definite matrix, ellipsoid algorithm, polynomially bounded algorithm.

1. Introduction The ellipsoid algorithm of N. Z. Shor and L. G. Khachiyan[9,11,26] processes systems of linear inequalities and linear programming problems with computational requirements that are bounded above by a polynomial in the size of the problem. Here we show that the ellipsoid algorithm can be extended to solve convex quadratic programs with integer data in polynomial time. It is well known that every convex quadratic programming problem can be posed as a linear complementarity problem (abbreviated here as LCP, see references [5,16,21]), associated with a positive semi-definite (abbreviated in the paper as PSD) matrix, and vice versa; and hence the methods described here provide polynomially bounded algorithms for processing this special class of LCPs. This clearly establishes that convex quadratic programs and LCPs associated with PSD matrices belong to the class P of problems, which is the class of problems solvable by polynomially bounded algorithms. Algorithms described in this paper can only process LCPs associated with PSD matrices, and in fact S. J. Chung [ 3] has shown that the LCP associated with a general matrix is strongly NP-Complete. Even the LCP associated with a negative definite matrix (abbreviated in the sequel as ND matrix) is NP-Complete, and in Section 5, we briefly explore the fundamental difference between LCPs associated with PSD matrices and ND matrices, that accounts for the difference in their computational complexity. Most of the work in this paper was carried out soon after the technical report of P. Gacs and L. Lovasz on Khachiyan's algorithm [ 9] became available in August 1979, and the version of the ellipsoid algorithm for solving nearest point problems appeared in the technical report [4]. Similar work has been carried out independently by several groups of researchers, among

2 which we became aware of those of P. C. Jones and E. S. Marwil [12], I. Adler, R. P. McLean and J. S. Provan [1], and M. K. Kozlov, S. P. Tarasov and L. G. Khachiyan [14]. The organization of the paper is as follows: In Section 2 we present the nearest point problem which is a special convex quadratic programming problem that leads to an LCP with positive definite (abbreviated in the sequel as PD) symmetric matrix, describe the ellipsoid algorithm for solving it, and prove that it obtains the solution of the problem in polynomial time. Our estimates of the running time of this algorithm are generous in the sense that emphasis is placed on proving that the algorithm is polynomially bounded, but not so much in obtaining the exact worst case bound on the running time. This algorithm has been coded by Y. Fathi, and comparative computational experience of this algorithm, and other algorithms for solving the nearest point problem described in [7 ] is summarized at the end of Section 2. In Section 3 we discuss the application of the ellipsoid algorithm to solve LCPs associated with PD matrices and prove that it is polynomially bounded. In Section 4 we develop the application of the ellipsoid algorithm to solve LCPs associated with PSD matrices and prove that it is polynomially bounded. We use regular style superscripts to distinguish between vectors, as in 1 2 x x. We also need exponents, and in order to distinguish between exponents and superscripts, we use only bold letters to indicate exponents, for example ar indicates a to the power of r. Rn = n 2 deos For x cR, || x ||= z x. denotes the usual Euclidean norm of x. j=l J If D is a matrix; we denote by Di. the ith row vector of D; and by D the jth column vector of D.

3 A vector a = (a,...,a) is nonnegative (denoted a > O) if aj > 0 for all j. It is positive (denoted a > O) if aj is strictly positive for all j. It is semi-positive (denoted a > O) if a > 0, but a 4 0. For applications of the LCP see [13, 17, 23]. 2. THE NEAREST POINT PROBLEM Let B be a given integer square nonsingular matrix of order n. Pos (B) = {x: x = Bz, z = (Zls,.,zn) > 0}. For x E Pos(B), z = B- x is known as the (nonnegative) combination vector corresponding to x. We consider the problem of finding the nearest point (in terms of tie usual Euclidean distance) in n the simplicial cone Pos(B) to a given integer point b E R". This problem will be denoted by the symbol [B;b] and is called a nearest point problem of order n. For n = 1 the problem is trivial, so in the sequel we assume n > 2. [B;b] is equivalent to the quadratic program: Find z to Minimize -bTBz + z(BT )z ~~~~~~'2 () Subject to z = (Z1...,zn) > 0 The solution of (1) can be obtained by solving the LCP (see [5,16,21]) w - (BTB)z = - BTb w > 0, z > 0 (2) w.z. = 0, j = 1 to n where w = (w1,...,wn) is a column vector of variables in R. Let M = B B, q = - BTb. Then (2) is the LCP denoted by (q, M) and can be written in the familiar form

4 I w - M z = q w > O, z > 0 (3) wz = 0 Since M is a P-matrix (2) or (3) has a unique solution (w, z) (see [20,22,25]) and then z is the optimum solution of (1) (see [ 8, 22 ]). If b c Pos(B) then b is itself the solution of [B;b] and (w = 0, z = B lb) is the unique solution of (2). So we assume that b 4 Pos(B), and in this case, the solution of [B;b] is a point on the boundary of Pos(B). Since we are assuming that b ~ Pos(B), b f 0. In the LCP (3), the pair of variables (w., zj) form the jth complementary pair of variables and each variable in this pair is the complement of the other. In any solution of (3), at least one variable ineach of the complementary pairs must be zero. The vector (yl-...,Yn) is called a complementary vector of variables in (3) if yj c {wj, zj} for each j = 1 to n. A complementary vector of variables for (3) is called a complementary basic vector if the set of column vectors corresponding to these variables in the system of equality constraints in (3) is linearly independent. A complementary basic vector for (3) is said to be a complementary feasible basic vector for (3) if the solution obtained by setting all the nonbasic variables to zero and then solving the remaining system of equality constraints in (3) for the values of the basic variables, satisfies the nonnegativity restrictions on all the variables; and in this case that solution obtained is known as the complementary BFS (basic feasible solution) of (3) corresponding to that complementary feasible basic vector.

5 SOME PRELIMINARY RESULTS: THEOREM 1: The set of feasible solution of xB x >:0 (4) BT(x-b) > 0 has a nonempty interior. PROOF: We want to show that B lx > 0 (5) BT(x-b) > 0 has a feasible solution x. Clearly (5) has a feasible solution iff B x >0 Bx-BTb Xn+l > 0 (6) Xn+l > has a feasible solution X... By Gordan's theorem of the alterxn+l native (see [181) (6) has a feasible solution X iff there exists no fr E Rn, E Rn, y E R which together satisfy -1 T 0 rTrB + -pB = - pBTb + = 0 (7) (1T, a, Y) > 0.

6 From the first n constraints in (7), we have pBB = - r < O. Since B B is PD, we know that the system pB B < 0 (8) I > 0 has the unique solution 1 = 0 (or otherwise there would exist a p $ 0 such that BT B p < 0, a contradiction to the positive definiteness of B B). So in any feasible solution to (7), p will have to be zero, which implies in turn that aT and Y will have to be zero too, a contradiction. So (7) cannot have a feasible solution. Hence the set of feasible solutions of (4) has a nonempty interior. Q.E.D. THEOREM 2: Let K be the set of feasible solutions of (4). Let S be the sphere determined by (x - b/2)T (x - b/2) = bT/4 (9) K n s consists of a single point, and this point is the nearest point in Pos(B) to b. Also, let E be the ball with S as boundary. Then K n E is the set containing this single point. PROOF: We want to prove that the system B x > 0 BT(x-b) > 0 (10) (x-b/2)T (x-b/2) = bTb/4 has the nearest point in Pos(B) to b as the unique solution.

7 Let x be the nearest point in Pos(B) to b. Let z = B x, w q + Mz. By earlier discussion (also[8,22]), (w, z) is then the solution of the LCP (2) or (3). So z = B- > 0, 0 < = q + Mz = -B BT + B B T(-b), from the definition of M and q. And (x - b/2)T (x - b/2) - (bTb/4) = -T- -T T.TT T: x x - x b = x (x-b) = z B (x-b) = w = 0 from (2). So x is a solution of (10). Conversely, suppose x is a solution of (10). Define z = B x, w = BT(x-b). From the last equation in (10) we have 0 = (x - b/2)T (x - b/2) - (b b/4) = x (x-b) = zw. Also from the definition of M, q, we have = BT(x-b) = -BTb + BT B-1-x = + Mz. These facts imply that (w, z) defined here is a solution of the LCP (2) or (3), which by earlier discussion implies that x is the nearest point in Pos(B) to b. Also E = {x: (x - b/2)T (x - b/2) bb/4} For all x E K we have (x - b/2)T (x - b/2) = xT(x-b) + bTb/4 =(B-x)T BT(x-b) + bTb/4 > bTb/4. Therefore K n E = K n S Q.E.D. THEOREM 3: The unique solution of (10) is an extreme point of K. PROOF: From known results about LCPs [5,16,21,22], the unique solution of the LCP (q, M), (w, z), is an extreme point of (3). So z is an extreme point of - Mz < q (11) z > 0

8 Since M = BTB, q - B b, we notice that if z is a solution of (11), then x = Bz solves (4); and conversely if x solves (4), then z = B-1x solves (11), Hence there is a 1-1 correspondence between solutions of (4) and (11). So, since z is an extreme point of (11); x = B z, which is the unique solution of (10) by Theorem 2, must be an extreme point of (4). Q.E.D. Let L1 be the total number of digits required for specifying the data in B = (bij), b = b. in binary form. So we have approximately n L1 = (l + log2n + Z (1 + 1og2(|b.i + 1)) + E ( 1 + log2(|bil + 1))1 (12) i=1 to n i=1 j=l to n = BT q = = - BT Since M = (mi.) = B B and q = (q) - B b, each m.. or qi is a sum of n terms, each term being a product of two entries from (B. b, or the square of an entry in (B b. So each m.j or qi is of the form y1Y2 + Y3Y4 +.. + Y2n-l Y2n where the y's are entries from (B b. So we have log? (mij) = log2 (Y1Y2 +..+ Y2n-l Y2n) < og2?((|jj + 2) 2)( + 2 +...+ (!Y2nll + 2)(12nl + 2)) < log2((1yll + 2)(Y21| + 2)(1Y31 + 2) - (Y2nl + 2)) (13) since each y is an integer, (|y| + 2) is an integer greater than or equal to 2, and hence, the sum of terms like this is less than the product of these terms. Also 10o2 (|yI + 2): 1 + 1 ( +1). So from (13) and (12) we see that 1og2(m i) - L1'

9 Let L2 = n(n+l)(L1 + 1) So, by the above, the total number of digits needed to specify the data in the system (3) is at most L2. THEOREM 4: If (w, z) is an extreme point of (3), then any wi or zi is either -L2 0or > 2 PROOF: Remembering that L2 is the size of the system (3), this theorem follows from the results of [-9,11]. Q.E.D. From the results of [9,11], the absolute value of the determinant of L B is at most 2 1/n. The same bound also holds for the determinant of any submatrix of B. So there exists a positive integer < 2'ln such that all the data in the system -1 BB x > 0 3B x 1 O (14) B'(x-b) > 0 - 1 2 are integers. The absolute value of each entry in gB is < [(2 )/n] (since it is less than or equal to a subdeterminant of B times B). Hence the size of (14), the total number of digits in the data in (14), is at most L3 where L3 = (n(2n + 1) + 1) L1 (15)

1'0 -L3 THEOREM 5: The length of any edge of K is > 2 PROOF: If the edge is unbounded, the theorem is trivially true. Each bounded edge of K is the line segment joining two distinct adjacent extreme points of K. Let x1, x be any two distinct extreme points of K. From the results of [9,11] and the fact that (4) is the same as (14), we have x = (up11/v1, unl /v1) 2 x = (U12/V2,..., Un2/V2) where v1, v2 and all the uij's are integers; and v1, v2 are both nonzero; L 1 2 and I|v, Iv21 and all luij| are <2 I/n. Since x x, either there exists a j such that lul - uj2 > 1, or ujl = uj2for all j and Iv1 - v2 > 1. 1 2 -L3 These facts together imply that there exists a j such that x. - x.1 > 2 ~1 2 ~L This clearly implies that I xl - x 21 > 2 3. Q.E.D. THEOREM 6: Let e be a positive number < 22(n+l) L1 and let E1 be the ball (x - b/2)T (x - b/2) < (c + b 4)2 (16) Then the n-dimensional volume of K n E is greater than or equal to n - (n+l)L3 ~n2. PROOF: K, the set of feasible solutions of (4) or (14), is the intersection of the pointed cone {x: B- x > O0 with the translate of a pointed cone {x: BT(x-b) > 0}, with a nonempty interior by Theorem 1. The intersection S n K consists of a single point, say Vo; and E1 F K contains all the points in K in an E - neighborhood of VO, and hence has a nonempty interior and a positive n-dimensional volume.

t \V V bb/2 \ E / I 1\ /S / Figure 1: The volume of E1 n K is greater than or equal to the volume of the shaded simplex.

12 If one takes a sphere of radius a, a concentric sphere of radius a+e, and a hyperplane tangent to the smaller sphere at a boundary point x on it, then a tight upper bound on the distance from x of any point in the larger sphere on the side of the hyperplane opposite the smaller sphere is (L -1) 2 2a E +. Also the radius of E is bb/4 < 2. From Theorem 3, V0 is an extreme point of K, and every edge of K through V0 has a length -L3 > 2 by Theorem 5. These facts and the choice of c here, together imply that every edge of K through V0 intersects the boundary of E1. Let V1,...,Vn be points along the edges of K through V0 that intersect the boundary of E1, at a distance of at most 1 but greater than c from V0, such that {VO, V1*.Vn} is affinely independent. The portion of the edge between V0 and Vi lies inside E1 for at least a length of E. See Figure 1. If V.i() is the point on the edge joining V0 and Vi at a distance of c from V0, the volume of E1 () K is greater than or equal to the volume of the simplex whose vertices are VO, Vi(c) for i=l to n. From the choice of Vi, Vi(E) - VO = Y(Vi - VO) where Y > E. So in this case the volume of E rl K is greater than or equal to n! (determinant of (e(V1 - V0) *...: E(VJ - VO))I n -e! I(determinant of ((V1 - VO):.. (Vn - V)) n> i2 fn rom theresultsIin Q \. =! (determinant of( \V' ~1 V n -(n+l)L3 from the results in [9,11]. Q.E.D.

13 In the sequel, we will denote the unique point in S n K by x (this was called V0 in the proof of Theorem 6). Let z = B x, w B (-b). By earlier discussion (w, z) is the solution of the LCP (2) or (3), and it is an extreme point. THEOREM 7: For any ^ c E1) K, define 2 = B' x and w = BT(x-b). Then the following hold, for all j = 1 to n. L 2L zj-xjl < 21 - jz. - z.j < n2 E 3 J = 2L |Wj - Wj < n2 1 PROOF: Using the results in [9,11.] we see that the value of any entry in B-1 has an absolute value less than or equal to 2L1, and the same fact obviously holds for BT. As mentioned in the proof of Theorem 6, if one takes a sphere of radius a, a concentric sphere of radius a+c, and a hyperplane tangent to the smaller sphere at a boundary point x on it, then a tight upper bound on the distance from x of any point in the larger sphere on the side of the hyperplane opposite the small sphere is 2cc+ e As the radius of E is /4 < 2-,theresults in the theorem follow from this fact and the definitions of E, S, E1, w, z. Q.E.D.

14 THEOREM 8: Let x be an arbitrary point in E1 F K, and let z, z be as defined above..If < 2(n 2 (17) < 2-2(n+1)2(L1+l ) (17) then -L2 z. < - 2 if j is such that z. = 0 (18) J 4 J 3 -L > (-)2,=, if j is such that z. > 0. 4 3 PROOF: This follows from the results proved in Theorems 7 and 4. Q.E.D. THEOREM 9: Let x be the nearest point in Pos(B) to b, and z = B Let J = {j: Zj > 0}. Define the vector of variables y = (yj) by y; = z.i f j E J 3 J =w. if j J Then y is a feasible basic vector for (2) or (3) and the complementary BFS corresponding to the basic vector y is the solution of this LCP. PROOF: By the discussion earlier, if w = Mz + q, then (w, z) is the solution of the LCP (2) or (3). This result that the basic vector y defined as above is a complementary feasible basic vector is well known about LCPs associated with positive definite matrices or even P-matrices [8,22]. Q.E.D.

15 THE ALGORITHM -2(n+1)2(L+l ) *-1 Fix e = 2. Consider the following system of constraints -B lx < (19) - BT(x-b) < 0 which is the same as (14) or (4); and the quadratic constraint (16). Define x= (b/2), Al = I(e +4/ 7)2 (20) where I is the identity matrix of order n. Given any point x E Rn and a symmetric positive definite matrix Ak of order n, define E(xk, Ak) to be the ellipsoid E(xk Ak) = {x: (x-xk) A1 - (21) El = E(x, Al) is the ball defined by (16). Here we describe a modification of Shor-Khachiyan's ellipsoid algorithm [9,11.] to find a point in El n K, that is, a point satisfying (19) and (16). Let N = 8(n+1)4(Ll+l). With x, A1, E1 go to Step 2. GENERAL STEP r + 1 Let xr, Ar, E = E(xr, A ); be respectively the center, positive' r r definite symmetric matrix, and the ellipsoid at the beginning of this step. If xr is feasible to both (19) and (16) it is the point we are seeking. In this case, terminate the ellipsoid algorithm. Call xr as and go to the finaZ step described below. If xr violates at least one of the constraints in (19) or (16), select an inequality constraint

16 ax < d (22) violated by xr, as described in one of the two cases below. CASE 1: xr 4 K So, in this case, xr violates one or more constraints in (19). In this case select (22) to be the constraint in (19) that xr violates most. Break ties arbitrarily. CASE 2 r xr CASE 2: xr ~ K BUT xr E1 r So, in this case, x satisfies all the constraints in (19), but violates (16). Find the point of intersection Er, of the line segment joining xl and xr with the boundary of E1, (x - x)T (x - x1) = (c + bTb/4)2 (23) Actually r = lxi + (l-)xr, where X = 1 - ((c + bTb/4 )/ Ilxr - x l). In this case, choose (22) to be the half-space not containing x, determined by the tangent plane of E1 at its boundary point. Thus in this case "ax = d" is the tangent plane of E1 at r, and xr violates (22). See Figure 2.

17 K 1 b/2 \ \ \ Half-space ax < d. Figure 2: Construction of "ax < d" when x satisfies (19) but violates (16).

18 Now define (see [10,15] among others) d - axr or I T r+l =r 1 rn ( r \ (24) (l-y) )n 2\( l-nyr (r (ra )(A aTT\ 2 A1 +n aAra Ar+ ( l) (Ar - (l)(^ -) ( 7 7 -- With xr, A +, Er = E(x 1 Ar+l) move to the next step in the algorithm. r+l r+l After at most N steps, this ellipsoid algorithm will terminate with the point xr in the terminal step lying in E1 rn K. Then go to the final step discussed below. FINAL STEP: Let the center of the ellipsoid in the terminal step be x (this is the point xr in the last step r of the ellipsoid algorithm). Let B. Define J to be ^ >(3 2 J = {j: j such that zj () 2 = Define y = (yj) by = z. if j ~ J Yj j3 =w. if j J Then y is a complementary feasible basic vector for (2) or (3) and the BFS corresponding to it is the solution of the LCP (2) or (3), If (w, z) is the solution, x = Bz is the nearest point in Pos(B) to b.

19 PROOF OF THE ALGORITHM Let xr, Ar, E = E(xr, A ), be the center, positive definite symmetric r' r matrix, and the ellipsoid at the beginning of step r + 1. The inequality (22) is choosen in this step r + 1 in such a way that x violates it. In the hyperplane "ax = d" decrease d until a value d1 is reached such that the translate "ax = dl" is a tangent plane to the ellipsoid Er, and suppose the boundary point of Er where this is a tangent plane is n r Then Er+, = E(xr+l Ar ) is the minimum volume ellipsoid that contains Er n {x: ax < d}, (the shaded region in Figure 3), has nr as a boundary point and has the same tangent plane at nr as Er.

20 Hal f-space ax < d Eax = o ax = d Figure 3: Construction of the new ellipsoid Er+l in the modification of Shor-Khachiyan's algorithm. From the manner in which the inequality (22) is selected, it is clear t! Lt if ErD E1 n K, then Er+ E1 n K. Arguing inductively on r, we conclude that every ellipsoid Er constructed during the algorithm satisfies ErD E1l K (25) r 1

21 From Theorem 6, the volume of E1 K is > 2-4n(n+l) (L1l) From [9,11], the volume of E gets multiplied by a factor of e-(1/2(n+l)) or less, after r each step in Shor-Khachiyan's algorithm. E1 is a ball whose radius is (E +4 bTb/4) and we know that bTb < 22L1. So the volume of E1 is at most i\ i * 22nLI. The algorithm terminates in step r, if the center x satisfies (19) and (16), that is, it is a point in E1 n K. If termination does not occur 4 2Lln -(N/2(n+l)) < upto step N = 8(n+l) (L1+1), the volume of EN is at most 2 e 2-4(n+1)2(L1il) From the fact that the volume of E1 n K > 2-4n(n1+)2(L+ ) this is a contradiction to (25). So for some r < N, we will have xr E1 n K, and in that step the algorithm terminates. The validity of the remaining portion of the algorithm follows from Theorems 7, 8, 9. Since the algorithm terminates after at most N = 8(n+) 4(Ll+l) steps, the algorithm is obviously polynomially bounded. In practice, it is impossible to run the algorithm using exact arithmetic. To run the algorithm with finite-precision (for example, if all the computa4 tionns are performed to approximation within 2-n L1) requires that the ellipsoids be expanded by a small amount in each iteration. This has been completely analyzed in LIT], and those results can be applied to this algorithm directly. Eventhough the algorithm developed here is a polynomially bounded algorithm for the nearest point problem, it is not clear that it will be efficient to solve practical problems. In particular, this algorithm is not likely to beat those discussed in [8] for practical efficiency.

22 COMPUTATIONAL COMPARISON Y. Fathi [7] did a comparative study in which this ellipsoid algorithm has been compared with two other algorithms for the nearest point problem. We provide a summary of his results here. In the table below algorithm I refers to an algorithm discussed by P. Wolfe in [27 ], algorithm II refers to an algorithm developed by Y. Fathi and K. G. Murty in [8], and algorithm III refers to the ellipsoid algorithm discussed in this section. In the study the matrix B was generated randomly, with its entries to be integers between -5 and + 5. The b-vector was also generated randomly with its entries to be integers between -20 and + 20. Instead of using computer times for the comparison, he counted the number of iterations of various types and from it estimated the total number of multiplication, division operations required before termination on each problem. Problems with n = 10, 20, 30, 40, 50 were tried and each entry in the table is an average for several problems (between 10 (for n = 50) to 50 (for smaller n) problems). Double precision was used. It was not possible to take the values of ~ and 6 as small as those recommended in the algorithm. Mostly he tried, 6 = 0.1 (the computational effort before termination iD algorithm III reported in the table below refers to E, 6 = 0.1), and with this, sometimes the complementary basic vector obtained at termination of the algorithm turned out to be infeasible (this result is called an unsuccessful run). He noticed that if the values of these tolerances were decreased, the probability of an unsuccessful run decreases; but the computational effort required before termination increases, both happening very rapidly.

23 Average Number of Multiplication, Division Operations Required Before Termination in Algorithm I Algorithm II Algorithm III (Ellipsoid Algorithm) 10 Too small Too small 33,303 20 39,096 16,266 381,060 30 123,644 42,592 1,764,092 40 514,822 170,643 5,207,180 50 896,919 324,126 11,286,717 These empirical results suggest that the ellipsoid algorithm cannot compete with other existing algorithms for the nearest point problem, in practical efficiency. The same comment seems to hold for the other ellipsoid algorithms discussed next in Sections 3, 4.

24 3. LCPs ASSOCIATED WITH PD MATRICES In this section M denotes a given PD matrix of order n (symmetric or not) with integer entries, and q denotes a given integer column vector in R". We consider the LCP (q, M), which is to find w C R n z c R satisfying I w - Mz = q w > 0, z > 0 (26) wTz = 0 In this section we let K denote the set of feasible solutions of Mz + q > 0 (27) z > 0 We let E denote the ellipsoid which is the set of all z c Rn satisfying z (Mz + q) < 0 (28) and let Bd(E) be the boundary of E, that is, it is the set of all z satisfying zT(Mz + q) = 0 (29) THEOREM 11: K, the set of feasible solutions of (27), has a nonempty interior. PROOF: Remembering that M is PD, the proof of this theorem is similar to that of Theorem 1 in Section 2. Q.E.D.

25 THEOREM 12: En K = Bd(E)n K, and this contains a single point z where (w = Mz + qz) is the unique solution of the LCP (26). PROOF: Since M is PD, the LCP (q, M) has a unique solution [20,22, 25]; and if this solution is (w, z), then z is the unique point satisfying (27) and (29). So Bd(E) n K = {z}. (27), (28) together imply (29), so En K = Bd(E)n K. Q.E.D. Define L = [(1 + log2n + Z (1 + log2(jm I j + 1)) + (1 + loq2(1qij + 1))1 i,j i E ={z: zT(Mz + q) < E} for E > 0 E = {: z z < 22L}. THEOREM 13: If (w, z) is the unique solution of (26), then (w, z) is a BFS of (26), and z is an extreme point of K. Also every extreme point z of K other than z satisfies zT(Mz + q) > 2-2L. PROOF: The fact that (i, z) is BFS of (26) is a well known result in linear complimentarity. [5, 16, 21]. This implies that z is an extreme point of K. By the results in [9, 11 ] at every BFS (w, z) of (26), for each i, eithe i and similarleither wz is 0 or > 2or > or > 2-L This implies that at any extreme point z of K, for each i either z. is 0 or' L) 1 > 2L and similarly either-. z + qi is 0 or > 21. Since (VI, z) is the unique solution of the LCP'(26), at every extreme point z of K other than z, T n we must have zT(Mz + q) = E z(M. z + qj) > O, so we must have at least i=l 1 ti one i vhere both z. > 0 and M. z + q. > 0. Combining these results we conclude that every extreme~ point z of K other than z satisfies zT(lz + q) > 2. Q.E..

26 THEOREM 14: For E positive and < 2 2L, the n-dimensional volume of EO0 E n K is > n 2-(3n+1)L PROOF: Obviously z c E f K, and by Theorem 13, no other extreme point ~ -2L z of K lies in E n K for 0 < s < 2.So for every value of c in the specified range, every edge of K through z intersects E. Also, since K has a nonempty interior by Theorem 11, E (1 K has a positive ndimensional volume. K might be unbounded, but by the results in [ 9,11], at every extreme point of K, both z. and M.z + q. are < 2L/n for each i. To the constraints in (27), augment the additional bound constraints that both zi and Mjz + qi are < 2L/n for each i, and let K denote the set of feasible solution of (27) together with these bound constraints. By the above facts, every edge of K through z is either an edge of K (if it is a bounded edge of K), or a portion of an edge of K (if it is an unbounded edge of K). Let zi,...,z" be adjacent extreme points of - 1 n 2 in K such that {z, z,...,z } is affinely independent. The above facts imply that all these points z, z', t = 1 to n are in Eg. Define f(z) = zT(Mz + q). Since M is PD, f(z) is convex. Let X = E 2-2L So for each t = 1 to n f(z + X(zt - z)) < (l-X) f (z) + Xf(zt) X f(zt) n t = X Ez z (M z + q) i=l 1 i n ( L 2L X< E ( x - -i=l \ n =< c.

27 This implies that the line segment [z, z + X(zt - z)] completely lies inside E0 n E n K. So the volume of E0 n E n K is > the volume of the simplex whose vertices are z, z + X (zt z), t = 1 to n. = 1 determinant of (X(z1 - z).. X(z - z))| n! w > xn 2-(n+l)L by the results in [9] > n 2-(3n+l)L Q.E.D. THEOREM 15: Let 3 = 2-(6L+l) For any point z E E n E n K, we 0 have either z. < i <O < 2-3L or M;. z + q < o < 21 ~vO PROOF: For any i, if both z. and M. z + qi are > F then z(M z + q) > ~0, contradiction to the fact that z c E0 E n K. Q.E.D. THEOREM 16: Let z be any point in E0 n E n K. Define u E0 y = w if z. < 2-3L = z. if z. > 2-3L Then (yl,...,yn) is a complementary feasible basis for (26), and the BFS of (26) corresponding to the basic vector (Yl,...,yn) is (w, z), the solution of the LCP (q, M).

28 PROOF: Let J1 = {i: z. > 2-3L and J2 = {i:. < 23L So ~' {i~: ad =....z + < 2 }.So-3L J1 J 2 = 2 and J1U J2 {1, 2,...,n}. By Theorem 15, M. z + q. < 2for each i c J1. In [9] P. Ggcs and L. Lovasz proved the following lemma: Consider the system of constraints A. x < b., i = 1 to m (30) A~: i1 with integer data, and let Z be the size of this system. Suppose x is a solution of A. x b. + 2 i = 1 to m x~ < b1 such that A. x > b., i = 1 to k, and let r < k be such that {A1,...,A } I* 1 le -= span {A1,...,Am } linearly. Let x be any solution of the system of eauations Ai. x = b., i = 1 to r. Then x is a solution of (30). We will use this lemma in proving this theorem. Consider the system l. te C,' c- --- a 1' U h,R - Mz < q + 2-3Le (31) z < O + 2-3L e M. z < -q+ 2, for i c J1 z. < 0 + 2-, for i E J. I: 2'

29 A A We know that z solves (31) and in addition z also satisfies Mi.z > -qi for i c J1 z. > 0 for i ~ J2 Also, since M is PD, the set {Mi.: i e J1} U{Ij.: i E J2} linearly spans all the row vectors in the system (31). By using the theorem of P. Gdcs and L. Lovasz mentioned above on this system, we conclude that if z is a solution of the system of equations, Mijz = -qi for i 3 J1 (32) z= 0 for i c J2 then z would be a solution of - Mz < q -z < 0 (33) M. z = -q. for i ~ J1 z. 0 for i c J2 1 From (33) we know that Mz + q > 0, z > 0 and since z.= 0 for all i E J2 1 and M.Oz + q0 = 0 for all i c J1 we conclude that z (Mz + q) = 0 (since J1 n J2 = and J1 U J2 = {1,...,n}). So z is a solution of the LCP (q, M). From (32) we notice that (w = Mz + q, 2) is the solution of the system of remaining equality constraints in (26) after setting w. = 0 for i E J1 and z. = 0 for i ~ J2' that is, it is the basic solution of (26) corresponding to the complementary basic vector y = (y..'Yn) defined in the theorem. So y is a complementary feasible basic vector for (26) and the BFS of (26) corresponding to it is the unique solution of the LCP (q, M). Q.E.D.

30 THE ALGORITHM Fix = = 2(6Ll) For any point z E R" and a PD symmetric matrix A, let E(z,A) denote the ellipsoid {z: (z - z)TA- (z - z) < 1} So E0 = E(O, 22LI). In this section define N = 2(n+l)2(11L+l). With o 2L 0 ~ = 2 IE(z, A) A go to Step 1. GENERAL STEP r+l Let zr, Ar, E = E(z, A ); be respectively the center, PD symmetric matrix, and the ellipsoid at the beginning of this step. If zr is feasible to (34), (35) - z -q < 0 (34) -Z < 0 z (Mz + q) < c (35) terminate the ellipsoid algorithm, call z' as z and go to the final step described below. If z' violates at least one of the constraints in (34), (35) select an inequality constraint az < d (36) violated by zr by the following: If zr violates (34), take (36) to be the constraint in (34) that zr violates most. Break ties arbitrarily. If zr satisfies (34) but violates (35), choose (36) to be the half-space not containing zr, determined by the tangent plane of E at its boundary point r, where 9r is the point of intersection of the line segment joining the center of E and zr with the boundary of E o co

31 The center of E is z' = ( M + )1, and r = Xz' + (l-)zr where 2O ) 2 X is the positive root of the quadratic equation (Xz' + (1lX)Zr)T(M(Xz' + (1-X)zr) + q) = 0. Now define yr, Ar+l as in (24) and Zr+l Z r ( rn) ( T )(37) aAraT With zrl, Ar+, Er+l = E(z+, Ar+ ) move to the next step in the ellipsoid algorithm. After at most N steps, this ellipsoid algorithm will terminate with the point zr in the terminal step lying in E n E 0 K. Then go to the final step described below. FINAL STEP Let the center of the ellipsoid in the terminal step be z. Using z, find the complementary BFS of (26) as outlined in Theorem 16. PROOF OF THE ALGORITHM The updating formulas used in this ellipsoid algorithm are the same as those used in the algorithm of Section 2. Hence using the same arguments as in Section 2, we can verify that Er EOn EO n K for all r. 2Ln0 The volume of E0 is < 22L After each step in the ellipsoid algorithm. the volume of the current ellipsoid Er gets multiplied by a factor of e-(1/2(n+l) or less. So if the ellipsoid algorithm does not terminate (e(n+l) ( ) (L+ )<Ln) 2 9n+1)-n even after N steps, the volume of EN (e- l(llL+l))( Ln) < 2-L(9n+l)-n contradiction to the fact that EN D E0 n E f n K and Theorem 14. So for some r < N, we will have zr C E0 n E n K, and in that step the ellipsoid algorithm terminates. Hence the algorithm is obviously polynomially bounded.

32 Comments made in Section 2 about the precision of computation required, remain valid here also. 4. LCPs ASSOCIATED WITH PSD MATRICES In this section we consider the LCP (26) where M denotes a given PSD matrix of order n (symmetric or not) with integer entries, and q denotes a given integer column vector in Rn. Let K denote the set of feasible solutions of (27). Since M is only PSD here, K may have an empty interior, and in fact K may even be empty. Let E be defined by (28) and let Bd(E) be defined by (29) as in Section 3. Also let L, E, be as defined in Section 3. Here E, E may not be ellipsoids because M is only PSO. We let e = (1,...,1) denote the column vector in Rn all of whose entries are 1. THEOREM 17: In this case the LCP (26) has a solution iff K i f. If K J p, there exists a solution, (w, z), to the LCP (26), which is a BFS of (26), and in this case z is an extreme point of K. When K f 4, the LCP (26) may have many solutions, but the set of all solutions of (26) is a convex set which is E N K = Bd(E) K. PROOF: Since M is PSD, the fact that (26) has a solution iff K $ s is a standard result in linear complementarity [5, 16, 21]. When K t q, Lemke's complementary pivot algorithm produces a solution, (w, z), to (26), which is a BFS of (26) [5, 16, 21], and obviously if (w, z) is a BFS of (26), z is an extreme point of K. The set of all solutions of (26) is obviously Bd(E) n K, and from the definition of K (from (27)) and E(from (28)) it is clear that in this case Bd(E)N K = E n K, and since both E and K are convex sets (E is convex because M is PSD), this set is convex. Q.E.D.

33 In this section we define E0 to be E0 = {z: Z z < 22( (38) THEOREM 18: When K $ q, E0 n E.nK contains all the extreme points z of K such that (w = Mz + q, z) is a solution of (26). PROOF: By the results in [9, 11] if (w, z) is a solution of (26) which is a BFS, then z c E0O. The rest follows from Theorem 17. Q.E.D. In this case E0 n EC n K may not contain all the z which lead to solutions of (26), Theorem 18 only guarantees that Eon EE n K contains all the z which are extreme points of K that lead to solutions of (26). Since M is PSD, the LCP (q, M) may have solutions which are ray solutions, and if so, the set of solutions of (26) may in fact be unbounded and hence all of it may not lie in E0. THEOREM 19: If z. is positive in some solution of (26), then its complement wi is zero in all solutions of (26). Similarly if wi is positive in some solutions of (26), then z. is zero in all solutions of (26). 1 PROOF: By Theorem 17, the set of all solutions of (26) is a convex set. 1 1 7 2 So if (w, z ), (w, z ) are two solutions of (26) satisfying the proper1 2 ties that z. > 0 and w. > 0, then other points on the line segment joining 1 1 (w, z ), (w, z ) cannot be solutions of (26) (because they violate the complementarity constraint w.z. = 0 in (26)) contradicting the fact that the set of solutions of (26) is a convex set. Q.E.D. THEOREM 20: If z is an extreme point of K that leads to a solution of (26), then for each i either z. = 0 or 2-L < z < 2L/n. Also either M.z + q. is zero or 2' < M. 2L/n. Also at every extreme point of z of K that does not lead to a solution of (26), we will have zT(Mz + q) > 2-2L

34 PROOF: Similar to the proof of Theorem 13 in Section 3. Q.E.D. THEOREM 21: K $ q iff the set of solutions of Mz + q > -2- e (39) z > -2-1 e has a nonempty interior. PROOF: By the results in [9], (39) is feasible if and only if K f t. Also any point in K is an interior point of the set of feasible solutions of (39). Q.E.D. Let K1 denote the set of feasible solutions of (39). THEOREM 22: Let E0 = 2-(6L+1) For any point z E EOc E E K1, we have for each i = 1 to n, either z. < 23L 3L 3L or M,.z + q < 2-31 PROOF: Suppose that z > 2- and M.z + q > 2-3L Since z ~ E and M1. i = 0 zT(Mz + q) < 2(6L+). Then we have n Z zt(Mt. z+ qt) < 2-(L+) -2-61 $1 ~~< -2-(6L+1) E zt (Mt + qt) > - (n-l) 2-10L (22L+ + 2L) t=l 2-(6L+1) a contradiction. Q.E.D.

35 THEOREM 23: Let 0 = 2-(6L+1) If K + ), the n-dimensional volume of Eon E n K1 is > 2-11nL PROOF: Assume K $ ). So by earlier results (26) has a solution. Let (w, z) be a complementary BFS of (26). So by Theorem 17, z s Bd(E) n K. Define the hypercube C (for X > 0) C = {z: z E Rn, z - zl < X/2 for all j = 1 to n}. Then, clearly, the n-dimensional volume of C, is Xn. We will now prove that C C K1 n E0 nE for X < 211L. Since the radius of E0 is 2L+1 CxC E0 by the definition Cx and the fact that |Ijzl < 2 from Theorem 20. Let z be any point in Cx. Since z. > O, M. z + q. > 0 for all i = 1 to n, we have z. > z. - X/2 > -X/2 >2-10L n..z + qi > M. + qi - (X/2)( E |mIjl) 1:'1 j=l ij >2-(11L+l) x 2L > - 2-10L So CXC K1. Also, since z'(Mz + q) = 0 (since (w = Mz + q, z) solves (26)), we have zT(Mz+q) = (;z-)T (Mz+q+MT ) + (z-z)TM(z-z) < (X/2) n(2L+2L 2L) + (X/2)2 Z ImJ <=~ 211l n2L 22i,j j < 2-(11L+l) n 22L+2 + n2 2L-2(11L+1) <= 0

36 This implies that C c E. Hence C K1 n E0 n E. Now letting 1110 1 1 nL K A = 2-, the volume of Cr is 2-1, and these facts imply the theorem. Q.E.D. Let z be any point in E 0 E n K1. Define = {i: M. z + q < 0} J1 i = = {i: 0 < Mi. z + q < 2-3L} J= {i:. <0 2 {i: 0 < z. < 23L} Then by Theorem 22, + + J12 UJ2UJ = {,...,n}. (40) Furthermore, z is a solution of - Mz < q + 2-3Le - z < 2-3Le (41) M. z < - q + 2-3L for i c J z 2-3L for i e J 1 - 2

37 THEOREM 24: Let z be any point in EO0 E E n K1. Let I be the unit matrix of order n. In [9] P. G[cs and L. Lovfsz describe a constructive procedure for obtaining a new solution, which we will denote by the same symbol z, such that if J1, 1 J2 are the index sets corresponding to this new z, then the new z also satisfies (41), and there exists a linearly independent subset D of row vectors. Dc {M: i E U J 1 U {J i E U { such that D spans linearly {Mi.: i = 1 to n}U {I.: i = 1 to n}. Furthermore, if z is a solution of -M. z = qi for i such that Mi. E D z. = 0 for i such that I. c D then (w - Mz + q, z) is a solution of (26). PROOF: This theorem follows from the results of P. Gbcs and L. Lovgsz in [9], applied on (41). We know that 2 satisfies - M. z > q2, for i J M. z >-q., for i c J 1- =i1 1 -. > 0, for i c J2 Z^> 0, for i F+J zi > 0, for i c J2' By the results in [9], z is a solution of - Mz < q -z < 0

38 Furthermore, z satisfies Mi. = -q., for i J1 U J1 z. = 0, for i c J2 UJ2 1 2 2 by the spanning property of D and the results in [9]. By (40), this implies that at least one of w. or z. is zero for each i = 1 to n. All these facts together clearly imply that (w, z) is a solution of the LCP (26). Q.E.D. THE ALGORITHM Apply the ellipsoid algorithm discussed in Section 3, to get a point z iEn E0 E a0\ K1, initiating the algorithm with z = 0, A0 = 2( )I, E = E(z, Aj). The volume of E0 here is < 22n(L+l) and if K, the volume of E0 n E f K1 is > 2-llnL by Theorem 23. Hence if K + p, 0 2 this ellipsoid algorithm will terminate in at most 2(n+1) (13L+1) steps with a point z c E0n E n K1. So, if the ellipsoid algorithm did not 0 <2 find a point in En0 E n K1 even after 2(n+l) (13L+l), we can conclude that K = X, that is, that the LCP (26) has no solution. On the other hand, if a point z in E0 n E K1 is obtained in the ellipsoid algorithm, 0 then using it, obtain a solution (w, z) of the LCP (26) as discussed in Theorem 24.

39 5. OTHER LCPs The ellipsoid algorithms discussed in Sections 2, 3, 4 can only process LCPs associated with PSD matrices (the class of these LCPs is equivalent to the class of convex quadratic programs). There are other polynomially bounded algorithms for other special classes of LCPs. One prime example of this is the very efficient O(n3) algorithm of R. Chandrasekharan and R. Saigal [2, 24] for processing LCPs associated with z-matrices. Also in [6, 19] it was shown that LCPs satisfying certain properties can be solved as linear programs, and these LCPs are therefore polynomially solvable using Shor-Khachiyan's ellipsoid algorithm [9, 11] on the resulting linear program. For the general LCP, the prospects of finding a polynomially bounded algorithm are not very promising, in view of the result in [3] where it is shown that this problem is NP-complete. Let al,...,an, b be positive integers and let Mn2 and q(n+2) be the following matrices I- 0 0 a Mn+2..'' q(n+2) = n+2: - e -n a n T =1 en 0 -nor 1 for all i =1 to n. b where I denotes the unit matrix of order n, and en is the column vector in Rn all of whose entries are 1. Also consider the 0-1 equality constraint Knapsack feasibility problem 7 a.x. = b (42) xi = 0 or 1 for all i = 1 to n.

40 In [3], the following result was proved: If (w, z) is a solution of the LCP (q(n+2), Mn+2); define x. = zi/ai for i = 1 to n; then x = (xl,... n)T is a solution of (42). Conversely if x = (x,...,x)T is a solution of (42); define Wn+l = +1 = n+2 d z. a x. w= a.( - i = 1 to n; then (w = (Wl" w n+2)' 2 =(z1,...n+2 )) is a solution of the LCP (q(n+2), Mn+2 ). Since (42) is a well known NP-complete problem, this shows that the LCP (qn+2' Rn+2) is NP-complete. One can clearly verify that the matrix Mn+2 is ND. This shows that even the LCPs associated with ND matrices are NP-complete. Let M be a given ND matrix with integer entries, and let q ~ R" be a given integer column vector. In this case the LCP (q, M) may not have a solution; and even if it does, the solution may not be unique. From the results in [20] we do know that the number of distinct solutions of the LCP (q, M) in this case is finite. Let K be the set of feasible solutions of z > 0 (43) Mz + q > 0 and let E be the ellipsoid T zT(Mz + q) > 0. (44) Since M is ND, the inequality (44) defines an ellipsoid in Rn. Let Bd(E) be the boundary of E. Clearly any point z c Bd(E) n K satisfies the property that (w = Mz + q, z) is a solution of the LCP (q, M) and vice versa. So solving the LCP (q, M) is equivalent to the problem of finding a point

41 Figure 4: When M is ND, E and K may be as in one of the figures given here. Points of K on the boundary of E, if any, lead to solutions of the LCP(q, M).

4? in Bd(E) n K. However, in this case, from (43), (44) we notice that K c E, and in general, Bd(E) n K C E n K. See Figure 4. So the nice property that E K = Bd(E) n K which held for LCPs associated with PSD matrices does not hold here anymore, which makes the LCP associated with an ND matrix much harder. In this case (i.e., with M being ND), it is possible to find a point in E nK using an ellipsoid algorithm (actually since KC E here, a point in K can be found by the ShorKhachiyan algorithm of [9, lJ], and that point will also lie in E), but the point in E n K obtained by the algorithm may not be on the boundary of E, and hence may not lead to a solution of the LCP (q, M). In fact, finding a point in Bd(E)N K is a concave minimization problem, and that's why it is NP-complete. The status of the LCPs (q, M) where M is a P but not a PSD matrix, is unresolved. In this case the LCP(q, M) is known to have a unique solution [20, 25], but the sets {z: z'(Mz + q) < 0} or {z: zT(Mz + q) > 0} are not ellipsoids. The interesting question is whether a polynomially hounded algorithm exists for solving this special class of LCPs. This still remains an open question. It is also not known whether these LCPs are NP-complete.

43 REFERENCES 1. I. Adler, R. P. McClean and J. S. Provan, "An Application of the Khachiyan-Shor Algorithm to a Class of Linear Complementarity Problems", Cowles Foundation discussion paper No. 549, Cowles Foundation for research in Economics, Yale University, Box 2125, Yale Station, New Haven, Connecticut 06520. 2. R. Chandrasekharan, "A Special Class of the Complementary Pivot Problem", OPSEARCH, 7, pp. 263-268, 1970. 3. S. J. Chung, "The Linear Complementarity Problem is NP-Complete", to appear in Mathematical Programming. 4. S. J. Chung and K. G. Murty, "A Polynomially Bounded Algorithm for Positive Definite Symmetric LCPs", Technical Report 79-10, Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, Michigan 48109, December 1979. 5. R. W. Cottle and G. B. Dantzig, "Complementary Pivot Theory of Mathematical Programming", Linear Algebra and its Applications, 1, pp. 103-125, 1968. 6. R. W. Cottle and J. S. Pang, "On Solving Linear Complementarity Problems as Linear Programs", pp. 88-107 in Mathematical Programming Study 7, 1978. 7. Y. Fathi, "Comparative Study of the Ellipsoid Algorithm and Other Algorithms for the Nearest Point Problem", Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, Michigan 48109, USA, June 1980. 8. Y. Fathi and 1<. G. Murty, "The Nearest Point Problem", Technical Report No. 79-7, Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, Michigan 48109, U.S.A., 1979. 9. P. Gacs and L. Lovasz, "Khachiyan's Algorithm for Linear Programming", Computer Science Department, Stanford University, August 1979. 10. D. Goldfard and M. J. Todd, "Modificiation and Implementation of the Shor-Khachiyan Algorithm for Linear Programming", Technical Report No. 446, School of Operations Research and Industrial Engineering, College of Engineering, Cornell University, Ithaca, New York, January 1980. 11. L. G. Hacijan, "A Polynomial Algorithm in Linear Programming", Soviet Math. Dokl., No. 1, 20, pp. 191-194, 1979.

44 12. PC. Jones and E. S. Marwil, "Solving Linear Complementarity Problems with Khachiyan's Algorithm", E. G. & G. Idaho, Inc., P. 0. B. 1625, Idaho Falls, Idaho 83415, January 1980. 13. I. Kaneko, "Piecewise Linear Elastic-Plastic Analysis", International Journal for Numerical Methods in Engineering, 14, 5, pp. 757-767, 1979. 14. M. K. Kozlov, S. P. Tarasov and L. G. Hachijan, "Polynomial Solvability of Convex Quadratic Programming", Soviet Mathematics Doklady, 20, 1979, No. 5. 15. K. K. Kubota, Private Communication. 16. C. E. Lemke, "Bimatrix Equilibrium Points and Mathematical Programming", Management Science, 11, pp. 681-689, 1965. 17. CE. Lemke, and J. T. Howson, "Equilibrium Points of Bimatrix Games", SIAM Journal of Applied Mathematics, 12, pp. 413-423, 1964. 18. 0. L. Mangasarian, Nonlinear Programming, McGraw-Hill, 1969. 19. 0. L. Mangasarian, "Simplified Characterizations of Linear Complementarity Problems Solvable as Linear Programs", Mathematics of Operations Research, 4, pp. 268-273, 1979. 20. K. G. Murty, "On the Number of Solutions of the Complementarity Problem and Spanning Properties of Complementary Cones", Linear Algebra and its Applications, 5, pp. 65-108, 1972. 21. K. G. Murty, Chapter 16 in Linear and Combinatorial Progrcmming, Wiley, 1976 22. K. G. Murty, "On the Linear Complementarity Problem", pp. 425-439 in Band 31, "Continuous Optimization" of Proceedings of the Third Symposium on Operations Research, Universitat Mannheim, Sept. 6-8, 1978, Edited by W. Oettli and F. Steffens, published by Verlagrgruppe, Athenaum/Hain/Scriptor/Hanstein. 23. J. S. Pang, I. Kaneko and W. P. Hallman, "On the Solution of Some (Parametric) Linear Complementarity Problems with Applications to Portfolio Selection, Structural Engineering and Acturial Graduation", Mathematical Programming, 16, 3, pp. 325-347, May 1979. 24. R. Saigal, "A Note on a Special Linear Complementarity Problem", OPRESEARCH, 7, 3, pp. 175-183, September 1970. 25. H. Samuelson, R. M. Thrall and 0. Wesler, "A Partition Theorem for Euclidean n-space", Proceedings of American Mathematical Society, 9, pp. 805-807, 1958.

45 26. N. Z. Shor, "Convergence Rate of the Gradient Descent Method with Dilation of the Space"', Kibernetika 6 (No. 2, March-April 1970), translated in Cybernetics, 6, pp. 102-108, 1970. 27. P. Wolfe, "Finding the Nearest Point in a Polytope", IBM Thomas J. Watson Research Center, Yorktown Heights, New York 10598. Revised, January 1976.

SECURITY CLASSIFICATION OF THIS PAGE (When Deta Entered) REPORT DOCUMENTATION PAGE BEFORE COMPLESTRUCTING FORM BEFORE COMPLETING FORM 79-10 \. REPORT NUMBE: {2. GOVT ACCESSION NO. 3. RECIPIENT'S CATALOG NUMBER 4. TITLE (and Subtitle) 5. TYPE OF REPORT & PERIOD COVERED "Polynomially Rounded Ellipsoid Algorithms for T PRFRMNG OReearEch rTepNrt. 6. PERFORMING ORG. REPORT NUMBER Convex Quadratic Programming.". 79-10 7. AUTHOR(s) 8. CONTRACT OR GRANT NUMBER(s) S. J. Chung and K. G. Murty Grant AFOSR 78-3646 9. PERFORMING ORGANIZATION NAME AND ADDRESS 10. PROGRAM ELEMENT, PROJECT, TASK AREA & WORK UNIT NUMBERS University of Michigan Ann Arbor, Michigan 48109, U.S.A. 11. CONTROLLING OFFICE NAME AND ADDRESStJashington, D.C. 2033 2. REPORT DATE Directorate of Mathematical & Information Sciences June, 1980 Department of the Air Force, Air Force Office of 13. NUMBER OF PAGES —- - Scientific Research (AFSC), Bolling Air Force Base 47 14. MONITORING AGENCY NAME & ADDRESS(if different from Controlling Office) 15. SECURITY CLASS. (of this report) 15a. DECLASSIFICATION/DOWNGRADING SCHEDULE 16. DIST IBUTION STATEMENT (of this Report) Unlimited. 17. DISTRIBUTION STATEMENT (of the abstract entered in Block 20, if different from Report) Unlimited. 18. SUPPLEMENTARY NOTES 19. KEY WORDS (Continue on reverse side if necessary and identify by block number) Convex quadratic programming, linear complementarity problem, nearest point problem, positive semi-definite matrix, ellipsoid algorithm, polynomially bounded algorithm. 20. ABSTRACT (Continue on reverse side if necessary and identify by block number) le show that the ellipsoid algorithm of N. F. Shor and L. G. Khachiyan, can be applied to solve convex quadratic programming problems with integer data in polynomially bounded time. DD,A73 1473 SECURITY CLASSIFICATION OF THIS PAGE (Ifhe.I Data Entered)

SECURITY CLASSIFICATION OF THIS PAGE(Whon Data Entered) UNIVERSITY OF MICHIGAN 390 5 04732 7203 SECURITY CLASSIFICATION OF THIS PAGE(When Data Entered)