Inexact Newton-type method for solving large-scale absolute value equation A x - | x | = b

Jingyong Tang

Applications of Mathematics (2024)

  • Volume: 69, Issue: 1, page 49-66
  • ISSN: 0862-7940

Abstract

top
Newton-type methods have been successfully applied to solve the absolute value equation A x - | x | = b (denoted by AVE). This class of methods usually solves a system of linear equations exactly in each iteration. However, for large-scale AVEs, solving the corresponding system exactly may be expensive. In this paper, we propose an inexact Newton-type method for solving the AVE. In each iteration, the proposed method solves the corresponding system only approximately. Moreover, it adopts a new line search technique, which is well-defined and easy to implement. We prove that the proposed method has global and local superlinear convergence under the condition that the interval matrix [ A - I , A + I ] is regular. This condition is much weaker than those used in some Newton-type methods. Numerical results show that our method has fairly good practical efficiency for solving large-scale AVEs.

How to cite

top

Tang, Jingyong. "Inexact Newton-type method for solving large-scale absolute value equation $Ax-|x| = b$." Applications of Mathematics 69.1 (2024): 49-66. <http://eudml.org/doc/299200>.

@article{Tang2024,
abstract = {Newton-type methods have been successfully applied to solve the absolute value equation $Ax-|x| = b$ (denoted by AVE). This class of methods usually solves a system of linear equations exactly in each iteration. However, for large-scale AVEs, solving the corresponding system exactly may be expensive. In this paper, we propose an inexact Newton-type method for solving the AVE. In each iteration, the proposed method solves the corresponding system only approximately. Moreover, it adopts a new line search technique, which is well-defined and easy to implement. We prove that the proposed method has global and local superlinear convergence under the condition that the interval matrix $[A - I,A + I]$ is regular. This condition is much weaker than those used in some Newton-type methods. Numerical results show that our method has fairly good practical efficiency for solving large-scale AVEs.},
author = {Tang, Jingyong},
journal = {Applications of Mathematics},
keywords = {absolute value equation; inexact Newton method; regularity of interval matrices; superlinear convergence},
language = {eng},
number = {1},
pages = {49-66},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Inexact Newton-type method for solving large-scale absolute value equation $Ax-|x| = b$},
url = {http://eudml.org/doc/299200},
volume = {69},
year = {2024},
}

TY - JOUR
AU - Tang, Jingyong
TI - Inexact Newton-type method for solving large-scale absolute value equation $Ax-|x| = b$
JO - Applications of Mathematics
PY - 2024
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 69
IS - 1
SP - 49
EP - 66
AB - Newton-type methods have been successfully applied to solve the absolute value equation $Ax-|x| = b$ (denoted by AVE). This class of methods usually solves a system of linear equations exactly in each iteration. However, for large-scale AVEs, solving the corresponding system exactly may be expensive. In this paper, we propose an inexact Newton-type method for solving the AVE. In each iteration, the proposed method solves the corresponding system only approximately. Moreover, it adopts a new line search technique, which is well-defined and easy to implement. We prove that the proposed method has global and local superlinear convergence under the condition that the interval matrix $[A - I,A + I]$ is regular. This condition is much weaker than those used in some Newton-type methods. Numerical results show that our method has fairly good practical efficiency for solving large-scale AVEs.
LA - eng
KW - absolute value equation; inexact Newton method; regularity of interval matrices; superlinear convergence
UR - http://eudml.org/doc/299200
ER -

References

