A Modified-Newton Step Primal-dual Interior Point Algorithm for Linear Complementarity Problems

Abstract

[1] J. Bonnans and C. Gonzaga, “Convergence of interior point algorithms for the monotone linear complementarity problem,” Mathematics of Operations Research, vol. 21, no. 1, pp. 1–25, 1996.
http://dx.doi.org/10.1287/moor.21.1.1

[2] C. Gonzaga and J. Bonnans, “Fast convergence of the simplified largest step path following algorithm,” Mathematical Programming, vol. 76, no. 1, pp. 95–115, 1997.
http://dx.doi.org/10.1007/BF02614379

[3] C. Gonzaga, “The largest step path following algorithm for monotone linear complementarity problems,” Mathematical Programming, vol. 76, no. 2, pp. 309–332, 1997.
http://dx.doi.org/10.1007/BF02614443

[4] Z. Huang, “Polynomiality of high-order feasible interior point method for solving the horizontal linear complementarity problems,” Journal of System Science and Mathematical Sciences, vol. 20, no. 4, 2000.

[5] R. Monteiro and T. Tsuchiya, “Limiting behavior of the derivatives of certain trajectories associated with a monotone horizontal linear complementarity problem,” Mathematics of Operations Research, vol. 21, no. 4, pp. 793–814, 1996.
http://dx.doi.org/10.1287/moor.21.4.793

[6] Y. Zhang, “On the convergence of a class of infeasible interior-point methods for the horizontal linear complementarity problem,” SIAM Journal on Optimization, vol. 4, pp. 208–227, 1994.
http://dx.doi.org/10.1137/0804012

[7] S. Bellavia and B. Morini, “Global convergence enhancement of classical linesearch interior point methods for MCPs,” Journal of Computational and Applied Mathematics, vol. 151, no. 1, pp. 171–199, 2003.
http://dx.doi.org/10.1016/S0377-0427(02)00745-8

[8] G. Wang and Y. Bai, “Polynomial interior-point algorithms for p*(k) horizontal linear complementarity problem,” Journal of Computational and Applied Mathematics, vol. 233, no. 2, pp. 248–263, 2009.
http://dx.doi.org/10.1016/j.cam.2009.07.014

[9] Y. Bai, M. El Ghami, and C. Roos, “A new efficient large-update primal-dual interior-point method based on a finite barrier,” SIAM Journal on Optimization, vol. 13, pp. 766–782, 2002.
http://dx.doi.org/10.1137/S1052623401398132

[10] ——, “A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization,” SIAM Journal on Optimization, vol. 15, pp. 101–128, 2004.
http://dx.doi.org/10.1137/S1052623403423114

[11] J. Peng, C. Roos, and T. Terlaky, “New Complexity Analysis of the Primal-Dual Newton Method for Linear Optimization,” Annals of Operations Research, vol. 99, no. 1, pp. 23–39, 2000.
http://dx.doi.org/10.1023/A:1019280614748

[12] ——, Self-Regularity: A new paradigm for Primal-Dual interior-point algorithms. Princeton Univ Pr, 2002.

[13] M. Kojima, N. Megiddo, T. Noma, and A. Yoshise, “A unified approach to interior point algorithms for linear complementarity problems, volume 538 of Lecture Notes in Computer Science,” 1991.

[14] Z. Darvay, “A weighted-path-following method for linear optimization,” Studia Universitatis Babes-Bolyai, Series Informatica, vol. 47, no. 1, pp. 3–12, 2002.