Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Journal of Applied Mathematics and Computing
Published in: Journal of Applied Mathematics and Computing 1-2/2020

11-05-2020 | Original Research

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

Authors: Mingwang Zhang, Kun Huang, Mengmeng Li, Yanli Lv

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

Log in

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

search-config
loading …

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.
previous article Explicit solutions for distributed, boundary and distributed-boundary elliptic optimal control problems
next article Mathematical analysis and optimal control applied to the treatment of leukemia

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
Literature
1.
2.
Roos, C., Terlaky, T., Vial, J-Ph: Theory and Algorithms for Linear Optimization: An Interior Point Approach. Wiley, Chichester (1997)MATH
3.
Wright, S.J.: Primal-Dual Interior-Point Methods. SIAM, Philadelphia (1997)CrossRef
4.
Cottle, R.W., Pang, J.S., Stone, R.E.: The Linear Complementarity Problem. Academic Press, New York (1992)MATH
5.
Roos, C., Vial, J-Ph: A polynomial method of approximate centers for linear programming. Math. Program. 54(1–3), 295–305 (1992)MathSciNetCrossRef
6.
NeterrovR, E., Nemirovskii, A.S.: Interior-Point Ploynomial Methods in Convex Programming. SIAM, Philadelphia (1994)
7.
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
8.
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
9.
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
Metadata
Title
A new full-Newton step interior-point method for -LCP based on a positive-asymptotic kernel function
Authors
Mingwang Zhang
Kun Huang
Mengmeng Li
Yanli Lv
Publication date
11-05-2020
Publisher
Springer Berlin Heidelberg
Published in
Journal of Applied Mathematics and Computing / Issue 1-2/2020
Print ISSN: 1598-5865
Electronic ISSN: 1865-2085
DOI
https://doi.org/10.1007/s12190-020-01356-1

Other articles of this Issue 1-2/2020

Journal of Applied Mathematics and Computing 1-2/2020 Go to the issue

Original Research

Algorithmic aspects of Roman domination in graphs

Original Research

Optimal binary codes derived from -additive cyclic codes

Original Research

Optimal binary and ternary linear codes with hull dimension one

Original Research

On existence, uniqueness and Ulam’s stability results for boundary value problems of fractional iterative integrodifferential equations

Original Research

Stability of a delayed competitive model with saturation effect and interval biological parameters

Original Research

Hopf and forward bifurcation of an integer and fractional-order SIR epidemic model with logistic growth of the susceptible individuals

Premium Partner

    Image Credits