top
  1. Arias, C. A., Martínez, H. J., Pérez, R., 10.1016/j.apnum.2019.11.002, Appl. Numer. Math. 150 (2020), 559-575. (2020) Zbl1434.65073MR4046472DOI10.1016/j.apnum.2019.11.002
  2. Caccetta, L., Qu, B., Zhou, G., 10.1007/s10589-009-9242-9, Comput. Optim. Appl. 48 (2011), 45-58. (2011) Zbl1230.90195MR2762957DOI10.1007/s10589-009-9242-9
  3. Chen, C., Yu, D., Han, D., 10.1093/imanum/drab105, IMA J. Numer. Anal. 43 (2023), 1036-1060. (2023) Zbl07673881MR4568439DOI10.1093/imanum/drab105
  4. Haghani, F. K., 10.1007/s10957-015-0712-1, J. Optim. Theory Appl. 166 (2015), 619-625. (2015) Zbl1391.65106MR3371392DOI10.1007/s10957-015-0712-1
  5. Iqbal, J., Iqbal, A., Arif, M., 10.1016/j.cam.2014.11.062, J. Comput. Appl. Math. 282 (2015), 134-138. (2015) Zbl1309.65057MR3313095DOI10.1016/j.cam.2014.11.062
  6. Jiang, X., Zhang, Y., 10.3934/jimo.2013.9.789, J. Ind. Manag. Optim. 9 (2013), 789-798. (2013) Zbl1281.90023MR3119087DOI10.3934/jimo.2013.9.789
  7. Kumar, S., Deepmala, 10.1007/s40009-022-01193-9, Natl. Acad. Sci. Lett. 46 (2023), 129-131. (2023) MR4565846DOI10.1007/s40009-022-01193-9
  8. Kumar, S., Deepmala, 10.2298/YJOR220515036K, (to appear) in Yugosl. J. Oper. Res. MR4633526DOI10.2298/YJOR220515036K
  9. Li, D., Fukushima, M., 10.1080/10556780008805782, Optim. Methods Softw. 13 (2000), 181-201. (2000) Zbl0960.65076MR1785195DOI10.1080/10556780008805782
  10. Mangasarian, O. L., 10.1007/s11590-008-0094-5, Optim. Lett. 3 (2009), 101-108. (2009) Zbl1154.90599MR2453508DOI10.1007/s11590-008-0094-5
  11. Mangasarian, O. L., 10.1007/s11590-011-0347-6, Optim. Lett. 6 (2012), 1527-1533. (2012) Zbl1259.90065MR2980561DOI10.1007/s11590-011-0347-6
  12. Mangasarian, O. L., 10.1007/s11590-015-0893-4, Optim. Lett. 9 (2015), 1469-1474. (2015) Zbl1332.90215MR3396552DOI10.1007/s11590-015-0893-4
  13. Mangasarian, O. L., Meyer, R. R., 10.1016/j.laa.2006.05.004, Linear Algebra Appl. 419 (2006), 359-367. (2006) Zbl1172.15302MR2277975DOI10.1016/j.laa.2006.05.004
  14. Ni, T., Gu, W.-Z., Zhai, J., 10.1016/j.neucom.2013.09.047, Neurocomputing 129 (2014), 127-135. (2014) DOI10.1016/j.neucom.2013.09.047
  15. Noor, M. A., Iqbal, J., Noor, K. I., Al-Said, E., 10.1007/s11590-011-0332-0, Optim. Lett. 6 (2012), 1027-1033. (2012) Zbl1254.90149MR2925637DOI10.1007/s11590-011-0332-0
  16. Qi, L., Sun, D., Zhou, G., 10.1007/s101079900127, Math. Program. 87 (2000), 1-35. (2000) Zbl0989.90124MR1734657DOI10.1007/s101079900127
  17. Qi, L., Sun, J., 10.1007/BF01581275, Math. Program. 58 (1993), 353-367. (1993) Zbl0780.90090MR1216791DOI10.1007/BF01581275
  18. Rex, G., Rohn, J., 10.1137/S0895479896310743, SIAM J. Matrix Anal. Appl. 20 (1998), 437-445. (1998) Zbl0924.15003MR1651396DOI10.1137/S0895479896310743
  19. Rohn, J., 10.1016/0024-3795(89)90004-9, Linear Algebra Appl. 126 (1989), 39-78. (1989) Zbl0712.65029MR1040771DOI10.1016/0024-3795(89)90004-9
  20. Rohn, J., 10.1007/s11590-011-0305-3, Optim. Lett. 6 (2012), 851-856. (2012) Zbl1254.90260MR2925621DOI10.1007/s11590-011-0305-3
  21. Saheya, B., Yu, C.-H., Chen, J.-S., 10.1007/s12190-016-1065-0, J. Appl. Math. Comput. 56 (2018), 131-149. (2018) Zbl1390.26020MR3770379DOI10.1007/s12190-016-1065-0
  22. Tang, J., Zhou, J., 10.1016/j.orl.2019.03.014, Oper. Res. Lett. 47 (2019), 229-234. (2019) Zbl1476.65077MR3937799DOI10.1016/j.orl.2019.03.014
  23. Tang, J., Zhou, J., Zhang, H., 10.1007/s10957-022-02152-6, J. Optim. Theory Appl. 196 (2023), 641-665. (2023) Zbl07675403MR4548588DOI10.1007/s10957-022-02152-6
  24. Wang, A., Wang, H., Deng, Y., 10.2478/s11533-011-0067-2, Cent. Eur. J. Math. 9 (2011), 1171-1184. (2011) Zbl1236.65047MR2824456DOI10.2478/s11533-011-0067-2
  25. Wu, S.-L., 10.1016/j.aml.2021.107029, Appl. Math. Lett. 116 (2021), Article ID 107029, 6 pages. (2021) Zbl1469.15019MR4205122DOI10.1016/j.aml.2021.107029
  26. Yu, D., Chen, C., Han, D., 10.48550/arXiv.2103.10129, Available at https://arxiv.org/abs/2103.10129 (2022), 15 pages. (2022) DOI10.48550/arXiv.2103.10129
  27. Zhang, C., Wei, Q. J., 10.1007/s10957-009-9557-9, J. Optim. Theory Appl. 143 (2009), 391-403. (2009) Zbl1175.90418MR2545959DOI10.1007/s10957-009-9557-9
  28. Zhang, H., Hager, W. W., 10.1137/S1052623403428208, SIAM. J. Optim. 14 (2004), 1043-1056. (2004) Zbl1073.90024MR2112963DOI10.1137/S1052623403428208
  29. Zhang, J.-J., 10.1016/j.amc.2015.05.018, Appl. Math. Comput. 265 (2015), 266-274. (2015) Zbl1410.90224MR3373480DOI10.1016/j.amc.2015.05.018
  30. Zhou, H., Wu, S., 10.3934/math.2021517, AIMS Math. 6 (2021), 8912-8919. (2021) Zbl1485.90065MR4281108DOI10.3934/math.2021517

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.