Top

previous article A multiresolution algorithm to generate images ...

next article Preconditioners and their analyses for edge ele...

Hint

Swipe to navigate through the articles of this issue

14-03-2020 | Original Paper | Issue 1/2021

Convergence analysis on matrix splitting iteration algorithm for semidefinite linear complementarity problems

Journal:: Numerical Algorithms > Issue 1/2021

Author:: Yi-Fen Ke

» Get access to the full-text

Important notes

Publisher’s note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Abstract

In this paper, we present some novel observations for the semidefinite linear complementarity problems, abbreviated as SDLCPs. Based on these new results, we establish the modulus-based matrix splitting iteration methods, which are obtained by reformulating equivalently SDLCP as an implicit fixed-point matrix equation. The convergence of the proposed modulus-based matrix splitting iteration methods has been analyzed. Numerical experiments have shown that the modulus-based iteration methods are effective for solving SDLCPs.

Please log in to get access to this content

To get access to this content you need the following product:

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 30 Tage kostenlos.

inform now

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 + Umwelt
Maschinenbau + Werkstoffe

Testen Sie jetzt 30 Tage kostenlos.

inform now

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 + Umwelt
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

inform now

Alizadeh, F.: Interior point methods in semidefinite programming with application to combinatorial optimization. SIAM J. Optim. 5(1), 13–51 (1995) MathSciNetMATHCrossRef

Bai, Z. -Z.: Modulus-based matrix splitting iteration methods for linear complementarity problems. Numer. Linear Algebra Appl. 17, 917–933 (2010) MathSciNetMATHCrossRef

Bai, Z. -Z., Zhang, L. -L.: Modulus-based synchronous multisplitting iteration methods for linear complementarity problems. Numer. Algor. 62(1), 100–112 (2013) MathSciNetMATHCrossRef

Bai, Z. -Z., Zhang, L. -L.: Modulus-based synchronous two-stage multisplitting iteration methods for linear complementarity problems. Numer. Algor. 62(1), 59–77 (2013) MathSciNetMATHCrossRef

Benner, P., Bollhöfer, M., Kressner, D., Mehl, C., Stykel, T.: Numerical Algebra, Matrix Theory, Differential-Algebraic Equations and Control Theory. Springer International Publishing (2015)

Chen, X., Qi, H. -D.: Cartesian P-property and its applications to the semidefinite linear complementarity problem. Math. Program. 106(1), 177–201 (2006) MathSciNetMATHCrossRef

Chen, X., Tseng, P.: Non-interior continuation methods for solving semidefinite complementarity problems. Math. Program. 95(3), 431–474 (2003) MathSciNetMATHCrossRef

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

Davis, T.: University of Florida Sparse Matrix Collection, University of Florida, Gainesville. http://www.cise.ufl.edu/research/sparse/matrices/

10.

Ding, F., Liu, P. -X., Ding, J.: Iterative solutions of the generalized Sylvester matrix equations by using the hierarchical identification principle. Appl. Math. Comput. 197(1), 41–50 (2008) MathSciNetMATH

11.

Dong, J. -L., Jiang, M. -Q.: A modified modulus method for symmetric positive-definite linear complementarity problems. Numer. Linear Algebra Appl. 16, 129–143 (2009) MathSciNetMATHCrossRef

12.

Ferris, M. C., Pang, J. -S.: Engineering and economic applications of complementarity problems. SIAM Rev. 39(4), 669–713 (1997) MathSciNetMATHCrossRef

13.

Gowda, M. S., Parthasarathy, T.: Complementarity forms of theorems of Lyapunov and Stein, and related results. Linear. Algebra. Appl. 320(1-3), 131–144 (2000) MathSciNetMATHCrossRef

14.

Fukushima, M., Luo, Z. -Q., Tseng, P.: Smoothing functions for second-order-cone complementarity problems. SIAMJ. Optim. 12(2), 436–460 (2015) MathSciNetMATHCrossRef

15.

