Computational Complexity of Van der Heyden's Variable Dimension Algorithm and Dantzig-Cottle's Principal Pivoting Method for Solving LCP's Technical Report No. 82-2 by John R. Birge and Akli Gana Department of Industrial and Operations Engineering The University of Michigan Ann Arbor,. Michigan 48109 March 1982

Computational Complexity of Van der Heyden's Variable Dimension Algorithm and Dant.zig-Cottle's Principal Pivoting Method for Solving LCP's John R. Birge Akli Gana Department of Industrial and Department of Industrial and Operations Engineering Operations Engineering The University of Michigan and The University of Michigan Ann Arbor, Michigan 48109 Ann Arbor, Michigan 48109 ABSTRACT We show that Van der Heyden's variable dimension algorithm and Dantzig and Cottle's principal pivoting method require 2 -1 pivot steps to solve a class of linear complementarity problems of order n. Murty and Fathi have previously shown that the computational effort required to solve a linear complementarity problem of order n by Lemke's complementary pivot algorithm or by Murty's Bard-type algorithm is not bounded above by a polynomial in n. Our study shows that the variable dimension algorithm and the principal pivoting method have similar worst case computational requirements. KEYWORDS: Linear complementarity problem, computational complexity. ABBREVIATED TITLE: Computational Complexity of VDA and PPM.

1. Introduction The linear complementarity problem (LCP) of order n, LCP(q, M), is to find w C R and z ~ R such that w - Mz = q, (1) w z= 0, (2) w > 0, (3) z > 0, (4) where M is a square matrix of order n, and q is a vector in R. Murty [7] and Fathi [3] have shown that Lemke's complementary pivot method [5] and Murty's Bard-type method [5] require a number of pivot steps that is not bounded above by a polynomial in n for a certain class of LCPs. Geometrically, Murty showed that the algorithms follow a path across all 2 complementary cones in R, In this paper, we consider Van der Heyden's variable dimension algorithm (VDA) [8] and Dantzig and Cottle's principal pivoting method (PPM) [3]. We construct a class of matrices similar to Murty's and show that VDA and PPM require 2 -1 pivot steps for these problems. The nth order problem in this class will be denoted LCP(q(n), M(n)) where the elements of M(n) are mi. such that 1 if i = j. = 2 if j > i (5) m0 otherwise, and q(n) = (ql' q72'"'' qn) where n q. = Z -2j. (6) j=i

2 We note that M(n) is the transpose of the matrix used by Murty in [7]. 2. A Geometrical Interpretation of the VDA. A matrix M is called a Q-matrix if LCP(q, M) has a solution for all q c R. M is a completely Q or Q-matrix if M is a Q-matrix and so are all of its proper principal submatrices. We will consider the VDA algorithm applied to this latter class of matrices. Some properties of completely Q-matrices can be found in Cottle [2]. Under nondegeneracy, Van der Heyden [8] showed that VDA solves a sequence of subproblems that is guaranteed to terminate with a solution to the original problem LCP(q, M). The algorithm follows. VDA. Step 0: Initialize (w, z) = (q, 0). Step 1: If w > 0 the current basic complementary solution is feasible. Stop. Otherwise set k equal to the index of the first negative component of w, increase zk and go to Step 2. Step 2: Keep on increasing or decreasing the variable specified by the previous step, until one of the basic variables in the subproblem of order k becomes nonbasic. Denote this variable by sj(s. = wj or z., j < k) then perform one ]j i J =j of the following operations: (a) If j < k, increase the complement of sj; go to Step 2. (b) If j = k and sk = wk, we have solved the subproblem of order k; go to Step 1. (c) If j = k and sk = zk, we have found another solution of a subproblem of size smaller than k; go to Step 3.

3 Step 3: Set k equal to the index of the last positive component of z, decrease wk and go to Step 2. Remarks. 1. k is the subproblem size. The algorithm considers only subproblems of order k obtained by disregarding the last (n-k) rows and (n-k) columns of the matrix M and the last (n-k) components of q. 2. Note that when M has positive principal minors, (a P-matrix), Step 2c and Step 3 will never be performed because each subproblem has a unique solution. For this subproblem, VDA then follows the same steps as PPM. 3. When solving a subproblem of order k where M is a P-matrix, wk and Zk will both be basic variables until the last step, when wk leaves the basis. (This is a consequence of Remark 2.) 4. When solving a subproblem of order k, (k > 2) the algorithm maintains complementarity and nonnegativity of (w1, w2,...,wk ) and(z1, Z2,.., zk-l). We now give a geometric interpretation of the VDA when applied to solve an LCP(q, M) where M is a P-matrix, q. > 0 for i = 1,..., n-l, and q < O. (Notice that any subproblem has this general form.) By Remark 4, the VDA maintains feasibility of the problem of order (n-l) when attempting to solve the order n problem. Also, z will enter the basis at the first step and will never become nonbasic, and wn will be basic in all tableaus encountered except the last. Hence, the only pivot step in row n that the

