A generalized Newton method for absolute value equations

被引：287

作者：

Mangasarian, O. 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 | 2009年 / 3卷 / 01期

基金：

美国国家科学基金会;

关键词：

Absolute value equation; Generalized Newton; Linear complementarity problems;

D O I：

10.1007/s11590-008-0094-5

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

A direct generalized Newton method is proposed for solving the NP-hard absolute value equation (AVE) Ax -vertical bar x vertical bar = b when the singular values of A exceed 1. A simple MATLAB implementation of the method solved 100 randomly generated 1,000-dimensional AVEs to an accuracy of 10(-6) in less than 10 s each. Similarly, AVEs corresponding to 100 randomly generated linear complementarity problems with 1,000 x 1,000 nonsymmetric positive definite matrices were also solved to the same accuracy in less than 29 s each.

引用

页码：101 / 108

页数：8

共 11 条

[1]

Bertsekas Dimitri P, 1997, Journal of the Operational Research Society, V48, P334, DOI [10.1057/palgrave.jors.2600425, 10.1057/palgrave.jors.2600425.18, DOI 10.1057/PALGRAVE.JORS.2600425.18]

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

CHUNG, SJ .

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

[3]

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

[4]

Cottle Richard W., 1968, Linear Algebra and its Applications, V1, P103, DOI [DOI 10.1016/0024-3795(68)90052-9, 10.1016/0024-3795(68)90052-9]

[5] Absolute value programming [J].

Mangasarian, O. L. .

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

[6] Absolute value equations [J].

Mangasarian, O. L. ;

Meyer, R. R. .

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

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

Mangasarian, O. L. .

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

[8]

Ortega JM., 1970, Iterative Solution of Nonlinear Equations in Several Variables

[9]

Polyak BT, 1987, INTRO OPTIMIZATION

[10]

ROCKAFELLAR RT, 1971, P 4 C PROB BRAS

← 1 2 →