A hybrid algorithm for solving the absolute value equation

被引：36
|
作者：
Mangasarian, Olvi L. [1 ,2 ]
机构：
[1] Univ Wisconsin, Dept Comp Sci, Madison, WI 53706 USA
[2] Univ Calif San Diego, Dept Math, La Jolla, CA 92093 USA
来源：
OPTIMIZATION LETTERS | 2015年 / 9卷 / 07期
关键词：
Absolute value equation; Concave minimization; Linear programming; Linear equations; COMPLEMENTARITY; THEOREM;
D O I：
10.1007/s11590-015-0893-4
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
We propose a hybrid algorithm for solving the NP-hard absolute value equation (AVE): , where is an square matrix. The algorithm makes no assumptions on the AVE other than solvability and consists of solving iteratively a linear system of equations followed by a linear program. The algorithm was tested on 100 consecutively generated random solvable instances of the AVE with 50, 100, 200, 500 and 1000. The algorithm solved of the test problems to an accuracy of by solving an average of 2.77 systems of linear equations and linear programs per AVE.
引用
收藏
页码：1469 / 1474
页数：6
相关论文
共 50 条
12345