Homotopy Techniques in Linear Programming

被引：8

作者：

Nazareth, J. L. ^{[1
,2
]}

机构：

[1] CDSS, Berkeley, CA 94704 USA

[2] IIASA, A-2361 Laxenburg, Austria

来源：

ALGORITHMICA | 1986年 / 1卷 / 1-4期

关键词：

Homotopy; Linear programming; Interior point methods; Nonlinear programming; Karmarkar's method; Quadratic regularization; Path-following;

D O I：

10.1007/BF01840461

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

In this note, we consider the solution of a linear program, using suitably adapted homotopy techniques of nonlinear programming and equation solving that move through the interior of the polytope of feasible solutions. The homotopy is defined by means of a quadratic regularizing term in an appropriate metric. We also briefly discuss algorithmic implications and connections with the affine variant of Karmarkar's method.

引用

页码：529 / 535

页数：7

共 19 条

[1] [Anonymous], 1981, PATHWAYS SOLUTIONS F
[2] Eaves B. C., 1976, Mathematics of Operations Research, V1, P1, DOI 10.1287/moor.1.1.1
[3] EAVES B. C., 1979, CONSTRUCTIVE APPROAC, P153
[4] GILL PE, 1985, 8511 SOL STANF U DEP
[5] ALGORITHMS FOR SOLVING F(X)=0
HIRSCH, MW
SMALE, S
[J]. COMMUNICATIONS ON PURE AND APPLIED MATHEMATICS, 1979, 32 (03) : 281 - 312
[6] Karmarkar Narendra, 1984, P 16 ANN ACM S THEOR, P302
[7] KHACHIIAN LG, 1979, DOKL AKAD NAUK SSSR+, V244, P1093
[8] Lemke C.E., 1968, MATH DECISION SCI
[9] ITERATIVE SOLUTION OF LINEAR-PROGRAMS
MANGASARIAN, OL
[J]. SIAM JOURNAL ON NUMERICAL ANALYSIS, 1981, 18 (04) : 606 - 614
[10] MEGIDDO N, 1985, VARIATION KARMARKARS

← 1 2 →