{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:32:21Z","timestamp":1787333541269,"version":"build-2736575974"},"reference-count":24,"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":[[1996,5]]},"abstract":"<jats:p>An important advantage of infeasible interior-point methods over feasible interior-point methods is their ability to be warm-started from approximate solutions. It is therefore important for the convergence theory of these algorithms not to depend on the ability to alter the starting point. In a recent paper [SIAM J. Optim., 4 (1994), pp. 208\u2013227], Zhang proves a global linear convergence rate for an infeasible interior-point method for the horizontal linear complementarily problem, which unfortunately places a restriction on the starting point. It is easy to meet the restriction by altering the starting point, but this may take the point farther away from the solution, thus removing the advantage of warm-starting the algorithm. In this paper we extend Zhang\u2019s results to apply to arbitrary strictly positive starting points. We also show how the extended results can be used to prove convergence for an algorithm for box-constrained linear complementarily problems.<\/jats:p>","DOI":"10.1137\/0806018","type":"journal-article","created":{"date-parts":[[2005,2,23]],"date-time":"2005-02-23T05:51:47Z","timestamp":1109137907000},"page":"316-325","source":"Crossref","is-referenced-by-count":6,"title":["Convergence of an Infeasible Interior-Point Algorithm from Arbitrary Positive Starting Points"],"prefix":"10.1137","volume":"6","author":[{"given":"Stephen C.","family":"Billups","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael C.","family":"Ferris","sequence":"additional","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\/BF01582290"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01582899"},{"key":"R3","unstructured":"S. C. Billups, M. C. Ferris, Convergence of infeasible interior-point algorithms from arbitrary starting points, Tech. report, 1180, Computer Sciences Department, University of Wisconsin, Madison, WI, 1993"},{"key":"R4","volume-title":"The linear complementarity problem","author":"Cottle R. W.","year":"1992"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1080\/10556789508805619"},{"key":"R6","unstructured":"S. P. Dirkse, M. C. Ferris, A pathsearch damped Newton method for computing general equilibria, Mathematical Programming Tech. report, 94-03, Computer Sciences Department, University of Wisconsin, Madison, WI, 1994"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1287\/moor.20.2.441"},{"key":"R8","unstructured":"M. Kojima, N. Meggido, S. Mizuno, A primal-dual exterior point algorithm for linear programming, Tech. report, RJ 8500, IBM Alamaden Research Center, San Jose, CA, 1991"},{"key":"R9","unstructured":"M. Kojima, S. Mizuno, M. Todd, Infeasible interior-point primal-dual potential-reduction algorithms for linear programming, Tech. report, 1023, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY, 1992"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(91)90275-2"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/0802022"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1.2.70"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/0802028"},{"key":"R14","unstructured":"S. Mizuno, Polynomiality of Kojima\u2013Meggido\u2013Mizuno infeasible\u2013interior\u2013point algorithm for linear programming, Tech. report, 1006, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY, 1993"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1137\/0806001"},{"key":"R16","unstructured":"F. A. Potra, An infeasible interior-point predictor-corrector algorithm for linear programming, Tech. Report, 26, Department of Mathematics, University of Iowa, Iowa City, IA, 1992"},{"key":"R17","unstructured":"F. A. Potra, On a predictor-corrector method for solving linear programs from infeasible starting points, Reports on Computational Mathematics, 34, Department of Mathematics, University of Iowa, Iowa City, IA, 1992"},{"key":"R18","unstructured":"F. A. Potra, A quadratically convergent infeasible interior-point algorithm for linear programming, Tech. report, 28, Department of Mathematics, University of Iowa, Iowa City, IA, 1992"},{"key":"R19","unstructured":"F. A. Potra, R. Sheng, A modified $O(nL)$ infeasible-interior-point algorithm for LCP with quadratic convergence, Reports on Computational Mathematics, 54, Department of Mathematics, University of Iowa, Iowa City, IA, 1994"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1080\/10556789308805537"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1007\/BF02206813"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1007\/BF01582211"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1137\/0804012"},{"key":"R24","unstructured":"Y. Zhang, D. Zhang, Superlinear convergence of infeasible interior-point methods for linear programming, Tech. report, 92-15, Department of Mathematics and Statistics, University of Maryland Baltimore County, Baltimore, MD, 1992"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0806018","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:07:56Z","timestamp":1787332076000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0806018"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,5]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1996,5]]}},"alternative-id":["10.1137\/0806018"],"URL":"https:\/\/doi.org\/10.1137\/0806018","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,5]]}}}