4 algorithm performs is the last one. Let us consider the parametric LCP of order (n-l) obtained from the given LCP(q, M), by disregarding row n and the column corresponding to wn, by transferring the column corresponding to Zn to the right hand side, and by treating z as a parameter. Let q = (ql, q2',',q 1) and M'. be the ith column of M whose last component 19 29~- n-1 ) * M' n-l is disregarded, then the point q'+ z,M traces a line in R as z takes n.. n on all values. We observe that, before'.the last pivot to solve the problem, the number of intermediate pivot steps required by the algorithm is bounded above by the number of complementary cones of order (n-l) that the half line L' = {x: x = q + z M; z > } intersects. n.n n = Thus, finding the worst case behavior of this algorithm is equivalent to finding the maximum number of complementary cones of order (n-l) that the half line LA cuts across. Claim: Each intermediate step of the VDA corresponds to a move from one facet of a complementary cone of order (n-l) to another along the half line LA. To see this, suppose at some stage of the algorithm (Y1, Y2,."'..Yj. Yj+l,-..'*nl, Z, wn) is the present basic vector; where yi e {Wi, Zi} for i = l,...,n-l, z = z, and w < 0. Since the algorithm does not perform n n a pivot on row n during the intermediate steps, we look only at the vector (Y1' Y2*'', Yn-l' Yj+l,'"'' Yn-l' Zn) The entering variable at this stage is y.. By increasing the value of yj, the algorithm travels through the interior of the complementary cone, J mentj set of vec s cding to te cple y v r mentary set of vectors corresponding to the complementary vector of

5 variables (y', yY29'. Y j- y, jy Yj+'',..,y n). The value of yj is increased until the half line intersects another facet of the same complementary cone, where the value of the dropping variable, y., becomes zero. The value of z becomes z. Therefore, the intermediate pivot steps can n n be interpreted as a walk along the half line L' across different complementary cones of the form, Pos(A1l, A'..., A", A..., A.). This *. 2Z *J Is J'TjL'.n-l sequence of intermediate complementary cones is identical to the sequence of solutions for the parametric LCP above where the initial value of z is zero and where M is a P-matrix. We can notice also that the VDA can be interpreted for a P-iiatrix as a walk in n-dimensions along the half line L = {x: x = q + z M, z > 0}. Across different complementary cones of n.n n = the form, Pos{A1' A.2,..A' A } where A e {l, - M ] i = 1,..., n-l,. 2. in- l'.i and A =- I. A is always equal to - I until the last step when.n.n.n n w leaves the basis. n

6 3. Computational complexity of the VDA. Let us consider the LCP(q, M) of order n in the following canonical tableau form after the (n-l) order subproblem has been solved. w w w z z..... z w z q 2n + 8 0 ~ -n-1 x ~- - Mn-l) (n) 0 2 0 2 2n + 2n-1 0 0 1 0 0 -1 - 2n Here, the basic vector is (w1, w2,..., Wn, Z1, wn ) 1n~" x n-l 2 O- n- If we apply the variable dimension algorithm to the above LCP, the VDA maintains feasibility of the (n-l) order subproblem (Remark 4) and the values of w and z are determined by the sequence of solutions of the subproblem n n followed by the algorithm.