Gajic, Z., Qureshi, M. T. J.: Lyapunov Matrix Equation in System Stability and Control. Dover Publication, Inc, Mineola (2008)

16.

Gowda, M. S., Song, Y.: On semidefinite linear complementarity problems. Math. Program. 88(3), 575–587 (2000) MathSciNetMATHCrossRef

17.

Gowda, M. S., Song, Y.: Some new results for the semidefinite linear complementarity problem. SIAM J. Matrix Anal. Appl. 24(1), 25–39 (2002) MathSciNetMATHCrossRef

18.

Gowda, M. S., Song, Y., Ravindran, G.: On some interconnections between strict monotonicity, globally uniquely solvable, and P properties in semidefinite linear complementarity problems. Linear. Algebra. Appl. 370(1), 355–368 (2003) MathSciNetMATHCrossRef

19.

Hadjidimos, A., Lapidakis, M., Tzoumas, M.: On iterative solution for linear complementarity problem with an H ₊-matrix. SIAM J. Matrix Anal. Appl. 33(1), 97–110 (2012) MathSciNetMATHCrossRef

20.

Hu, S. -L., Huang, Z. -H., Wang, P.: A nonmonotone smoothing Newton algorithm for solving nonlinear complementarity problems. Optim. Methods Softw. 24(3), 447–460 (2009) MathSciNetMATHCrossRef

21.

Hu, D. -Y., Reichel, L.: Krylov-subspace methods for the Sylvester equation. Linear Algebra Appl. 172, 283–313 (1992) MathSciNetMATHCrossRef

22.

Kanzow, C., Nagel, C.: Semidefinite programs: New search directions, smoothing-type methods, and numerical results. SIAM J. Optim. 13(1), 1–23 (2002) MathSciNetMATHCrossRef

23.

Ke, Y. -F.: The new iteration algorithm for absolute value equation. Appl. Math. Lett. 99, 105990 (2020) MathSciNetMATHCrossRef

24.

Ke, Y. -F., Ma, C. -F.: On the convergence analysis of two-step modulus-based matrix splitting iteration method for linear complementarity problems. Appl. Math. Comput. 243, 413–418 (2014) MathSciNetMATH

25.

Ke, Y. -F., Ma, C. -F.: A preconditioned nested splitting conjugate gradient iterative method for the large sparse generalized Sylvester equation. Comput. Math. Appl. 68, 1409–1420 (2014) MathSciNetMATHCrossRef

26.

Ke, Y. -F., Ma, C. -F.: SOR-Like iteration method for solving absolute value equations. Appl. Math. Comput. 311, 195–202 (2017) MathSciNetMATH

27.

Ke, Y. -F., Ma, C. -F., Zhang, H.: The modulus-based matrix splitting iteration methods for second-order cone linear complementarity problems. Numer. Algor. 79(4), 1283–1303 (2018) MathSciNetMATHCrossRef

28.

Ke, Y. -F., Ma, C. -F., Zhang, H.: The relaxation modulus-based matrix splitting iteration methods for circular cone nonlinear complementarity problems. Comput. Appl. Math. 37, 6795–6820 (2018) MathSciNetMATHCrossRef

29.

Kojima, M., Shindoh, S., Hara, S.: Interior-point methods for the monotone semidefinite linear complementarity problems. SIAM J. Optim. 7(1), 86–125 (1997) MathSciNetMATHCrossRef

30.

Liu, S. -M., Zheng, H., Li, W.: A general accelerated modulus-based matrix splitting iteration method for solving linear complementarity problems. Calcolo 53 (2), 189–199 (2016) MathSciNetMATHCrossRef

31.

Lu, Q. -Q., Li, C. -L.: Modulus-based matrix splitting iteration methods for a class of stochastic linear complementarity problem. American. J. Oper. Res. 9, 245–254 (2019) MathSciNet

32.

Mitra, S. K.: The matrix equation A X B + C X D = E. SIAM J. Appl. Math. 32(4), 823–825 (1977) MathSciNetMATHCrossRef

33.

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

34.

