Article
| Title: | Inexact Newton-type method for solving large-scale absolute value equation $Ax-|x| = b$ (English) |
| Author: | Tang, Jingyong |
| Language: | English |
| Journal: | Applications of Mathematics |
| ISSN: | 0862-7940 (print) |
| ISSN: | 1572-9109 (online) |
| Volume: | 69 |
| Issue: | 1 |
| Year: | 2024 |
| Pages: | 49-66 |
| Summary lang: | English |
| . | |
| Category: | math |
| . | |
| Summary: | 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. (English) |
| Keyword: | absolute value equation |
| Keyword: | inexact Newton method |
| Keyword: | regularity of interval matrices |
| Keyword: | superlinear convergence |
| MSC: | 90C05 |
| MSC: | 90C33 |
| DOI: | 10.21136/AM.2023.0171-22 |
| . | |
| Date available: | 2024-02-26T10:55:10Z |
| Last updated: | 2024-03-04 |
| Stable URL: | http://hdl.handle.net/10338.dmlcz/152252 |
| . | |
| Reference: | [1] Arias, C. A., Martínez, H. J., Pérez, R.: Global inexact quasi-Newton method for nonlinear system of equations with constraints.Appl. Numer. Math. 150 (2020), 559-575. Zbl 1434.65073, MR 4046472, 10.1016/j.apnum.2019.11.002 |
| Reference: | [2] Caccetta, L., Qu, B., Zhou, G.: A globally and quadratically convergent method for absolute value equations.Comput. Optim. Appl. 48 (2011), 45-58. Zbl 1230.90195, MR 2762957, 10.1007/s10589-009-9242-9 |
| Reference: | [3] Chen, C., Yu, D., Han, D.: Exact and inexact Douglas-Rachford splitting methods for solving large-scale sparse absolute value equations.IMA J. Numer. Anal. 43 (2023), 1036-1060. Zbl 07673881, MR 4568439, 10.1093/imanum/drab105 |
| Reference: | [4] Haghani, F. K.: On generalized Traub's method for absolute value equations.J. Optim. Theory Appl. 166 (2015), 619-625. Zbl 1391.65106, MR 3371392, 10.1007/s10957-015-0712-1 |
| Reference: | [5] Iqbal, J., Iqbal, A., Arif, M.: Levenberg-Marquardt method for solving systems of absolute value equations.J. Comput. Appl. Math. 282 (2015), 134-138. Zbl 1309.65057, MR 3313095, 10.1016/j.cam.2014.11.062 |
| Reference: | [6] Jiang, X., Zhang, Y.: A smoothing-type algorithm for absolute value equations.J. Ind. Manag. Optim. 9 (2013), 789-798. Zbl 1281.90023, MR 3119087, 10.3934/jimo.2013.9.789 |
| Reference: | [7] Kumar, S., Deepmala: A note on unique solvability of the generalized absolute value matrix equation.Natl. Acad. Sci. Lett. 46 (2023), 129-131. MR 4565846, 10.1007/s40009-022-01193-9 |
| Reference: | [8] Kumar, S., Deepmala: The unique solvability conditions for a new class of absolute value equation.(to appear) in Yugosl. J. Oper. Res. MR 4633526, 10.2298/YJOR220515036K |
| Reference: | [9] Li, D., Fukushima, M.: A derivative-free line search and global convergence of Broyden-like method for nonlinear equations.Optim. Methods Softw. 13 (2000), 181-201. Zbl 0960.65076, MR 1785195, 10.1080/10556780008805782 |
| Reference: | [10] Mangasarian, O. L.: A generalized Newton method for absolute value equations.Optim. Lett. 3 (2009), 101-108. Zbl 1154.90599, MR 2453508, 10.1007/s11590-008-0094-5 |
| Reference: | [11] Mangasarian, O. L.: Primal-dual bilinear programming solution of the absolute value equation.Optim. Lett. 6 (2012), 1527-1533. Zbl 1259.90065, MR 2980561, 10.1007/s11590-011-0347-6 |
| Reference: | [12] Mangasarian, O. L.: A hybrid algorithm for solving the absolute value equation.Optim. Lett. 9 (2015), 1469-1474. Zbl 1332.90215, MR 3396552, 10.1007/s11590-015-0893-4 |
| Reference: | [13] Mangasarian, O. L., Meyer, R. R.: Absolute value equations.Linear Algebra Appl. 419 (2006), 359-367. Zbl 1172.15302, MR 2277975, 10.1016/j.laa.2006.05.004 |
| Reference: | [14] Ni, T., Gu, W.-Z., Zhai, J.: An inexact smoothing-type algorithm for support vector machines.Neurocomputing 129 (2014), 127-135. 10.1016/j.neucom.2013.09.047 |
| Reference: | [15] Noor, M. A., Iqbal, J., Noor, K. I., Al-Said, E.: On an iterative method for solving absolute value equations.Optim. Lett. 6 (2012), 1027-1033. Zbl 1254.90149, MR 2925637, 10.1007/s11590-011-0332-0 |
| Reference: | [16] Qi, L., Sun, D., Zhou, G.: A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities.Math. Program. 87 (2000), 1-35. Zbl 0989.90124, MR 1734657, 10.1007/s101079900127 |
| Reference: | [17] Qi, L., Sun, J.: A nonsmooth version of Newton's method.Math. Program. 58 (1993), 353-367. Zbl 0780.90090, MR 1216791, 10.1007/BF01581275 |
| Reference: | [18] Rex, G., Rohn, J.: Sufficient conditions for regularity and singularity of interval matrices.SIAM J. Matrix Anal. Appl. 20 (1998), 437-445. Zbl 0924.15003, MR 1651396, 10.1137/S0895479896310743 |
| Reference: | [19] Rohn, J.: Systems of linear interval equations.Linear Algebra Appl. 126 (1989), 39-78. Zbl 0712.65029, MR 1040771, 10.1016/0024-3795(89)90004-9 |
| Reference: | [20] Rohn, J.: An algorithm for computing all solutions of an absolute value equation.Optim. Lett. 6 (2012), 851-856. Zbl 1254.90260, MR 2925621, 10.1007/s11590-011-0305-3 |
| Reference: | [21] Saheya, B., Yu, C.-H., Chen, J.-S.: Numerical comparisons based on four smoothing functions for absolute value equation.J. Appl. Math. Comput. 56 (2018), 131-149. Zbl 1390.26020, MR 3770379, 10.1007/s12190-016-1065-0 |
| Reference: | [22] Tang, J., Zhou, J.: A quadratically convergent descent method for the absolute value equation $Ax+B|x|=b$.Oper. Res. Lett. 47 (2019), 229-234. Zbl 1476.65077, MR 3937799, 10.1016/j.orl.2019.03.014 |
| Reference: | [23] Tang, J., Zhou, J., Zhang, H.: An accelerated smoothing Newton method with cubic convergence for weighted complementarity problems.J. Optim. Theory Appl. 196 (2023), 641-665. Zbl 07675403, MR 4548588, 10.1007/s10957-022-02152-6 |
| Reference: | [24] Wang, A., Wang, H., Deng, Y.: Interval algorithm for absolute value equations.Cent. Eur. J. Math. 9 (2011), 1171-1184. Zbl 1236.65047, MR 2824456, 10.2478/s11533-011-0067-2 |
| Reference: | [25] Wu, S.-L.: The unique solution of a class of the new generalized absolute value equation.Appl. Math. Lett. 116 (2021), Article ID 107029, 6 pages. Zbl 1469.15019, MR 4205122, 10.1016/j.aml.2021.107029 |
| Reference: | [26] Yu, D., Chen, C., Han, D.: An inexact framework of the Newton-based matrix splitting iterative method for the generalized absolute value equation.Available at https://arxiv.org/abs/2103.10129 (2022), 15 pages. 10.48550/arXiv.2103.10129 |
| Reference: | [27] Zhang, C., Wei, Q. J.: Global and finite convergence of a generalized Newton method for absolute value equations.J. Optim. Theory Appl. 143 (2009), 391-403. Zbl 1175.90418, MR 2545959, 10.1007/s10957-009-9557-9 |
| Reference: | [28] Zhang, H., Hager, W. W.: A nonmonotone line search technique and its application to unconstrained optimization.SIAM. J. Optim. 14 (2004), 1043-1056. Zbl 1073.90024, MR 2112963, 10.1137/S1052623403428208 |
| Reference: | [29] Zhang, J.-J.: The relaxed nonlinear PHSS-like iteration method for absolute value equations.Appl. Math. Comput. 265 (2015), 266-274. Zbl 1410.90224, MR 3373480, 10.1016/j.amc.2015.05.018 |
| Reference: | [30] Zhou, H., Wu, S.: On the unique solution of a class of absolute value equations $Ax-B|Cx|=d$.AIMS Math. 6 (2021), 8912-8919. Zbl 1485.90065, MR 4281108, 10.3934/math.2021517 |
| . |
Fulltext not available (moving wall 24 months)
Search
Partner of
