A New Semi-smooth Newton Method for Absolute Value Equations

Absolute value equation(AVE):Ax |x| = b,where A is an n×n real matrix,arising in solving systems of interval linear equations.Linear complementarity problem,which subsumes many mathematical programming problems,can be formulated as an AVE.A semi-smooth Newton algorithm is proposed for solving the AVE.In the algorithm,two non-smooth equation reformulations are used.They are constructed based on the min-and FB-function,respectively.At each iteration,however,only one system of linear equations needs to be solved.The algorithm is globally and finitely convergent,under the condition that the interval matrix [A I,A + I] is regular.The proposed algorithm was tested on 100 consecutively generated random instances of the AVE with n = 1000.All of these test problems are well solved,with accuracy of 10 6.