Abstract
We present several improvements of the full-Newton step infeasible interior-point method for linear optimization introduced by Roos (SIAM J. Optim. 16(4):1110–1136, 2006). Each main step of the method consists of a feasibility step and several centering steps. We use a more natural feasibility step, which targets the μ +-center of the next pair of perturbed problems. As for the centering steps, we apply a sharper quadratic convergence result, which leads to a slightly wider neighborhood for the feasibility steps. Moreover, the analysis is much simplified and the iteration bound is slightly better.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Roos, C.: A full-Newton step O(n) infeasible interior-point algorithm for linear optimization. SIAM J. Optim. 16(4), 1110–1136 (2006) (electronic)
Ji, J., Potra, F.A., Sheng, R.: A predictor-corrector method for solving the P*(κ)-matrix LCP from infeasible starting points. Optim. Methods Softw. 6(2), 109–126 (1996)
Kojima, M., Megiddo, N., Mizuno, S.: A primal-dual infeasible-interior-point algorithm for linear programming. Math. Program. Ser. A 61(3), 263–280 (1993)
Lustig, I.J.: Feasibility issues in a primal-dual interior-point method for linear programming. Math. Program. Ser. A 49(2), 145–162 (1990/91)
Mizuno, S.: Polynomiality of infeasible-interior-point algorithms for linear programming. Math. Program. Ser. A 67(1), 109–119 (1994)
Potra, F.A.: An infeasible-interior-point predictor-corrector algorithm for linear programming. SIAM J. Optim. 6(1), 19–32 (1996)
Potra, F.A., Sheng, R.: A large-step infeasible-interior-point method for the P *-matrix LCP. SIAM J. Optim. 7(2), 318–335 (1997)
Potra, F.A., Sheng, R.: Predictor-corrector algorithm for solving P *(κ)-matrix LCP from arbitrary positive starting points. Math. Program. Ser. B 76(1), 223–244 (1997). Interior point methods in theory and practice (Iowa City, IA, 1994)
Zhang, Y.: On the convergence of a class of infeasible interior-point methods for the horizontal linear complementarity problem. SIAM J. Optim. 4(1), 208–227 (1994)
Mansouri, H., Roos, C.: Simplified O(nL) infeasible interior-point algorithm for linear optimization using full-Newton steps. Optim. Methods Softw. 22(3), 519–530 (2007)
Roos, C., Terlaky, T., Vial, J.P.: Interior Point Methods for Linear Optimization. Springer, New York (2006) (2nd edn. of Theory and Algorithms for Linear Optimization. Wiley, Chichester (1997))
Ye, Y.: Interior Point Algorithms. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, New York (1997)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Florian Potra.
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Gu, G., Mansouri, H., Zangiabadi, M. et al. Improved Full-Newton Step O(nL) Infeasible Interior-Point Method for Linear Optimization. J Optim Theory Appl 145, 271–288 (2010). https://doi.org/10.1007/s10957-009-9634-0
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10957-009-9634-0