Primal-dual bilinear programming solution of the absolute value equation

摘要

We propose a finitely terminating primal-dual bilinear programming algorithm for the solution of the NP-hard absolute value equation (AVE): Ax - {pipe}x{pipe} = b, where A is an n × n square matrix. The algorithm, which makes no assumptions on AVE other than solvability, consists of a finite number of linear programs terminating at a solution of the AVE or at a stationary point of the bilinear program. The proposed algorithm was tested on 500 consecutively generated random instances of the AVE with n = 10, 50, 100, 500 and 1,000. The algorithm solved 88. 6% of the test problems to an accuracy of 10 ~(-6).