Top

Journal of Applied Mathematics and Computing

Published in:

31-05-2016 | Original Research

An infeasible interior-point algorithm for monotone linear complementarity problem based on a specific kernel function

Authors: M. Pirhaji, M. Zangiabadi, H. Mansouri

Published in: Journal of Applied Mathematics and Computing | Issue 1-2/2017

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this paper, a full-Newton step infeasible kernel-based interior-point algorithm for solving monotone linear complementarity problems is proposed. In each iteration, the algorithm computes the new feasibility search directions by using a specific kernel function with the trigonometric barrier term and obtains the centering search directions using the classical kernel function. The algorithm takes only full-Newton steps and therefore no line-searches are needed for generating the new iterations. The convergence of the algorithm is shown and it is proved that the iteration bound of the algorithm coincides with the currently best iteration bound for monotone linear complementarity problem.

previous article Solutions for a class of fractional Hamiltonian systems with a parameter

next article Modeling the virus dynamics in computer network with SVEIR model and nonlinear incident rate

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

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, 101–128 (2005)MathSciNetCrossRefMATH

Danhua, Z., Mingwang, Z.: A full-Newton step infeasible interior-point algorithm for \(P_{*}(\kappa )\)-linear complementarity problems. J. Syst. Sci. Complex. 27, 1027–1044 (2014)MathSciNetCrossRefMATH

El Ghami, M., Guennoun, Z.A., Bouali, S., Steihaug, T.: Interior-point methods for linear optimization based on a kernel function with a trigonometric barrier term. J. Comput. Appl. Math. 236, 3613–3623 (2012)MathSciNetCrossRefMATH

El Ghami, M.: Primal dual interior-point methods for \(P_{*}(\kappa )\)-linear complementarity problem based on a kernel function with a trigonometric barrier term. Optim. Theory Decis. Mak. Oper. Res. Appl. 31, 331–349 (2013)MathSciNet

Fathi Hafshejani, S., Fatemi, M., Peyghami, M.R.: An interior-point method for \(P_{*}(\kappa )\)-linear complementarity problem based on a trigonometric kernel function. J. Appl. Math. Comput. 48, 111–128 (2015)MathSciNetCrossRefMATH

Fathi, Y.: Computational complexity of LCPs associated with positive definite matrices. Math. Program 17, 335–344 (1979)MathSciNetCrossRefMATH

Kheirfam, B.: A full-Newton step infeasible interior-point algorithm for linear complementarity problems based on a kernel function. Algorithmic Oper. Res. 7, 103–110 (2013)MathSciNetMATH

Kheirfam, B., Haghighi, M.: A full-Newton step infeasible interior-point method for linear optimization based on a trigonometric kernel function. Optimization. doi:10.1080/02331934.2015.1080255, (2015)

Kheirfam, B., Moslemi, M.: A polynomial-time algorithm for linear optimization based on a new kernel function with trigonometric barrier term. Yugosl. J. Oper. Res. 25, 233–250 (2015)MathSciNetCrossRef

10.

Kojima, M., Mizuno, S., Yoshise, A.: A Primal-Dual Interior-Point Algorithm for Linear Programming, Progress in Mathematical Programming (Pacific Grove, CA, 1987), pp. 29–47. Springer, New York (1989a)

11.

Kojima, M., Mizuno, S., Yoshise, A.: A polynomial-time algorithm for a class of linear complementarity problems. Math. Program. 44, 1–26 (1989b)MathSciNetCrossRefMATH

12.

Liu, Y., Bai, Y.: Interior-point algorithm based on general kernel function for monotone linear complementarity problem. J. Shanghai Univ. 13, 95–101 (2009)MathSciNetCrossRefMATH

13.

Lustig, I.J.: Feasible issues in a primal-dual interior point method for linear programming. Math. Program. 49, 145–162 (1990–1991)

14.

Mansouri, H., Zangiabadi, M., Pirhaji, M.: A full-Newton step \(O(n)\) infeasible-interior-point algorithm for linear complementarity problems. Nonlinear Anal. Real World Appl. 12, 546–561 (2011)MathSciNetCrossRefMATH

15.

Megiddo, N.: Pathways to the Optimal Set in Linear Programming, Progress in Mathematical Programming (Pacific Grove, CA, 1987), pp. 131–158. Springer, New York (1989)

16.

Mizuno, S., Todd, M.J., Ye, Y.: On adaptive-step primal-dual interior-point algorithms for linear programming. Math. Oper. Res. 18, 964–981 (1993)MathSciNetCrossRefMATH

17.

Murty, K.G.: Linear Complementarity, Linear and Nonlinear Programming. Helderman, Berlin (1988)MATH

18.

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

19.

Potra, F., Sheng, R.: A path following method for LCP withsuperlinearly convergent iteration sequence. Ann. Oper. Res. 81, 97–114 (1998)MathSciNetCrossRefMATH

20.

Roos, C.: A full-Newton step \(O(n)\) infeasible interior-point algorithm for linear optimization. SIAM J. Optim. 16, 1110–1136 (2006)MathSciNetCrossRefMATH

21.

Tanabe, K.: Centered Newton method for linear programming: interior and ‘exterior’ point method. In: Tone, K. (ed.) New Methods for Linear Programming, vol. 3. The Institute of Statistical Mathematics, Tokyo (1990). (in Japanese)

22.

Zhang, L., Bai, Y., Xu, Y.: A full-Newton step infeasible interior-point algorithm for monotone LCP based on a locally-kernel function. Numer. Algorith. 61, 57–81 (2012)MathSciNetCrossRefMATH

Title: An infeasible interior-point algorithm for monotone linear complementarity problem based on a specific kernel function
Authors: M. Pirhaji
M. Zangiabadi
H. Mansouri
Publication date: 31-05-2016
Publisher: Springer Berlin Heidelberg
Published in: Journal of Applied Mathematics and Computing / Issue 1-2/2017
Print ISSN: 1598-5865
Electronic ISSN: 1865-2085
DOI: https://doi.org/10.1007/s12190-016-1019-6

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1-2/2017

M/M/1 queue with m kinds of differentiated working vacations

Topological efficiency under graph operations

Dynamical analysis of a fractional-order predator-prey model incorporating a prey refuge

On (p, q)-analogue of modified Bernstein–Schurer operators for functions of one and two variables

Existence and uniqueness of solutions to a fractional difference equation with p-Laplacian operator

Dynamical analysis of a new microbial pesticide model with the Monod growth rate

Premium Partner