Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

Erschienen 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

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

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

Einloggen, um Zugang zu erhalten
share
TEILEN

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.

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

  • über 69.000 Bücher
  • über 500 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

Testen Sie jetzt 15 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

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




Testen Sie jetzt 15 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

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




Testen Sie jetzt 15 Tage kostenlos.

Literatur
1.
2.
Zurück zum Zitat Roos, C., Terlaky, T., Vial, J-Ph: Theory and Algorithms for Linear Optimization: An Interior Point Approach. Wiley, Chichester (1997) MATH Roos, C., Terlaky, T., Vial, J-Ph: Theory and Algorithms for Linear Optimization: An Interior Point Approach. Wiley, Chichester (1997) MATH
3.
Zurück zum Zitat Wright, S.J.: Primal-Dual Interior-Point Methods. SIAM, Philadelphia (1997) CrossRef Wright, S.J.: Primal-Dual Interior-Point Methods. SIAM, Philadelphia (1997) CrossRef
4.
Zurück zum Zitat Cottle, R.W., Pang, J.S., Stone, R.E.: The Linear Complementarity Problem. Academic Press, New York (1992) MATH Cottle, R.W., Pang, J.S., Stone, R.E.: The Linear Complementarity Problem. Academic Press, New York (1992) MATH
5.
Zurück zum Zitat Roos, C., Vial, J-Ph: A polynomial method of approximate centers for linear programming. Math. Program. 54(1–3), 295–305 (1992) MathSciNetCrossRef Roos, C., Vial, J-Ph: A polynomial method of approximate centers for linear programming. Math. Program. 54(1–3), 295–305 (1992) MathSciNetCrossRef
6.
Zurück zum Zitat NeterrovR, E., Nemirovskii, A.S.: Interior-Point Ploynomial Methods in Convex Programming. SIAM, Philadelphia (1994) NeterrovR, E., Nemirovskii, A.S.: Interior-Point Ploynomial Methods in Convex Programming. SIAM, Philadelphia (1994)
7.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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) 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat Illes, T., Nagy, M., Terlaky, T.: Ep theorem for dual linear complementarity problems. J. Optim. Theory Appl. 140(2), 233–238 (2009) MathSciNetCrossRef Illes, T., Nagy, M., Terlaky, T.: Ep theorem for dual linear complementarity problems. J. Optim. Theory Appl. 140(2), 233–238 (2009) MathSciNetCrossRef
12.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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) 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat Darvay, Z.: A new algorithm for solving self-dual linear optimization problems. Studia Univ. Babe s-Bolyai Ser. Informatica 47, 15–26 (2002) MathSciNetMATH 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.
Zurück zum Zitat Darvay, Z.: New interior-point algorithms in linear programming. Adv. Model. Optim. 5(1), 51–92 (2003) MathSciNetMATH Darvay, Z.: New interior-point algorithms in linear programming. Adv. Model. Optim. 5(1), 51–92 (2003) MathSciNetMATH
20.
Zurück zum Zitat Achache, M.: A new primal-dual path-following method for convex quadratic programming. Comput. Appl. Math. 25(1), 97–110 (2006) MathSciNetCrossRef Achache, M.: A new primal-dual path-following method for convex quadratic programming. Comput. Appl. Math. 25(1), 97–110 (2006) MathSciNetCrossRef
21.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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) 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat Harker, P.T., Pang, J.S.: A damped Newton method for linear complementarity problem. Lect. Appl. Math. 26(1), 265–284 (1990) MathSciNetMATH Harker, P.T., Pang, J.S.: A damped Newton method for linear complementarity problem. Lect. Appl. Math. 26(1), 265–284 (1990) MathSciNetMATH
32.
Zurück zum Zitat 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 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
Metadaten
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

Weitere Artikel der Ausgabe 1-2/2020

Journal of Applied Mathematics and Computing 1-2/2020 Zur Ausgabe

Premium Partner