Absolute Value Equation Solution Via Linear Programming

Olvi L. Mangasarian ()
Additional contact information
Olvi L. Mangasarian: University of Wisconsin

Journal of Optimization Theory and Applications, 2014, vol. 161, issue 3, No 12, 870-876

Abstract: Abstract By utilizing a dual complementarity property, we propose a new linear programming 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 few linear programs, typically less than four. The algorithm was tested on 500 consecutively generated random solvable instances of the AVE with n=10, 50, 100, 500 and 1000. The algorithm solved 100 % of the test problems to an accuracy of 10−8 by solving an average of 3.3 linear programs per AVE problem.

Keywords: Absolute value equation; Complementarity; Linear programming (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://link.springer.com/10.1007/s10957-013-0461-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:161:y:2014:i:3:d:10.1007_s10957-013-0461-y

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-013-0461-y

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().