A Smoothing Newton Method For Solving A Class Of Absolute Value Equations

Popular the system of absolute value equations (SAVE) is given by Ax-Blxl=b. On the one hand, many practical problems can be modeled as an SAVE, on the other hand, many optimization and related problems, such as linear programming, quadratic programming, and linear complementarity problems, can be equivalently transformed as an SAVE, and therefore, SAVE has wide applications. It has been shown that SAVE is an NP-hard problem. So it has important theoretical significance and practical application value for the study of SAVE. In recent years, SAVE has received wide attention, and has made progress quickly.In this paper, we consider a class of generalized absolute value equations, i.e., Ax-|Bx+c|=b, which is a generalization of Ax-Blxl=b. We mainly discuss the theory and algorithm for solving this class of absolute value equations. The main work is as follows:1. We transform the considered problem as a linear complementarity problem, and then, propose a smoothing Newton algorithm to solve it. We show that the algorithm is well defined under the following three conditions:i) matrices (B+A) and (B-A) are invertible; ⅱ) matrices A and B satisfy AB=BA; and iii) the absolute value of every diagonal element of A is strictly greater than that of B. Moreover, we show that the algorithm is globally convergent when B=I, c=0.2. We implement the proposed smoothing Newton method for solving randomly generated200-dimensional SAVE,500-dimensional SAVE,800-dimensional SAVE, and1000-dimensional SAVE, where all codes in MATLAB.50randomly generated SAVEs for each case are solved to an accuracy of10-6. The average time for the200-dimensional SAVEs is about0.3s. The average time for the500-dimensional SAVEs is about3s. The average time for the800-dimensional SAVEs is about10s. The average time for the1000-dimensional SAVEs is about20s.