Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Fast convergence of an inexact interior point method for horizontal complementarity problems

  • Original Paper
  • Published:
Numerical Algorithms Aims and scope Submit manuscript

Abstract

In Andreani et al. (Numer. Algorithms 57:457–485, 2011), an interior point method for the horizontal nonlinear complementarity problem was introduced. This method was based on inexact Newton directions and safeguarding projected gradient iterations. Global convergence, in the sense that every cluster point is stationary, was proved in Andreani et al. (Numer. Algorithms 57:457–485, 2011). In Andreani et al. (Eur. J. Oper. Res. 249:41–54, 2016), local fast convergence was proved for the underdetermined problem in the case that the Newtonian directions are computed exactly. In the present paper, it will be proved that the method introduced in Andreani et al. (Numer. Algorithms 57:457–485, 2011) enjoys fast (linear, superlinear, or quadratic) convergence in the case of truly inexact Newton computations. Some numerical experiments will illustrate the accuracy of the convergence theory.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

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

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Andreani, R., Birgin, E.G., Martínez, J.M., Schuverdt, M.L.: Augmented Lagrangian methods under the constant positive linear dependence constraint qualification. Math. Program. 111, 5–32 (2008)

    Article  MathSciNet  Google Scholar 

  2. Andreani, R., Júdice, J.J., Martínez, J.M., Martini, T.: Feasibility problems with complementarity constraints. Eur. J. Oper. Res. 249, 41–54 (2016)

    Article  MathSciNet  Google Scholar 

  3. Andreani, R., Júdice, J.J., Martínez, J.M., Patricio, J.: On the natural merit function for solving complementarity problems. Math. Program. 130, 211–223 (2011)

    Article  MathSciNet  Google Scholar 

  4. Andreani, R., Júdice, J.J., Martínez, J.M., Patricio, J.: A projected-gradient interior-point algorithm for complementarity problems. Numer. Algorithms 57, 457–485 (2011)

    Article  MathSciNet  Google Scholar 

  5. Arenas, F.E., Martínez, H.J., Pérez, R.: Least change secant update methods for nonlinear complementarity problem. Ing. Cienc. 11, 11–36 (2015)

    Article  Google Scholar 

  6. Arias, C.A., Martínez, H.J., Pérez, R.: A global quasi-Newton algorithm for nonlinear complementarity problem. Pac. J. Optim. 13(1), 1–15 (2017)

    MathSciNet  Google Scholar 

  7. Bellavia, S.: Inexact interior-point method. J. Optim. Theory Appl. 96, 109–121 (1998)

    Article  MathSciNet  Google Scholar 

  8. Facchinei, F., Pang, J.S.: Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer Ser. Oper. Res. Financ. Eng. (2003)

  9. Fernandes, L., Friedlander, A., Guedes, M.C., Júdice, J.: Solution of a general linear complementarity problem using smooth optimization and its applications to bilinear programming and LCP. Appl. Math. Optim 43, 1–19 (2001)

    Article  MathSciNet  Google Scholar 

  10. Ferris, M.C., Kanzow, C., Munson, T.S.: Feasible descent algorithms for mixed complementarity problems. Math. Program. 86(475), 497 (1999)

    MathSciNet  MATH  Google Scholar 

  11. Ferris, M.C., Pang, J.: Engineering and economic applications of complementarity problems. SIAM Rev. 39, 669–713 (1997)

    Article  MathSciNet  Google Scholar 

  12. Freund, R.W., Jarre, F., Mizuno, S: Convergence of a class of inexact interior-point algorithms for linear programs. Math. Oper. Res. 24, 50–71 (1999)

    Article  MathSciNet  Google Scholar 

  13. Gondzio, J.: Matrix-free interior point method. Comput. Optim. Appl. 51, 457–480 (2012)

    Article  MathSciNet  Google Scholar 

  14. Kojima, M., Megiddo, N., Noma, T., Yoshise, A.: A unified approach to interior-point algorithms for linear complementarity problems. Lect. Notes Comput. Sci. 58, 1–112 (1991)

    MATH  Google Scholar 

  15. Kostreva, M.: Elasto-hydrodynamic lubrication: a non-linear complementarity problem. Int. J. Numer. Methods Fluids 4, 377–397 (1984)

    Article  Google Scholar 

  16. Li, L., Toh, K.: An inexact interior point method for L 1 regularized sparse covariance selection. Math. Prog. Comput. 2, 291–315 (2010)

    Article  Google Scholar 

  17. Murty, K.: Linear Complementarity, Linear and Nonlinear Programming. Heldermann Verlag, Berlin (1988)

    MATH  Google Scholar 

  18. Wardrop, J.G.: Some theoretical aspects of road traffic research. Proc. ICE 36, 325–378 (1952)

    Google Scholar 

Download references

Acknowledgements

We are grateful to the associated editor and an anonymous referee for valuable comments and suggestions.

Funding

This work has been partially supported by the Brazilian agencies FAPESP (grants 2010/10133-0, 2013/03447-6, 2013/05475-7, 2013/07375-0, and 2014/18711-3) and CNPq (grants 309517/2014-1 and 03750/2014-6), and by the International Relationship Direction (DRI) of the University of Valle and COLCIENCIAS.

Author information

Authors and Affiliations

  1. Department of Mathematics, University of Valle, Cali, Colombia

    C. A. Arias

  2. Department of Applied Mathematics, Institute of Mathematics, Statistics, and Scientific Computing (IMECC), University of Campinas, Campinas, SP, 13083-859, Brazil

    J. M. Martínez

Authors
  1. C. A. Arias
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. J. M. Martínez
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to C. A. Arias.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Arias, C.A., Martínez, J.M. Fast convergence of an inexact interior point method for horizontal complementarity problems. Numer Algor 79, 1187–1210 (2018). https://doi.org/10.1007/s11075-018-0480-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11075-018-0480-8

Keywords

Search

Navigation