Absolute value equation solution via dual complementarity

By utilizing a dual complementarity condition, we propose an iterative method for solving the NP-hard absolute value equation (AVE): Ax − | x | =  b , where A is an n  × n square matrix. The algorithm makes no assumptions on the AVE other than solvability and consists of solving a succession of line...

Full description

Saved in:
Bibliographic Details
Published in:Optimization letters 2013-04, Vol.7 (4), p.625-630
Main Author: Mangasarian, Olvi L.
Format: Article
Language:English
Subjects:
Computational Intelligence
Mathematics
Mathematics and Statistics
Numerical and Computational Physics
Operations Research/Decision Theory
Optimization
Original Paper
Simulation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:By utilizing a dual complementarity condition, we propose an iterative method for solving the NP-hard absolute value equation (AVE): Ax − | x | =  b , where A is an n  × n square matrix. The algorithm makes no assumptions on the AVE other than solvability and consists of solving a succession of linear programs. The algorithm was tested on 500 consecutively generated random solvable instances of the AVE with n  = 10, 50, 100, 500 and 1,000. The algorithm solved 90.2 % of the test problems to an accuracy of 10 −8 .
ISSN:1862-4472
1862-4480
DOI:10.1007/s11590-012-0469-5