Abstract
We present an improved version of an infeasible interior-point method for horizontal linear complementarity problem (J. Optim. Theory Appl.,161(3),853–869, ??2014). In the earlier version, each iteration consisted of one so-called feasibility and a few centering steps. Here, each iteration consists of only a feasibility step, whereas the iteration bound improves the earlier bound.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Ai, W.B., Zhang, S.Z.: An \(O(\sqrt {nL})\) iteration primal-dual path-following method, based on wide neighborhoods and large updates, for monotone linear complementarity problems. SIAM J. Optim. 16(2), 400–417 (2005)
Fathi, Y.: Computational complexity of LCPs associated with positive definite matrices. Math. Program. 17(1), 335–344 (1979)
Gurtuna, F., Petra, C., Potra, F., Shevchenko, O., Vancea, A.: Corrector-predictor methods for sufficient linear complementarity problems. Comput. Optim. Appl. 48, 453–485 (2011)
Huang, Z.H.: Polynomiality of high-order feasible interior point method for solving the horizontal linear complementarity problems. J. Sys. Sci. Math. Sci. 20(4), 432–438 (2000)
Karmarkar, N.K.: A new polynomial-time algorithm for linear programming. Combinatorica 4, 373–395 (1984)
Kheirfam, B.: A new complexity analysis for full-Newton step infeasible interior-point algorithm for horizontal linear complementarity problems. J. Optim. Theory Appl. 161(3), 853–869 (2014)
Miao, J.: A quadratically convergent \(\mathcal {O}((1+\kappa )\sqrt {n}L)\)-iteration algorithm for the P ∗(κ)-matrix linear complementarity problem. Math. Program. 69, 355–368 (1995)
Murty, K.G.: Linear Complementarity, Linear and Nonlinear Programming. Helderman-Verlag, Berlin (1988)
Potra, F., Stoer, J.: On a class of superlinearly convergent polynomial time interior point methods for sufficient LCP. SIAM J. Optim. 20(3), 1333–1363 (2009)
Roos, C.: A full-Newton step O(n L) infeasible interior-point algorithm for linear optimization. SIAM J. Optim. 16(4), 1110–1136 (2006)
Roos, C., Terlaky, T., Vial, J.-Ph.: Theory and Algorithms for Linear Optimization. An Interior-Point Approach. Wiley, Chichester (1997)
Roos, C.: An improved and simplified full-Newton step O(n) infeasible interior-point method for linear optimization. SIAM J. Optim. 25(1), 102–114 (2015)
Stoer, J., Wechs, M., Mizuno, S.: High order infeasible-interior-point methods for solving sufficient linear complementarity problems. Math. Oper. Res. 23(4), 832–862 (1998)
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)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Kheirfam, B. An improved full-Newton step O(n) infeasible interior-point method for horizontal linear complementarity problem. Numer Algor 71, 491–503 (2016). https://doi.org/10.1007/s11075-015-0005-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11075-015-0005-7