Primal-Dual Bilinear Programming Solution of the Absolute Value Equation
Abstract
We propose a finitely terminating primal-dual bilinear programming algorithm for the solution of
the NP-hard absolute value equation (AVE): Ax ? |x| = 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
1e ? 6 .
Subject
linear programming
bilinear programming
absolute value equations
Permanent Link
http://digital.library.wisc.edu/1793/64356Citation
11-01