[Home]
[
News]
[ Events]
[ People]
[ Research]
[ Education]
[Visitor Info]
[UCSD Only]
[Admin]
Absolute Value Equation Solution via Concave Minimization
Professor Olvi Mangasarian
UCSD Department of Mathematics
Abstract:
The NP-hard absolute value equation (AVE) Ax-|x|=b whereA 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 bysuccessive linearization. A simple MATLAB implementationof the successive linearization algorithm solved 100 consecutivelygenerated 1000-dimensional random instances of the AVE with onlyfive 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
Tuesday, April 11, 2006
11:00AM AP&M 2402
News]
[ Events]
[ People]
[ Research]
[ Education]
[Visitor Info]
[UCSD Only]
[Admin]
Directors:
Randolph E. Bank
Philip E. Gill
Michael Holst
Administrative Contact:
[ Click to Send Email ]
Randolph E. Bank
Philip E. Gill
Michael Holst
Administrative Contact:
[ Click to Send Email ]
Professor Olvi Mangasarian
UCSD Department of Mathematics
Abstract:
The NP-hard absolute value equation (AVE) Ax-|x|=b whereA 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 bysuccessive linearization. A simple MATLAB implementationof the successive linearization algorithm solved 100 consecutivelygenerated 1000-dimensional random instances of the AVE with onlyfive 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
Tuesday, April 11, 2006
11:00AM AP&M 2402