Abstract

We investigate the NP-hard absolute value equation (AVE) Ax - |x| = b, where A is an arbitrary square matrix whose singular values 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, the non-smooth AVE is formulated 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.

Key words: Absolute value equation, quasi-Newton method, smoothing method, aggregate function.