Article
Full entry | Fulltext not available
(moving wall
24 months)
Feedback
Keywords:
absolute value equation; inexact Newton method; regularity of interval matrices; superlinear convergence
absolute value equation; inexact Newton method; regularity of interval matrices; superlinear convergence
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.
References:
[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. DOI 10.1016/j.apnum.2019.11.002 | MR 4046472 | Zbl 1434.65073
[2] Caccetta, L., Qu, B., Zhou, G.: A globally and quadratically convergent method for absolute value equations. Comput. Optim. Appl. 48 (2011), 45-58. DOI 10.1007/s10589-009-9242-9 | MR 2762957 | Zbl 1230.90195
[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. DOI 10.1093/imanum/drab105 | MR 4568439 | Zbl 07673881
[4] Haghani, F. K.: On generalized Traub's method for absolute value equations. J. Optim. Theory Appl. 166 (2015), 619-625. DOI 10.1007/s10957-015-0712-1 | MR 3371392 | Zbl 1391.65106
[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. DOI 10.1016/j.cam.2014.11.062 | MR 3313095 | Zbl 1309.65057
[6] Jiang, X., Zhang, Y.: A smoothing-type algorithm for absolute value equations. J. Ind. Manag. Optim. 9 (2013), 789-798. DOI 10.3934/jimo.2013.9.789 | MR 3119087 | Zbl 1281.90023
[7] Kumar, S., Deepmala: A note on unique solvability of the generalized absolute value matrix equation. Natl. Acad. Sci. Lett. 46 (2023), 129-131. DOI 10.1007/s40009-022-01193-9 | MR 4565846
[8] Kumar, S., Deepmala: The unique solvability conditions for a new class of absolute value equation. (to appear) in Yugosl. J. Oper. Res. DOI 10.2298/YJOR220515036K | MR 4633526
[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. DOI 10.1080/10556780008805782 | MR 1785195 | Zbl 0960.65076
[10] Mangasarian, O. L.: A generalized Newton method for absolute value equations. Optim. Lett. 3 (2009), 101-108. DOI 10.1007/s11590-008-0094-5 | MR 2453508 | Zbl 1154.90599
[11] Mangasarian, O. L.: Primal-dual bilinear programming solution of the absolute value equation. Optim. Lett. 6 (2012), 1527-1533. DOI 10.1007/s11590-011-0347-6 | MR 2980561 | Zbl 1259.90065
[12] Mangasarian, O. L.: A hybrid algorithm for solving the absolute value equation. Optim. Lett. 9 (2015), 1469-1474. DOI 10.1007/s11590-015-0893-4 | MR 3396552 | Zbl 1332.90215
[13] Mangasarian, O. L., Meyer, R. R.: Absolute value equations. Linear Algebra Appl. 419 (2006), 359-367. DOI 10.1016/j.laa.2006.05.004 | MR 2277975 | Zbl 1172.15302
[14] Ni, T., Gu, W.-Z., Zhai, J.: An inexact smoothing-type algorithm for support vector machines. Neurocomputing 129 (2014), 127-135. DOI 10.1016/j.neucom.2013.09.047
[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. DOI 10.1007/s11590-011-0332-0 | MR 2925637 | Zbl 1254.90149
[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. DOI 10.1007/s101079900127 | MR 1734657 | Zbl 0989.90124
[17] Qi, L., Sun, J.: A nonsmooth version of Newton's method. Math. Program. 58 (1993), 353-367. DOI 10.1007/BF01581275 | MR 1216791 | Zbl 0780.90090
[18] Rex, G., Rohn, J.: Sufficient conditions for regularity and singularity of interval matrices. SIAM J. Matrix Anal. Appl. 20 (1998), 437-445. DOI 10.1137/S0895479896310743 | MR 1651396 | Zbl 0924.15003
[19] Rohn, J.: Systems of linear interval equations. Linear Algebra Appl. 126 (1989), 39-78. DOI 10.1016/0024-3795(89)90004-9 | MR 1040771 | Zbl 0712.65029
[20] Rohn, J.: An algorithm for computing all solutions of an absolute value equation. Optim. Lett. 6 (2012), 851-856. DOI 10.1007/s11590-011-0305-3 | MR 2925621 | Zbl 1254.90260
[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. DOI 10.1007/s12190-016-1065-0 | MR 3770379 | Zbl 1390.26020
[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. DOI 10.1016/j.orl.2019.03.014 | MR 3937799 | Zbl 1476.65077
[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. DOI 10.1007/s10957-022-02152-6 | MR 4548588 | Zbl 07675403
[24] Wang, A., Wang, H., Deng, Y.: Interval algorithm for absolute value equations. Cent. Eur. J. Math. 9 (2011), 1171-1184. DOI 10.2478/s11533-011-0067-2 | MR 2824456 | Zbl 1236.65047
[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. DOI 10.1016/j.aml.2021.107029 | MR 4205122 | Zbl 1469.15019
[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. DOI 10.48550/arXiv.2103.10129
[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. DOI 10.1007/s10957-009-9557-9 | MR 2545959 | Zbl 1175.90418
[28] Zhang, H., Hager, W. W.: A nonmonotone line search technique and its application to unconstrained optimization. SIAM. J. Optim. 14 (2004), 1043-1056. DOI 10.1137/S1052623403428208 | MR 2112963 | Zbl 1073.90024
[29] Zhang, J.-J.: The relaxed nonlinear PHSS-like iteration method for absolute value equations. Appl. Math. Comput. 265 (2015), 266-274. DOI 10.1016/j.amc.2015.05.018 | MR 3373480 | Zbl 1410.90224
[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. DOI 10.3934/math.2021517 | MR 4281108 | Zbl 1485.90065
Search
Partner of
