nach oben

Journal of Applied Mathematics and Computing

Erschienen in:

11.05.2020 | Original Research

A new full-Newton step interior-point method for \(P_{*}(\kappa )\)-LCP based on a positive-asymptotic kernel function

verfasst von: Mingwang Zhang, Kun Huang, Mengmeng Li, Yanli Lv

Erschienen in: Journal of Applied Mathematics and Computing | Ausgabe 1-2/2020

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this paper, we propose a new full-Newton step interior-point method (IPM) for \(P_{*}(\kappa )\) linear complementarity problem (LCP). The search direction is obtained by applying algebraic equivalent transformation on the centering equation of the central path which is introduced by Darvay et al. for linear optimization (Optim Lett 12(5):1099–1116, 2018). They point out that the search direction can also be obtained by using a positive-asymptotic kernel function. This kernel function has not been used in the complexity analysis of IPMs for \(P_{*}(\kappa )\)-LCP before. Assuming a strictly feasible starting point is available, we show that the algorithm has the iteration complexity bound \(O((1+4\kappa )\sqrt{n}\log {\frac{n}{\epsilon }})\), which is the best known complexity result for such methods. Some numerical results have been provided.

Vorheriger Artikel Explicit solutions for distributed, boundary and distributed-boundary elliptic optimal control problems

Nächster Artikel Mathematical analysis and optimal control applied to the treatment of leukemia

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

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

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

Wright, S.J.: Primal-Dual Interior-Point Methods. SIAM, Philadelphia (1997)CrossRef

Cottle, R.W., Pang, J.S., Stone, R.E.: The Linear Complementarity Problem. Academic Press, New York (1992)MATH

Roos, C., Vial, J-Ph: A polynomial method of approximate centers for linear programming. Math. Program. 54(1–3), 295–305 (1992)MathSciNetCrossRef

NeterrovR, E., Nemirovskii, A.S.: Interior-Point Ploynomial Methods in Convex Programming. SIAM, Philadelphia (1994)

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

Kojima, M., Megiddo, N., Noma, T., Yoshise, A.: A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems, Volume 538. Springer, Berlin (1991)CrossRef

Miao, J.M.: A quadratically convergent \(O((1+\kappa )\sqrt{n}L)\)-iteration algorithm for the \(P_{*}(\kappa )\)-matrix linear complementarity problem. Math. Program. 69(1–3), 355–368 (1995)

10.

Potra, F.A., Sheng, R.Q.: Predictor-corrector algorithm for solving \(P_{*}(\kappa )\)-matrix lcp from arbitrary positive starting points. Math. Program. 76(1), 223–244 (1996)CrossRef

11.

Illes, T., Nagy, M., Terlaky, T.: Ep theorem for dual linear complementarity problems. J. Optim. Theory Appl. 140(2), 233–238 (2009)MathSciNetCrossRef

12.

Illes, T., Nagy, M., Terlaky, T.: A polynomial path-following interior point algorithm for general linear complementarity problems. J. Global Optim. 47(3), 329–342 (2010)MathSciNetCrossRef

13.

Peng, J.M., Roos, C., Terlaky, T., Yoshise, A.: Self-regular proximities and new search directions for nonlinear \(P_{*}(\kappa )\) complementarity problems. Tech. Rep., Faculty of Tech. Math. and Inform., Delft Univ. of Tech., The Netherlands (2000)

14.

Bai, Y.Q., Lesaja, G., Roos, C.: A new class of polynomial interior-point algorithms for \(P_{*}(\kappa )\)-linear complementarity problems. Pac. J. Optim. 4(1), 248–263 (2008)MATH

15.

Lesaja, G., Roos, C.: Unified analysis of kernel-based interior-point methods for \(P_{*}(\kappa )\)-linear complementarity problems. J. Optim. 20(6), 3014–3039 (2010)MathSciNetMATH

16.

Ji, P., Zhang, M.W., Li, X.: A primal-dual large-update interior-point algorithm for \(P_{*}(\kappa )\)-LCP based on a new class of kernel functions. Acta Math. Appl. Sin. Engl. Ser. 34(1), 119–134 (2018)MathSciNetCrossRef

17.

