A hybrid algorithm for solving the absolute value equation

被引：40

作者：

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

共 20 条

[1] NP-COMPLETENESS OF THE LINEAR COMPLEMENTARITY-PROBLEM [J].

CHUNG, SJ .

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 1989, 60 (03) :393-399

[2]

Cottle R. W., 1992, The Linear Complementarity Problem

[3]

Cottle RW., 1968, Linear Algebra Appl, V1, P103, DOI [DOI 10.1016/0024-3795(68)90052-9, 10.1016/0024-3795(68)90052-9]

[4]

ILOG, 2003, ILOG CPLEX 9 0 US MA

[5]

Mangasarian O.J., 1997, ACTA MATH VIETNAMICA, V22, P199

[6] Absolute value programming [J].

Mangasarian, O. L. .

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2007, 36 (01) :43-53

[7] Absolute value equations [J].

Mangasarian, O. L. ;

Meyer, R. R. .

LINEAR ALGEBRA AND ITS APPLICATIONS, 2006, 419 (2-3) :359-367

[8] A generalized Newton method for absolute value equations [J].

Mangasarian, O. L. .

OPTIMIZATION LETTERS, 2009, 3 (01) :101-108

[9] Absolute value equation solution via concave minimization [J].

Mangasarian, O. L. .

OPTIMIZATION LETTERS, 2007, 1 (01) :3-8

[10] Absolute Value Equation Solution Via Linear Programming [J].

Mangasarian, Olvi L. .

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 2014, 161 (03) :870-876

← 1 2 →