ON THE COMPUTATIONAL-COMPLEXITY OF PIECEWISE-LINEAR HOMOTOPY ALGORITHMS

被引：6

作者：

TODD, MJ ^{[1
]}

机构：

[1] UNIV CAMBRIDGE,CAMBRIDGE,ENGLAND

来源：

MATHEMATICAL PROGRAMMING | 1982年 / 24卷 / 02期

关键词：

COMPUTER PROGRAMMING - Algorithms;

D O I：

10.1007/BF01585104

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

It is shown that piecewise-linear homotopy algorithms may take a number of steps that grows exponentially with the dimension when solving a system of linear equations whose solution lies close to the starting point. The examples are based on an example of Murty exhibiting exponential growth for Lemke's algorithm for the linear complementarity problem.

引用

页码：216 / 224

页数：9

共 22 条

[1] SIMPLICIAL AND CONTINUATION METHODS FOR APPROXIMATING FIXED-POINTS AND SOLUTIONS TO SYSTEMS OF EQUATIONS
ALLGOWER, E
GEORG, K
[J]. SIAM REVIEW, 1980, 22 (01) : 28 - 85
[2] OBSERVATIONS ON A CLASS OF NASTY LINEAR COMPLEMENTARITY-PROBLEMS
COTTLE, RW
[J]. DISCRETE APPLIED MATHEMATICS, 1980, 2 (02) : 89 - 111
[3] Eaves B. C., 1976, Mathematics of Operations Research, V1, P1, DOI 10.1287/moor.1.1.1
[4] Eaves B.C., 1972, MATHEMATICAL PROGRAM, V3, P225, DOI 10.1007/BF01584991
[5] Eaves BC, 1972, MATHEMATICAL PROGRAM, V3, P1, DOI [10.1007/BF01584975, DOI 10.1007/BF01584975]
[6] EAVES BC, 1976, NONLINEAR PROGRAMMIN, P73
[7] COMPUTATIONAL COMPLEXITY OF LCPS ASSOCIATED WITH POSITIVE DEFINITE SYMMETRIC MATRICES
FATHI, Y
[J]. MATHEMATICAL PROGRAMMING, 1979, 17 (03) : 335 - 344
[8] KATZENELSON J, 1965, BELL SYST TECH J, V44, P1605
[9] Klee V, 1972, INEQUALITIES, VIII
[10] MERRILL OH, 1972, THESIS U MICHIGAN

← 1 2 3 →