Wang, G.Q., Yu, C.J., Teo, K.L.: A full-newton step feasible interior-point algorithm for \(P_{*}(\kappa )\)-linear complementarity problems. J. Global Optim. 59(1), 81–99 (2014)MathSciNetCrossRef

18.

Darvay, Z.: A new algorithm for solving self-dual linear optimization problems. Studia Univ. Babe s-Bolyai Ser. Informatica 47, 15–26 (2002)MathSciNetMATH

19.

Darvay, Z.: New interior-point algorithms in linear programming. Adv. Model. Optim. 5(1), 51–92 (2003)MathSciNetMATH

20.

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

21.

Kheirfam, B., Haghighi, M.: A full-newton step feasible interior-point algorithm for \(P_{*}(\kappa )\)-lcp based on a new search direction. Croatian Oper. Res. Rev. 7(2), 277–290 (2016)MathSciNetCrossRef

22.

Wang, G.Q., Fan, X.J., Zhu, D.T., Wang, D.Z.: New complexity analysis of a full-newton step feasible interior-point algorithm for \(P_{*}(\kappa )\)-LCP. Optim. Lett. 9(6), 1105–1119 (2015)MathSciNetCrossRef

23.

Wang, G.Q., Bai, Y.Q.: A new primal-dual path-following interior-point algorithm for semidefinite optimization. J. Math. Anal. Appl. 353(1), 339–349 (2009)MathSciNetCrossRef

24.

Wang, G.Q., Bai, Y.Q.: A primal-dual interior-point algorithm for second-order cone optimization with full nesterov-todd step. Appl. Math. Comput. 215(3), 1047–1061 (2009)MathSciNetCrossRef

25.

Takacs, P.R., Darvay, Z.: A primal-dual interior-point algorithm for symmetric optimization based on a new method for finding search directions. Optimization 67(6), 889–905 (2018)MathSciNetCrossRef

26.

Zhang, L., Xu, Y.H.: A full-newton step interior-point algorithm based on modified newton direction. Oper. Res. Lett. 39(5), 318–322 (2011)MathSciNetCrossRef

27.

Darvay, Z., Takacs, P.R.: New method for determining search directions for interior-point algorithms in linear optimization. Optim. Lett. 12(5), 1099–1116 (2018)MathSciNetCrossRef

28.

Darvay, Z., Papp, I.M., Takacs, P.R.: Complexity analysis of a full-newton step interior-point method for linear optimization. Per. Math. Hungarica 73(1), 27–42 (2016)MathSciNetCrossRef

29.

Darvay, Z., Takacs, P.R.: New interior-point algorithm for symmetric optimization based on a positive-asymptotic barrier function. Tech. Rep. Oper. Res. Report, Univ. of Sciences, Budapest (2016)

30.

Lee, Y.H., Cho, Y.Y., Cho, G.M.: Interior-point algorithms for \(P_{*}(\kappa )\)-LCP based on a new class of kernel functions. J. Glob. Optim. 58(1), 137–149 (2013)CrossRef

31.

Harker, P.T., Pang, J.S.: A damped Newton method for linear complementarity problem. Lect. Appl. Math. 26(1), 265–284 (1990)MathSciNetMATH

32.

Cho, G.M.: A new large-update interior point algorithm for \(P_{*}(\kappa )\) linear complementarity problems. Appl. Math. Comput. 216(1), 265–278 (2006)CrossRef

Titel: A new full-Newton step interior-point method for -LCP based on a positive-asymptotic kernel function
verfasst von: Mingwang Zhang
Kun Huang
Mengmeng Li
Yanli Lv
Publikationsdatum: 11.05.2020
Verlag: Springer Berlin Heidelberg
Erschienen in: Journal of Applied Mathematics and Computing / Ausgabe 1-2/2020
Print ISSN: 1598-5865
Elektronische ISSN: 1865-2085
DOI: https://doi.org/10.1007/s12190-020-01356-1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 1-2/2020

Optimal binary and ternary linear codes with hull dimension one

On a population model with Allee effects and environmental perturbations

SDFEM for singularly perturbed boundary-value problems with two parameters

Long time behavior of stochastic Lotka–Volterra competitive system with general Lévy jumps

Symmetry and two symmetry measures for the web and spider web graphs

NSFD scheme and dynamic consistency of a delayed diffusive humoral immunity viral infection model