7 We will show that this sequence of complementary bases include all of the (n-1) order complementary bases. Our procedure will be to prove that z and w are strictly increasing and that the size of the increases is n n bounded, forcing the algorithm to follow a maximum number of steps. We first need the following lemma in showing monotonicity. Lemma 1: Let A = (aij) be a 2-square matrix having the properties: (i) all < 0 (ii) a21 < 0 - a /al 1/al (iii) The matrix A1 = L (all a22 - a12 a21)/all a21/all (iv) has positive principal minors, a 11/a21 (a12 a21 - a22)a21 A2 = 1[ /a21 - 22/a21 has positive principal minors, then A must have the properties: (v) a12 > 0, (vi) a22 > 0. Proof: From Cottle [1]. Let the matrix of the LCP in (7) be M. It is a P-matrix. Thus, by Remark 2, when the VDA is applied to this problem, z will enter the basis n at the first step and it will never leave. Also, the schema is almost complementary during the entire solution process, and w and z will be n n

8 basic variables until the last step when wn leaves the basis and a solution is obtained. The following lemma establishes that z and w strictly n n increase during the application of VDA to (7). Lemma 2: Under nondegeneracy z and w in (7) will strictly increase during the application of the VDA. Proof: The VDA first increases z. Without loss of generality, we can assume that the current basic variables at any step of the algorithm are (w1, w2,..., w w) and the nonbasic variables are (zl, Z2..s s z, z ). If z is blocked by w then we have two cases: n s (a) If s = n, then the result is trival. (b) If s + n, then m < 0, and we exchange w and z. Before the sn s n pivot step we have the following 2 x 2 matrix corresponding Z z to the variables, z and z. s n. This $s n --. f m m \ ss sn m m ~ ns nn is a P-matrix since M is P. After the pivot step, the matrix corresponding to w and z (which becomes the new driving variable) is 1 m _ —- " SS m m sn sn (9) nn (m m m m )/ m ns sn ss nn sn sn

9 Now, since, m > 0, m < 0, and M is P, then Lemma 1 applies to (9), and nn sn we obtain - m m m -m m ss > and ns sn ss nn >0. (10) m m sn sn After the pivot step, w and z are the basic pair in the almost complen n mentary schema. (10) implies that both members of the basic pair will increase with increases in the new entering variable. We will show that the driving variables continue to have positive coefficients in the sth and nth rows of M until w is chosen as a blocking - — ~ -n variable. We assume that this is true after k pivot steps. We showed above that this assumption was true for k = 1. Let z be the driving variable in the next step and let w +$ w be the blocking variable. The matrix corresponding to w., z ( = w ), w, z. and z is: 3 n s n j n w z (w ) w z z ___ n s n n 1 0 0 -m - m 0 0 -in. M' (n O 1 0 - mjj m (11) 53 ~sn 0 0 1 - m. -m - nj nn Since w. is blocking, mj < 0, and m > 0 and m > 0 by assumption. 3 jn sn nn After pivoting, we obtain the matrix corresponding to wj and zj (the new driving variable) as

10 W. Zj 1 m _ _ijn jn m m. - m m.. sn Jn s sn JJ m. m. in jn m m. m - m m nn jn nj nn (12) m. Jn mi in Again, we continue to apply Lemma 1 and z and w increase as z. increases, n n J proving the result. U We can also notice that z and w will increase by the same amount n nn during the process of solving problem (7) since w = z - 2. The n n first increase is 2 +1 since z is blocked by wl. In the following, we show that the increase of z and w, after the first pivot step is at most one. To do, so, we proceed as Murty did in [7] by showing that the line q + M z crosses all complementary cones in the (n-l) order principal *n n subproblem. We treat z as a parameter in the (n-l) order principal subproblem n obtained from (7) by disregarding the last row and the column corresponding to w, We then transfer the last column to the right hand side and obtain the following parametric LP of order (nthe following parametric LCP of order (n-l).

11 w1 w2..... z 1 z2..... W1 W2 Wn2 Zn-l 1 2 n-2 n-l q 2n+ 2 - 2y 2n+ 4 - 2y I(n-1) x(n-i) -M(n-) (13) 2n +2n-1 -2y We can note that for y < 2 + i,(w1, 2,..., Wn2, Zn-l) is a feasible set of complementary basic variables for the above parametric LCP. Lemma 3: Starting from y = 2 + 1, the feasible complementary basic vector for (13) changes at every unit increase of y. Proof: We note that when the VDA is applied to (13) every step is a principal pivot step from one unique solution to the next as y increases. The lemna will be proved by induction on the size of the subproblem under consideration in the VDA algorithm for fixed problem size n. The (n-k) order parametric LCP subproblem will be the problem obtained from (13) by deleting the last k rows and the columns. corresponding to the variables Wn-k, Wn-k+l'1' Wn-1l Zn-k, Zn-k+1l',' Zn-l Induction Hypothesis. Let us suppose that y increases by one at each step when attempting to solve the (n-2) order parametric LCP subproblem using the VDA and that 2n -1 steps are requiredo The induction hypothesis can easily be verified for the subproblem of order 2 where n > 3.

12 w1 W2 z1 z2 q Range of y for which q is not negative. 1 0 -1 -2 2n+ 2 -2y ny< 2- + 1 0 1 0 -1 2n + 4 - 2-1 0 1 2 2y-2 -2 n-I n-l 2 + 1 < y 2 + 2 0 1 0 -1 2n + 4 - 2y -1 2 1 0 -2y + 2n + 6 2n-2 + 2 < y < 2n-1 + 3 0 -1 0 1 2y - 2 - 4 1 -2 -1 0 2y - 2n - 6 2n + 3 <y 0 -1 0 1 2y- 2- 4 Therefore, the induction hypothesis is true for the subproblem of order 2. We note that, in the LCP of order (n-l), q 2 = 2 - 2 e s non-l n- 2 remains nonnegative for all y < 2 + 2 After having solved the (n-2) order parametric LCP, the value of y is: n- + 1 + 2n-2 = 2n-1 + 2n-2 1 according to the induction hypothesis. Therefore, by the structure of M, the VDA will never choose to pivot on row (n-l) before having completely solved the (n-2) parametric LCP. After having solved the (n-2) parametric LCP, we obtain the unique complementary feasible basic solution given by (w, w2,..., Wn3, Zn-2) > 0 and (, z2,..., Zn-3 Wn-2) = 0. At this stage, the canonical tableau corresponding to the (n-l) order parametric LCP is:

13 w~ w2..... Wn_2 Zn 1 Z2.... z q 1 W2 * Wn-2 Zn-2 Zn-1 1 z2. zn —3 Wn-2 n- q 0 2 2n+2 + 2y-2n+l-2nn n. -. i. n-i 0 2 2n+4 + 2y-2n+-2n-'. M(n_2) *~ In-2 x n-2 2 2 + 2 0 2 -211 - 211" 22+ 2y 1 -1 2n + 2n-l 2y The right hand side and the column corresponding to w are obtained by n-l multiplying on the left by the inverse of the basis. The above basis is feasible for the values of: n-i + 2n-2 -1 < < 2n1 + 2n-2 So the next step of the algorithm will be a pivot step on the (n-l)th row and the column corresponding to w. After that pivot step, we obtain the following tableau:

14 w1 w..... w z z z..zW z W Z w q W1 W2 n-3 n-2 n-l 1 2 n-3 n-2 n-l n 2 n-l n-2 2 0 2 +2 -2(Y-2 +2- ) 2 0 2n+4 -2(y-2n-l+2n-2 * ~ M- h(n-2.) n-2 x n-2 - - * 0 * 0 2 2 2 0 2n+2n-2(-2 ( 2n-1+2n-22 0 0 -1 0 0 1 2y- 2- 2 nn-i n-2 Note that q 1> 0 for y > 2 + 2 and by Lemma 2, y will strictly increase. Therefore, we will never perform a pivot step on the last row, hence we can disregard that row and the columns corresponding to w 1 and z _I. We are left with a parametric LCP of order n-2. Treat n-i n-2 Y - 2 + 2 X in the right hand side as a parameter. We then have an (n-2) order parametric LCP with parameter X. By the induction hypothesis, n-I the increases of X are of magnitude one starting with the value 2 + 1, and n-2 it will take 2 - 1 steps to solve the (n-2) parametric LCP with parameter X. At termination, the value of X will be: X > 2n-1 + 2n-2 - 1.

15 We then have - 2n-1 + 2n-2 2n-1 + 2n-2 Y > 2n 1. This completes the proof of the lemma. I The number of steps required to solve the parametric LCP of order (n-l) is the sum of: (a) 2 - 1 steps to solve the (n-2) problem with parameter y. (b) One step to obtain the new parametric LCP of order n-2. (c) 2 - 1 steps to solve the (n-2) parametric LCP with parametric X. Hence, the solution of the parametric LCP required 2 - 1 steps. Now let us return to the original LCP(q(n), M(n)), Theorem: The variable dimension algorithm applied to LCP(q(n), M(n)) requires 2n - 1 steps to find a feasible complementary basic solution. Proof: We will prove the theorem by induction on the size,(n-k), of the subproblem considered by the algorithm for fixed problem size n. n-i Induction Hypothesis: Let us suppose that 2 - 1 steps are required to solve the (n-l) order subproblem. The hypothesis is easily verified for the subproblem of order two.

16 w1 w2 z1 z2 q n+l 1 0 -1 -2 -2n+1 + 2 0 1 0-1 -2n+l + 4 -1 0 +1 +2 2n+1 - 2 0 1 0 -1 -2n+l +4 n+l 0 -1 0 1 2n - 4 1 -2 -1 0 2n+l -6 Since the unique solution of the (n-l) problem requires (wl, w2,..,w n-2 Zn ) > 0 and all other variables to be zero, then when the nth problem is first considered, the problem has the canonical tableau form of (7). Since the increases of Y are of magnitude one, then the increases of z in problem (7) will also be one because the VDA maintains feasibility of the (n-l) subproblem. Also we have mentioned that w will increase n at the same rate as z, therefore, the algorithm will never pivot on the nth row until z = 2 - 1 and w = - 1, otherwise, the feasibility of the (n-) problem would be violated. (n-l) problem would be violated.

17 So the solution of the LCP (7) will require 21 - 1 steps to solve the (n-l) parametric LCP. Since the problem is nondegenerate, we will never visit the same almost complementary solution having (w, Zn) as the n-i basic pair twice. Thus after 2 -1 steps, we will have visited all possible almost complementary basic vectors having (Wn, zn) as the basic pair. Therefore, when z = 2-1 the last pivot step will be performed on the nth row. Hence, the number of steps required to solve the problem (7) is 2, and, by the induction hypothesis, the (n-l) subproblem re(7) is 2n-1 and, by the induction hypothesis, the (n-1) subproblem requires 2 -1 steps, making the total requirement 2n-1 steps. I 4,. Dantzig-Cottle's Principal Pivoting Method. PPM applies to an LCP(q, M) when M is a P-matrix or is positive semi-definite. There are two versions of the method, symmetric and asymmetric. We will describe the latter only for the P-matrix case. The methods follows major cycles, during each of which it reduces the number of negative components of q by at least one. When a component of q becomes positive, it will never become negative again during the process of solving the LCP(q, M). It is this monotonic reduction of the number of negative components of q that makes the method finite. Principal Pivoting Method [3]. In the following w, z, M and q represent the basic vector, the nonbasic vector, the matrix of nonbasic coefficients in the canonical tableau and the constant column at the Zth iteration, respectively.

18 Step 0. Set k = 0. Begin with the system w = Mz + q. Step 1. If q > 0 stop, (w, z ) = (q, O) is the solution. Otherwise, choose some q < 0, and let w be the 9 "s' s distinguished variable. Step 2. Determine the blocking variable by letting 0 be the largest value of the driving variable z such that one s of the basic variable goes to zero. (a) If z is blocked by w then pivot on m, replace 9 by 9 + 1 and go to Step 1. (b) If z is blocked by wi, i + s, then pivot on m., s IS replace by + 1 and go to Step 2 with zS = Z replace k by Z + 1 and go to Step 2 with z =z s i the complement of the leaving variable, as the new driving variable. n-i Corollary: PPM requires 2 steps to solve the LCP (7). Pro When the matrix of an LCP(q, M) is a P-matrix and the vector q has only the last component negative then, under nondegeneracy, PPM and VDA are the same method as noted in Remark (2). Therefore, since the VDA n-l n-1 requires 2 steps to solve problem (7), then PPM will also require 2 steps. i 5. Conclusion We have presented a class of LCPs for which Van der Heyden's VDA algorithm and Dantzig and Cottle's PPM method require a number of steps not bounded above by a polynomial in the problem size. Combining these

19 results with Murty's and Fathi's, we can conclude that almost all the direct methods for solving the linear complementary problem can require such exponential growth in computational effort. These results are intended only to show worst case behavior and do not address the average time behavior of the algorithms for general problems.

UNIVERSITY OF MICHIGAN 20 HIIIBIII N~I II/IIIReferences 3 9015 03994 7778 [1] R. W. Cottle, "The principal pivoting method of quadratic programming", in: G. B. Datitzig and A. F. Veinott, Jr., ed., Mathematics of the Decision Sciences, Part 1 (American Mathematical Society, 1968) pp. 144-162. [2] R. W. Cottle, "Completely Q-matrices", Mathematical Programming, 19 (1980) 347-351. [3] R. W. Cottle and G, B. Dantzig, "Complementary pivot theory of mathematical programming", Linear Algebra and its Applications 1 (1968) 103-125. [4] Y. Fathi, "On the computational complexity of the linear complementarity problem", Dissertation, The University of Michigan (Ann Arbor, Michigan, 1979). [5] C. E. Lemke, "Bimatrix equilibrium points and mathematical programming", Management Science 4 (1965) 681-689. [6] K. G. Murty, "Note on a Bard-type scheme for solving the complementarity problem", Opsearch 11 (1974) 123-130. [7] K. G. Murty, "Computational complexity of complementary pivot methods", Mathematical Programming Study 7 (1978) 61-73. [8] L. Van der Heyden, "A variable dimension algorithm for the linear complementarity problem", Mathematical Programming 19 (1980) pp. 328-346.