Abstract
In this paper we propose an O(n 3 L) algorithm which is a modification of the path following algorithm [8] for a linear complementarity problem. The path following algorithm has to take a short step size in each iteration in order to bound the number of overall arithmetic operations by O(n 3 L). In practical computation, we can determine the step size adaptively. Mizuno, Yoshise, and Kikuchi [11] reported that such an adaptive algorithm required about O(L) iterations for some test problems. Here we show that we can use a rank one update technique in the adaptive algorithm so that the number of overall arithmetic operations is theoretically bounded by O(n 3 L).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
K.M. Anstreicher and R.A. Bosch, “Long steps in an O(n 3 L) algorithm for linear programming,” to appear in:Mathematical Programming (1992).
R.W. Cottle and G.B. Dantzig, “Complementary pivot theory of mathematical programming,”Linear Algebra and its Applications 1 (1968) 103–125.
R.M. Freund, “Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function,”Mathematical Programming 51 (1991) 203–222.
C.C. Gonzaga, “An algorithm for solving linear programming programs in O(n 3 L) operations,” in: N. Megiddo, ed.,Progress in Mathematical Programming, Interior Point and Related Methods (Springer, New York, 1988) pp. 1–28.
N. Karmarkar, “A new polynomial-time algorithm for linear programming,”Combinatorica 4 (1984) 373–395.
M. Kojima, S. Mizuno and A. Yoshise, “An\(O(\sqrt n L)\) iteration potential reduction algorithm for linear complementarity problems,”Mathematical Programming 50 (1991) 331–342.
M. Kojima, S. Mizuno and A. Yoshise, “A primal—dual interior point algorithm for linear programming,” in: N. Megiddo, ed.,Progress in Mathematical Programming, Interior Point and Related Methods (Springer, New York, 1989) pp. 29–47.
M. Kojima, S. Mizuno and A. Yoshise, “A polynomial-time algorithm for a class of linear complementarity problems,”Mathematical Programming 44 (1989) 1–26.
C.E. Lemke, “Bimatrix equilibrium points and mathematical programming,”Management Science 11 (1965) 681–689.
N. Megiddo, “Pathways to the optimal set in linear programming,” in: N. Megiddo, ed.,Progress in Mathematical Programming, Interior Point and Related Methods (Springer, New York, 1988) pp. 131–158.
S. Mizuno, A. Yoshise and T. Kikuchi, “Practical polynomial time algorithms for linear complementarity problems,”Journal of the Operations Research Society of Japan 32 (1989) 75–92.
S. Mizuno, “A new polynomial time method for a linear complementarity problem,” to appear in:Mathematical Programming (1992).
S. Mizuno, “An O(n 3 L) algorithm using a sequence for a linear complementarity problem,”Journal of the Operations Research Society of Japan 33 (1990) 66–75.
S. Mizuno, “O(n ρ L) iteration O(n 3 L) potential reduction algorithms for linear programming,”Linear Algebra and its Applications 152 (1991) 155–168.
R.C. Monteiro and I. Adler, “Interior path following primal—dual algorithms. Part I: Linear programming,”Mathematical Programming 44 (1989) 27–42.
R.C. Monteiro and I. Adler, “Interior path following primal—dual algorithms. Part II: Convex quadratic programming,”Mathematical Programming 44 (1989) 43–66.
K.G. Murty,Linear Complementarity, Linear and Nonlinear Programming (Heldermann, Berlin, 1988).
J. Renegar, “A polynomial-time algorithm based on Newton's method for linear programming,”Mathematical Programming 40 (1988) 59–94.
M.J. Todd, “Recent developments and new directions in linear programming,” in: M. Iri and K. Tanabe, eds.,Mathematical Programming (Kluwer Academic Publishers, Dordrecht, 1989) pp. 109–157.
P.M. Vaidya, “An algorithm for linear programming which requires O(((m+n)n 2 +(m+n) 1.5 n)L) arithmetic operations,”Mathematical Programming 47 (1990) 175–201.
Y. Ye, “An O(n 3 L) potential reduction algorithm for linear programming,”Mathematical Programming 50 (1991) 239–258.
Author information
Authors and Affiliations
Additional information
Research supported in part by the U.S. Army Research Office through the Mathematical Sciences Institute of Cornell University.
Research supported in part by NSF grants ECS-8602534 and DMS-8904406 and ONR contract N-00014-87-K0212.
Rights and permissions
About this article
Cite this article
Mizuno, S., Todd, M.J. An O(n 3 L) adaptive path following algorithm for a linear complementarity problem. Mathematical Programming 52, 587–595 (1991). https://doi.org/10.1007/BF01582906
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01582906