Overton, M., Wolkowicz, H.: Semidefinite programming. Math. Program. 77, 97–320 (1997) MathSciNetMATH

35.

Shida, M., Shindoh, S., Kojima, M.: Existence and uniqueness of search directions in interior-point algorithms for the SDP and the monotone SDLCP. SIAM J. Optim. 8(2), 387–396 (1998) MathSciNetMATHCrossRef

36.

Sim, C. -K., Zhao, G.: Underlying paths in interior point methods for the monotone semidefinite linear complementarity problem. Math. Program. 110(3), 475–499 (2007) MathSciNetMATHCrossRef

37.

Sun, D. -F.: The strong second-order sufficient condition and constraint nondegeneracy in nonlinear semidefinite programming and their implications. Math. Oper. Res. 31(4), 761–776 (2006) MathSciNetMATHCrossRef

38.

Sun, D. -F., Sun, J.: Strong semismoothness of the Fischer-Burmeister SDC and SOC complementarity functions. Math. Program. 103(3), 575–581 (2005) MathSciNetMATHCrossRef

39.

Tseng, P.: Merit functions for semi-definite complementarity problems. Math. Program. 83(1-3), 159–185 (1998) MathSciNetMATHCrossRef

40.

Vandenberghe, L., Boyd, S.: Semidefinite programming. SIAM Rev. 38, 49–95 (1996) MathSciNetMATHCrossRef

41.

Yamashita, N., Fukushima, M.: A New Merit Function and a Descent Method for Semidefinite Complementarity Problems. In: Reformulation: Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods, pp. 405–420. Springer (1999)

42.

Zhang, L. -P.: A global linear and local quadratic single-tep noninterior continuation method for monotone semidefinite complementarity problems. Acta Math. Sci. 27(2), 243–253 (2007) MathSciNetMATHCrossRef

43.

Zhang, L. -L.: Two-step modulus-based matrix splitting iteration method for linear complementarity problems. Numer. Algor. 57(1), 83–99 (2011) MathSciNetMATHCrossRef

44.

Zhang, L. -L., Ren, Z. -R.: Improved convergence theorems of modulus-based matrix splitting iteration methods for linear complementarity problems. Appl. Math. Lett. 26(6), 638–642 (2013) MathSciNetMATHCrossRef

45.

Zhang, K. -Y., Xu, Z.: Numerical Algebra, 2nd edn. Science Press, Beijing (2006)

46.

Zheng, N., Yin, J. -F.: Accelerated modulus-based matrix splitting iteration methods for linear complementarity problem. Numer. Algor. 64(2), 245–262 (2013) MathSciNetMATHCrossRef

47.

Zheng, N., Yin, J. -F.: Convergence of accelerated modulus-based matrix splitting iteration methods for linear complementarity problem with an H ₊-matrix. J. Comput. Appl. Math. 260(2), 281–293 (2014) MathSciNetMATHCrossRef

Title: Convergence analysis on matrix splitting iteration algorithm for semidefinite linear complementarity problems
Author:: Yi-Fen Ke
Publication date: 14-03-2020
DOI: https://doi.org/10.1007/s11075-020-00888-8
Publisher: Springer US
Journal: Numerical Algorithms
Issue 1/2021
Print ISSN: 1017-1398
Electronic ISSN: 1572-9265

Premium Partner

Image Credits

Springer Professional

Hint

Swipe to navigate through the articles of this issue

Publisher’s note

Abstract

Please log in to get access to this content

To get access to this content you need the following product:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Other articles of this Issue 1/2021

Subgradient projection methods extended to monotone bilevel equilibrium problems in Hilbert spaces

A numerically efficient variational algorithm to solve a fractional nonlinear elastic string equation

Switching preconditioners using a hybrid approach for linear systems arising from interior point methods for linear programming

Recovery type a posteriori error estimates for the conduction convection problem

Projection extragradient algorithms for solving nonmonotone and non-Lipschitzian equilibrium problems in Hilbert spaces

A Riemannian derivative-free Polak–Ribiére–Polyak method for tangent vector field

Premium Partner