Skip to main content
SpringerLink
Log in

A full-Newton step feasible interior-point algorithm for monotone horizontal linear complementarity problems

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

In this paper, we present a full-Newton feasible step interior-point algorithm for solving monotone horizontal linear complementarity problems. In each iteration the algorithm performs only full-Newton step with the advantage that no line search is required. We prove under a new and appropriate strategy of the threshold that defines the size of the neighborhood of the central-path and of the update barrier parameter that the proposed algorithm is well-defined and the full-Newton step to the central-path is locally quadratically convergent. Moreover, we derive the complexity bound of the proposed algorithm with short-step method, namely, \(\mathcal {O}(\sqrt{n}\log \frac{n}{\epsilon })\). This bound is the currently best known iteration bound for monotone HLCP. Some numerical results are provided to show the efficiency of the proposed algorithm and to compare with an available method.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

References

  1. Achache, M.: A new primal-dual path-following method for convex quadratic programming. Comput. Appl. Math. 25, 97–110 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  2. Achache, M.: Complexity analysis and numerical implementation of a short-step algorithm for LCP. Appl. Math. Comput. 216(7), 1889–1895 (2010)

    MathSciNet  MATH  Google Scholar 

  3. Achache, M., Goutali, M.: Complexity analysis and numerical implementation of a full-Newton step interior-point algorithm for LCCO. Numer. Algorithms 70, 393–405 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  4. Achache, M., Boudiaf, N.: Complexity analysis of primal-dual algorithms for the semi-definite linear complementarity problem. J. Numer. Anal. Approx. Theory 40(2), 95–106 (2011)

    MATH  Google Scholar 

  5. Achache, M.: Complexity analysis of an interior-point algorithms for the semi-definite optimization based on a kernel function with a double barrier term. Acta Math. Sin. Engl. Ser. 31(3), 543–556 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  6. Bonnans, J.E., Gonzaga, C.C.: Convergence of interior-point algorithms for monotone linear complementarity problem. Math. Oper. Res. 21(1), 1–15 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  7. Cottle, R.W., Pang, J.S., Stone, R.E.: The Linear Complementarity Problem. Academic, San Diego (1992)

    MATH  Google Scholar 

  8. Darvay, Z., Papp, I.M., TaKács, P.R.: Complexity analysis of a full-Newton step interior point method for linear optimization. Period. Math. Hung. 73(1), 27–42 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  9. Huang, Z.H.: Polynomiality of high-order feasible interior-point method for solving the horizontal linear complementarity problems. J. Syst. Sci. Math. Sci. 20(4), 432–438 (2000)

    MathSciNet  MATH  Google Scholar 

  10. Jiang, X., Zhang, Y.: A smoothing-type algorithm for absolute value equations. J. Ind. Manag. Optim. 9(4), 789–798 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  11. Jiang, X., Zhang, Y.: An improved full-Newton step \(\cal{O}(n)\) infeasible interior-point method for horizontal linear complementarity problem. Numer. Algorithms 71(3), 491–503 (2016)

    Article  MathSciNet  Google Scholar 

  12. Mangasarian, O.L., Meyer, R.R.: Absolute value equations. Linear Algebra Appl. 419, 359–367 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  13. Monteiro, R., Tsuchiya, T.: Limiting behavior of the derivatives of certain trajectories associated with a monotone horizontal linear complementarity problem. Math. Oper. Res. 21(4), 793–814 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  14. Peng, J., Roos, C., Terlaky, T.: Self-regular functions and new search directions for linear and semi-definite optimization. Math. Program. 93, 129–171 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  15. Rohn, J.: On unique solvability of the absolute value equation. Optim. Lett. 3, 503–506 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  16. Roos, C., Terlaky, T., Vial, J.P.: Theory and Algorithms for Linear Optimization. An Interior Point Approach. Wiley, Chichester (1997)

    MATH  Google Scholar 

  17. Wang, G.Q., Bai, Y.Q.: Polynomial interior-point algorithms for \(P_{*}\)(\(\kappa \)) horizontal linear complementarity problem. J. Comput. Appl. Math. 233, 248–263 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  18. Wright, S.J.: Primal-Dual Interior-Point Methods. SIAM, University City (1997)

    Book  MATH  Google Scholar 

  19. Yong, L.: Iterative method for a class of linear complementarity problems. Int. Conf. Inf. Comput. Appl. 1, 390–398 (2010)

    Google Scholar 

  20. Zhang, L., Xu, Y.: A full-Newton step primal-dual interior-point algorithm for linear complementarity problem. J. Inf. Comput. Sci. 5(4), 305–313 (2010)

    Google Scholar 

  21. Zhang, Y.: On the convergence of a class of infeasible interior-point methods for horizontal linear complementarity problem. SIAM J. Optim. 4(1), 208–227 (1994)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Laboratoire de Mathématiques Fondamentales et Numériques, Université Ferhat Abbas-Sétif 1, 19000, Sétif, Algeria

    Mohamed Achache & Nesrine Tabchouche

Authors
  1. Mohamed Achache
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Nesrine Tabchouche
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mohamed Achache.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Achache, M., Tabchouche, N. A full-Newton step feasible interior-point algorithm for monotone horizontal linear complementarity problems. Optim Lett 13, 1039–1057 (2019). https://doi.org/10.1007/s11590-018-1328-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-018-1328-9

Keywords

Search

Navigation