Smoothing Newton Method for Absolute Value Equations Based on Aggregate Function

摘要

We investigate the NP-hard absolute value equation (AVE) Ax-|x| = b, where A is an arbitrary square matrix whose all singular values of A exceed one. The significance of the absolute value equations arises from the fact that linear programs, quadratic programs, bimatrix games and other problems can all be reduced to the linear complementarity problem that in turn is equivalent to the absolute value equations. In this paper, we present a smoothing method for the AVE. First, we replace the absolute value function by a smooth one, called aggregate function. With this smoothing technique, we formulate the non-smooth AVE as a smooth nonlinear equations, furthermore, an unconstrained differentiable optimization problem. Then we adopt quasi-Newton method to solve this problem. Numerical results indicate that the method is feasible and effective to absolute value equations.