{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:34:32Z","timestamp":1787333672919,"version":"build-2736575974"},"reference-count":23,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[1998,5]]},"abstract":"<jats:p>In this paper we study a first-order and a high-order algorithm for solving linear complementarity problems. These algorithms are implicitly associated with a large neighborhood whose size may depend on the dimension of the problems. The complexity of these algorithms depends on the size of the neighborhood. For the first-order algorithm, we achieve the complexity bound which the typical large-step algorithms possess. It is well known that the complexity of large-step algorithms is greater than that of short-step ones. By using high-order power series (hence the name high-order algorithm), the iteration complexity can be reduced. We show that the complexity upper bound for our high-order algorithms is equal to that for short-step algorithms.<\/jats:p>","DOI":"10.1137\/s1052623494275574","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"397-413","source":"Crossref","is-referenced-by-count":13,"title":["Interior Point Algorithms For Linear Complementarity Problems Based On Large Neighborhoods Of The Central Path"],"prefix":"10.1137","volume":"8","author":[{"given":"Gongyun","family":"Zhao","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,31]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01586933"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/0801018"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/0801019"},{"key":"R4","unstructured":"P. Hung and Y. Ye,\n                      An AsymptoticalO(nL)\u2010Iteration Path\u2010Following Linear Programming Algorithm that Uses Long Steps\n                      , Technical report no. 53, on Computational Mathematics, Dept. of Mathematics, University of Iowa, Iowa City, IA, 1994."},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1007\/BF02191759"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/BF01246327"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1989.tb00316.x"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581234"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-54509-3"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"MasakazuKojima, ShinjiMizuno, AkikoYoshise, A primal\u2010dual interior point algorithm for linear programming, Springer, New York, 1989, 29\u20134790k:90093","DOI":"10.1007\/978-1-4613-9617-8_2"},{"key":"R11","unstructured":"S. Mehrotra,\n                      Higher Order Methods and Their Performance\n                      , Technical report 90\u201016R1, Dept. of Industrial Engineering and Management Science, Northwestern University, Evanston, IL, 1990 (revised July 1991)."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1287\/moor.18.4.964"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1287\/moor.15.2.191"},{"key":"R14","unstructured":"F. A. Potra,\n                      On a Predictor\u2010Corrector Method for Solving Linear Programs from Infeasible Starting Points\n                      , Technical report 34, Department of Mathematics, The University of Iowa, Iowa City, IA, 1992."},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580724"},{"key":"R16","unstructured":"C. Roos and J.\u2010Ph. Vial,\n                      Long steps with the logarithmic penalty barrier function in linear programming\n                      , in Economic Decision\u2010Making: Games, Economics and Optimization, J. Gabszeywicz, J. F. Richard, and L. Wolsey, eds., Elsevier, Amsterdam, 1989, pp. 433\u2013441."},{"key":"R17","doi-asserted-by":"crossref","unstructured":"G. Sonnevend,\n                      An analytical center for polyhedrons and new classes for linear (smooth, convex) programming\n                      , in System Modelling and Optimization (Budapest, 1985), Lecture Notes in Control and Inform. Sci. 84, A. Pr\u00e9kopa, J. Szelezsan, and B. Strazicky, eds., Springer\u2010Verlag, New York, 1985, pp. 866\u2013876.","DOI":"10.1007\/BFb0043914"},{"key":"R18","unstructured":"MichaelTodd, Recent developments and new directions in linear programming, Math. Appl. (Japanese Ser.), Vol. 6, SCIPRESS, Tokyo, 1989, 109\u20131571114313"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1007\/BF01594937"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1016\/0025-5610(94)00053-V"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1007\/BF01182599"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1016\/0025-5610(94)00080-D"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1080\/02331939508844153"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S1052623494275574","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:17:18Z","timestamp":1787332638000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S1052623494275574"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,5]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1998,5]]}},"alternative-id":["10.1137\/S1052623494275574"],"URL":"https:\/\/doi.org\/10.1137\/s1052623494275574","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,5]]}}}