Abstract
Recently, Mehrotra [3] proposed a predictor—corrector primal—dual interior-point algorithm for linear programming. At each iteration, this algorithm utilizes a combination of three search directions: the predictor, the corrector and the centering directions, and requires only one matrix factorization. At present, Mehrotra's algorithmic framework is widely regarded as the most practically efficient one and has been implemented in the highly successful interior-point code OB1 [2]. In this paper, we study the theoretical convergence properties of Mehrotra's interior-point algorithmic framework. For generality, we carry out our analysis on a horizontal linear complementarity problem that includes linear and quadratic programming, as well as the standard linear complementarity problem. Under the monotonicity assumption, we establish polynomial complexity bounds for two variants of the Mehrotra-type predictor—corrector interior-point algorithms. These results are summarized in the last section in a table.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
R.W. Cottle, J.S. Pang and R.E. Stone,The Linear Complementarity Problem (Academic Press, Boston, 1992).
I.J. Lustig, R.E. Marsten and D.F. Shanno. “On implementing Mehrotra's predictor—corrector interior point method for linear programming,”SIAM J. Optimization 2 (1992) 435–449.
S. Mehrotra, “On the implementation of a primal—dual interior point method,”SIAM J. Optimization 2 (1992) 575–601.
S. Mizuno, M.J. Todd and Y. Ye. “On adaptive step primal—dual interior-point algorithms for linear programming,”Mathematics of Operations Research 18 (1994) 964–981.
R. Sznajder and M.S. Gowda, “Generalizations ofP 0 - andP-properties; extended vertical and horizontal LCPs,” to appear in a special issue ofLinear Algebra and Its Applications honoring M. Fiedler and V. Ptak (1992).
R.A. Tapia, Y. Zhang, M. Saltzman and A. Weiser, “The predictor—corrector interior-point method as a composite Newton method,” Technical Report TR 90-17, Dept. of Mathematical Sciences, Rice University, Houston, TX 77251, USA (1990).
Y. Zhang, “On the convergence of a class of infeasible interior-point algorithms for the horizontal linear complementarity problem,”SIAM J. Optimization 4 (1994) 208–227.
Author information
Authors and Affiliations
Additional information
Research supported in part by NSF DMS-9102761, DOE DE-FG05-91ER25100 and DOE DE-FG02-93ER25171.
Corresponding author.
Rights and permissions
About this article
Cite this article
Zhang, Y., Zhang, D. On polynomiality of the Mehrotra-type predictor—corrector interior-point algorithms. Mathematical Programming 68, 303–318 (1995). https://doi.org/10.1007/BF01585769
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01585769