{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,12]],"date-time":"2026-10-12T20:40:25Z","timestamp":1791837625859,"version":"4.3.4"},"reference-count":18,"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":[[2005,1]]},"abstract":"<jats:p>In this paper we propose a new class of primal-dual path-following interior point algorithms for solving monotone linear complementarity problems. At each iteration, the method would select a target on the central path with a large update from the current iterate, and then the Newton method is used to get the search directions, followed by adaptively choosing the step sizes, which are, e.g., the largest possible steps before leaving a neighborhood that is as wide as the given ${\\cal N}^-_{\\infty}$ neighborhood. The only deviation from the classical approach is that we treat the classical Newton direction as the sum of two other directions, corresponding to, respectively, the negative part and the positive part of the right-hand side. We show that if these two directions are equipped with different and appropriate step sizes, then the method enjoys the low iteration bound of $O(\\sqrt{n}\\log L)$, where n is the dimension of the problem and $L=\\frac{(x^0)^Ts^0}{\\ep}$ with $\\ep$ the required precision and $(x^0,s^0)$ the initial interior solution. For a predictor-corrector variant of the method, we further prove that, besides the predictor steps, each corrector step also reduces the duality gap by a rate of $1-1\/O(\\sqrt{n})$. Additionally, if the problem has a strict complementary solution, then the predictor steps converge Q-quadratically.<\/jats:p>","DOI":"10.1137\/040604492","type":"journal-article","created":{"date-parts":[[2005,10,24]],"date-time":"2005-10-24T21:00:13Z","timestamp":1130187613000},"page":"400-417","source":"Crossref","is-referenced-by-count":98,"title":["An\n                    <i>O<\/i>\n                    $(\\sqrtn L)$ Iteration Primal-dual Path-following Method, Based on Wide Neighborhoods and Large Updates, for Monotone LCP"],"prefix":"10.1137","volume":"16","author":[{"given":"Wenbao","family":"Ai","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shuzhong","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1360\/02ys0141"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/S0025-5610(96)00046-9"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580610"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623494266869"},{"key":"R5","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":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/BF01587074"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"NimrodMegiddo, Pathways to the optimal set in linear programming, Springer, New York, 1989, 131\u201315890c:90147","DOI":"10.1007\/978-1-4613-9617-8_8"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1287\/moor.18.4.964"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1007\/BF01587075"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1007\/BF01587076"},{"key":"R11","unstructured":"J. M. Peng, T. Terlaky, and Y. B. Zhao,\n                      A Predictor\u2010Corrector Algorithm for Linear Optimization Based on a Specific Self\u2010Regular Proximity Function\n                      , Technical report, McMaster University, Ontario, Canada, 2003."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1080\/10556789908805766"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1287\/moor.22.2.408"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611971453"},{"key":"R15","unstructured":"X. Xu,\n                      AnO(nL)\u2010Iteration Large\u2010Step Infeasible Path\u2010Following Algorithm for Linear Programming\n                      , Technical report, Department of Management Sciences, University of Iowa, Iowa City, IA, 1994."},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032701"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585182"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581242"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/040604492","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:28:19Z","timestamp":1787333299000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/040604492"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,1]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2005,1]]}},"alternative-id":["10.1137\/040604492"],"URL":"https:\/\/doi.org\/10.1137\/040604492","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,1]]}}}