Skip to main content
SpringerLink
Log in

A kernel function based Interior-Point Methods for solving P *(κ)-linear complementarity problem

  • Published:
Acta Mathematica Sinica, English Series Aims and scope Submit manuscript

Abstract

In this paper, motivated by the complexity results of Interior Point Methods (IPMs) for Linear Optimization (LO) based on kernel functions, we present a polynomial time IPM for solving P *(κ)-linear complementarity problem, using a new class of kernel functions. The special case of our new class was considered earlier for LO by Y. Q. Bai et al. in 2004. Using some appealing properties of the new class, we show that the iteration bound for IPMs matches the so far best known theoretical iteration bound for both large and small updates by choosing special values for the parameters of the new class.

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

Similar content being viewed by others

References

  1. Karmarkar, N. K.: A new polynomial-time algorithm for linear programming. Combinatorica, 4, 373–395 (1984)

    Article  MATH  MathSciNet  Google Scholar 

  2. Nemirovski, A., Nestrov, Y.: Interior-Point Polynomial Algorithms in Convex Optimization, SIAM Studies in Applied Mathematics, Philadelphia, 1994

    Google Scholar 

  3. Roos, C., Terlaky, T., Vial, J-P.: Theory and Algorithms for Linear Optimization: An Interior Point Approach, Springer, New York, 2005

    Google Scholar 

  4. Wright, S. J.: Primal-Dual Interior-Point Methods, SIAM Publications, Philadelphia, 1997

    MATH  Google Scholar 

  5. Ye, Y.: Interior-Point Algorithms: Theory and Analysis, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Chichester, 1997

    Google Scholar 

  6. Cottle, R. W., Pang, J. S., Stone, R. E.: The Linear Complementarity Problem, Academic Press Inc., San Diego, 1992

    MATH  Google Scholar 

  7. Ferris, M. C., Pang, J. S.: Complementarity and Variational Problems: State of the Art. In: Proceedings of the International Conference on Complementarity Problems, Philadelphia, SIAM, 1997

    Google Scholar 

  8. Kojima, M., Megiddo, N., Noma, T., et al.: A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems. In: Lecture Notes in Computer Science, Volume 538, Springer-Verlag, Berlin, 1991

    Google Scholar 

  9. Anitescu, M., Lesaja, G., Potra, F.: An infeasible interior-point predictor-corrector algorithm for the P *-geometric LCP. Appl. Math. Optim., 36, 203–228 (1997)

    MATH  MathSciNet  Google Scholar 

  10. Wright, S. J., Zhang, Y.: A superquadratic infeasible-interior-point method for linear complementarity problems. Math. Program, 73, 269–289 (1996)

    MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  12. Bai, Y. Q., Roos, C.: A polynomial-time algorithm for linear optimization based on a new simple kernel function. Optim. Methods Softw., 18(6), 631–646 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  13. He, S., Li, X., Pan, S.: A self-adjusting interior point algorithm for linear complementarity problems. Comput. Math. Appl., 50, 33–40 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  14. Amini, K., Peyghami, M. R.: An interior-point algorithm for linear optimization based on a new kernel function. Southeast Asian Bull. Math., 29, 651–667 (2005)

    MATH  MathSciNet  Google Scholar 

  15. Bai, Y. Q., Guo, J., Roos, C.: A new kernel function yielding the best known iteration bounds for primaldual interior-point algorithms. Acta Mathematica Sinica, English Series, 25(12), 2169–2178 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  16. Bai, Y. Q., El ghami, M., Roos, C.: A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization. SIAM J. Optim., 15(1), 766–782 (2004)

    Article  Google Scholar 

  17. Bai, Y. Q., Lesaja, G., Roos, C.: A new class of polynomial interior-point algorithms for P *(κ)-linear complementary problems. Pac. J. Optim., 4(1), 19–41 (2008)

    MATH  MathSciNet  Google Scholar 

  18. Väliaho, H.: P *-matrices are just sufficient. Linear Algebra Appl., 239, 103–108 (1999)

    Google Scholar 

  19. Amini, K., Peyghami, M. R.: An interior-point algorithm for linear programming based on a class of kernel functions. Bull. Austral. Math. Soc., 71, 139–153 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  20. Bai, Y. Q., El ghami, M., Roos, C.: A new efficient large-update primal-dual interior point method based on a finite barrier. SIAM J. Optim., 13(3) (electronic), 766–782 (2003)

    Article  MATH  Google Scholar 

  21. Peng, J., Roos, C., Terlaky, T.: A new class of polynomial primal-dual methods for linear and semidefinite optimization. European J. Oper. Res., 143(2), 234–256 (2002)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, K. N. Toosi University of Technology, P. O. Box 16315-1618, Tehran, Iran

    M. Reza Peyghami

  2. School of Mathematics, Institute for Research in Fundamental Sciences (IPM), P. O. Box 19395-5746, Tehran, Iran

    M. Reza Peyghami

  3. Department of Mathematics, Faculty of Sciences, Razi University, Kermanshah, Iran

    Keyvan Amini

Authors
  1. M. Reza Peyghami
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Keyvan Amini
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to M. Reza Peyghami.

Additional information

Supported by a grant from IPM (Grant No. 8890027)

Rights and permissions

Reprints and permissions

About this article

Cite this article

Peyghami, M.R., Amini, K. A kernel function based Interior-Point Methods for solving P *(κ)-linear complementarity problem. Acta. Math. Sin.-English Ser. 26, 1761–1778 (2010). https://doi.org/10.1007/s10114-010-7529-5

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10114-010-7529-5

Keywords

MR(2000) Subject Classification

Search

Navigation