An inexact Douglas-Rachford splitting method for solving absolute value equations

Abstract

The last two decades witnessed the increasing of the interests on the absolute value equations (AVE) of finding $x\in {\mathbb{R}}^n$ such that $Ax-|x|-b=0$, where $A\in {\mathbb{R}}^{n\times n}$ and $b\in {\mathbb{R}}^n$. In this paper, we pay our attention on designing efficient algorithms. To this end, we reformulate AVE to a generalized linear complementarity problem (GLCP), which, among the equivalent forms, is the most economical one in the sense that it does not increase the dimension of the variables. For solving the GLCP, we propose an inexact Douglas-Rachford splitting method which can adopt a relative error tolerance. As a consequence, in the inner iteration processes, we can employ the LSQR method ([C.C. Paige and M.A. Saunders, ACM Trans. Mathe. Softw. (TOMS), 8 (1982), pp. 43--71]) to find a qualified approximate solution for each subproblem, which makes the cost per iteration very low. We prove the convergence of the algorithm and establish its global linear rate of convergence. Comparing results with the popular algorithms such as the exact generalized Newton method [O.L. Mangasarian, Optim. Lett., 1 (2007), pp. 3--8], the inexact semi-smooth Newton method [J.Y.B. Cruz, O.P. Ferreira and L.F. Prudente, Comput. Optim. Appl., 65 (2016), pp. 93--108] and the exact SOR-like method [Y.-F. Ke and C.-F. Ma, Appl. Math. Comput., 311 (2017), pp. 195--202] are reported, which indicate that the proposed algorithm is very promising. Moreover, our method also extends the range of numerically solvable of the AVE; that is, it can deal with not only the case that $\Vert A^{-1}\Vert <1$, the commonly used in those existing literature, but also the case where $\Vert A^{-1}\Vert =1$.

25 pages, 3 figures, 3 tables

Cited by in corpus (5)

• Optimal parameter for the SOR-like iteration method for solving the system of absolute value equations
• On finite termination of the generalized Newton method for solving absolute value equations
• A generalization of the Newton-based matrix splitting iteration method for generalized absolute value equations
• Further study on two fixed point iterative schemes for absolute value equations
• An inexact framework of the Newton-based matrix splitting iterative method for the generalized absolute value equation