绝对值等式问题的一个求解方法

 线性规划、二次规划、双矩阵对策以及其他问题都能转化为线性互补问题，而线性互补问题又可以归结为绝对值等式问题，因此研究绝对值等式问题是非常有意义的。绝对值等式问题是一个NP-hard问题，本文给出了绝对值等式问题的一个求解方法。在假设矩阵A的奇异值（矩阵ATA特征值的非负平方根）大于1时，绝对值等式问题存在唯一解，进而将绝对值等式问题转化为线性互补问题。给出了求解一般线性互补问题的混合整数线性规划解法，数值实验表明此方法对求解绝对值等式问题十分有效。

A New Solution Method for Absolute Value Equations

The absolute value equations come from linear programming, quadratic programming, bimatrix games and other problems, that can all be reduced to a linear complementarity problem, which in turn is equivalent to absolute value equations. The solution of this kind of equations is an NP-hard problem in its general form. In this paper, a new method for solving this kind of equations is presented. Firstly, the existence and uniqueness theorem of the solution to absolute value equations problem is proven under the condition that the singular values of A are greater than one. Based on the theorem, the solution is transformed into a general linear complementarity problem. Then the mixed-integer linear programming method is applied to the linear complementarity problem. At last, some numerical examples are given to indicate that the method is feasible and effective to absolute value equations problems. These results may play a key role in solving this kind of equations.