×

zbMATH — the first resource for mathematics

An \(O(\sqrt n L)\) iteration potential reduction algorithm for linear complementarity problems. (English) Zbl 0738.90077
Summary: This paper proposes an interior point algorithm for a positive semi- definite linear complementarity problem: find an \((x,y)\in\mathbb{R}^{2n}\) such that \(y=Mx+q\), \((x,y)\geq 0\) and \(x^ Ty=0\). The algorithm reduces the potential function \[ f(x,y)=(n+\sqrt n)\log x^ Ty-\sum^ n_{i=1}\log x_ iy_ i \] by at least 0.2 in each iteration requiring \(O(n^ 3)\) arithmetic operations. If it starts from an interior feasible solution with the potential function value bounded by \(O(\sqrt n L)\), it generates, in at most \(O(\sqrt n L)\) iterations, an approximate solution with the potential function value \(-O(\sqrt n L)\), from which we can compute an exact solution in \(O(n^ 3)\) arithmetic operations. The algorithm is closely related with the central path following algorithm recently given by the authors [in: Progress in mathematical programming, Interior point and related methods, Proc. Conf., Pacific Grove/Calif. 1987, 29-47 (1989; Zbl 0708.90049); and Math. Program., Ser. A 44, No. 1, 1-26 (1989; Zbl 0676.90087)]. We also suggest a unified model for both potential reduction and path following algorithms for positive semi- definite complementarity problems.

MSC:
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
90C60 Abstract computational complexity for mathematical programming problems
90-08 Computational methods for problems pertaining to operations research and mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] I. Adler, N. Karmarkar, M.G.C. Resende and G. Veiga, ”An implementation of Karmarkar’s algorithm for linear programming,”Mathematical Programming 44 (1989) 297–335. · Zbl 0682.90061 · doi:10.1007/BF01587095
[2] K.M. Anstreicher and R.A. Bosch, ”Long steps in a O(n 3 L) algorithm for linear programming,” Technical Report, Yale School of Management (New Haven, CT, 1989).
[3] E.R. Barnes, ”A variation on Karmarkar’s algorithm for solving linear programming problems,”Mathematical Programming 36 (1986) 174–182. · Zbl 0626.90052 · doi:10.1007/BF02592024
[4] I.I. Dikin, ”Iterative solution of problems of linear and quadratic programming,”Soviet Mathematics Doklady 8 (1967) 674–675. · Zbl 0189.19504
[5] R.M. Freund, ”Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function,” OR 182-88, Sloan School of Management, Massachusetts Institute of Technology (Cambridge, MA, 1988).
[6] D Gay, ”A variant of Karmarkar’s linear programming algorithm for problems in standard form,”Mathematical Programming 37 (1987) 81–90. · Zbl 0629.90056 · doi:10.1007/BF02591685
[7] C.C. Gonzaga, ”Newton barrier function algorithms for following the cental trajectory in linear programming problems,”13th Mathematical Programming Symposium, Tokyo, Department of Systems Engineering and Computer Sciences, COPPE-Federal University of Rio de Janeiro (Rio de Janeiro, Brasil, 1988).
[8] 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, 1989) pp. 1–28.
[9] N. Karmarkar, ”A new polynomial-time algorithm for linear programming,”Combinatorica 4 (1984) 373–395. · Zbl 0557.90065 · doi:10.1007/BF02579150
[10] M. Kojima, N. Megiddo and T. Noma, ”Homotopy continuation methods for nonlinear complementarity problems,” to appear in:Mathematics of Operations Research (1991). · Zbl 0744.90087
[11] M. Kojima, N. Megiddo and Y. Ye, ”An interior point potential reduction algorithm for the linear complementarity problem,” to appear in:Mathematical Programming (1992). · Zbl 0764.90083
[12] 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. · Zbl 0708.90049
[13] M. Kojima, S. Mizuno and A. Yoshise, ”A polynomial-time algorithm for a class of linear complementary problems,”Mathematical Programming 44 (1989) 1–26. · Zbl 0676.90087 · doi:10.1007/BF01587074
[14] 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, 1989) pp. 131–158. · Zbl 0687.90056
[15] R.D.C. Monteiro and I. Adler, ”Interior path following primal–dual algorithms. Part I: Linear programming,”Mathematical Programming 44 (1989) 27–41. · Zbl 0676.90038 · doi:10.1007/BF01587075
[16] R.D.C. Monteiro and I. Adler, ”Interior path following primal–dual algorithms. Part II: Convex quadratic programming,”Mathematical Programming 44 (1989) 43–66. · Zbl 0676.90039 · doi:10.1007/BF01587076
[17] J. Renegar, ”A polynomial-time algorithm based on Newton’s method for linear programming,”Mathematical Programming 40 (1988) 59–94. · Zbl 0654.90050 · doi:10.1007/BF01580724
[18] G. Sonnevend and J. Stoer, ”Global ellipsoidal approximations and homotopy methods for solving convex analytic programs,” Report No. 40, Institut für Angewandte Mathematik und Statistik, Universität Würzburg (Am Hubland, Würzburg, 1988). · Zbl 0691.90071
[19] M.J. Todd and B.P. Burrell, ”An extension of Karmarkar’s algorithm for linear programming and using dual variables,”Algorithmica 1 (1986) 409–424. · Zbl 0621.90048 · doi:10.1007/BF01840455
[20] M.J. Todd and Y. Ye, ”A centered projective algorithm for linear programming,”Mathematics of Operations Research 15 (1990) 508–529. · Zbl 0722.90044 · doi:10.1287/moor.15.3.508
[21] 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. · Zbl 0708.90047 · doi:10.1007/BF01580859
[22] Y. Ye, ”A class of potential functions for linear programming,” Technical Report, Department of Management Sciences, The University of Iowa (Iowa City, IA, 1988).
[23] Y. Ye and M. Kojima, ”Recovering optimal dual solutions in Karmarkar’s polynomial algorithm for linear programming,”Mathematical Programming 39 (1987) 305–317. · Zbl 0639.90062 · doi:10.1007/BF02592079
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.