|
Absolute Value Equation Solution via Concave Minimization
Professor Olvi Mangasarian
Department of Mathematics
University of California, San Diego
Abstract
The NP-hard absolute value equation (AVE) Ax-|x|=b where
A is an n-by-n real matrix and b is an n-by-1 real vector is solved by a
succession of linear programs. The linear programs arise from a
reformulation of the AVE as the minimization of a piecewise-linear concave
function on a polyhedral set and solving the latter by
successive linearization. A simple MATLAB implementation
of the successive linearization algorithm solved 100 consecutively
generated 1000-dimensional random instances of the AVE with only
five violated equations out of a total of 100,000 equations.
Paper is available at: ftp://ftp.cs.wisc.edu/pub/dmi/tech-reports/06-02.pdf
|











