A LOW COMPLEXITY INTERIOR-POINT ALGORITHM FOR LINEAR PROGRAMMING

被引：15

作者：

Todd, Michael J. ^{[1
]}

机构：

[1] Cornell Univ, Sch Operat Res & Ind Engn, Coll Engn, Ithaca, NY 14853 USA

来源：

SIAM JOURNAL ON OPTIMIZATION | 1992年 / 2卷 / 02期

基金：

美国国家科学基金会;

关键词：

linear programming; interior-point methods;

D O I：

10.1137/0802011

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

This paper describes an interior-point algorithm for linear programming that is almost as simple as the affine-scaling method and yet achieves the currently best complexity of O(root n t) iterations to attain precision t. The basic algorithm needs neither dual estimates nor lower bounds, although its analysis is based on Ye's results for the primal-dual potential function. Some computationally preferable variants are also presented.

引用

页码：198 / 209

页数：12

共 33 条

[11]

GONZAGA C., 1989, ES22790 COPPE FED U

[12]

GONZAGA CC, 1991, ALGORITHMICA, V6, P153, DOI 10.1007/BF01759039

[13] POLYNOMIAL AFFINE ALGORITHMS FOR LINEAR-PROGRAMMING [J].

GONZAGA, CC .

MATHEMATICAL PROGRAMMING, 1990, 49 (01) :7-21

[14]

GONZAGA CC, 1988, PROGR MATH PROGRAMMI, P1

[15] LARGE STEP PATH-FOLLOWING METHODS FOR LINEAR PROGRAMMING, PART II: POTENTIAL REDUCTION METHOD [J].

Gonzaga, Clovis C. .

SIAM JOURNAL ON OPTIMIZATION, 1991, 1 (02) :280-292

[16] A NEW POLYNOMIAL-TIME ALGORITHM FOR LINEAR-PROGRAMMING [J].

KARMARKAR, N .

COMBINATORICA, 1984, 4 (04) :373-395

[17] AN O(SQUARE-ROOT-N L) ITERATION POTENTIAL REDUCTION ALGORITHM FOR LINEAR COMPLEMENTARITY-PROBLEMS [J].

KOJIMA, M ;

MIZUNO, S ;

YOSHISE, A .

MATHEMATICAL PROGRAMMING, 1991, 50 (03) :331-342

[18] A POLYNOMIAL-TIME ALGORITHM FOR A CLASS OF LINEAR COMPLEMENTARITY-PROBLEMS [J].

KOJIMA, M ;

MIZUNO, S ;

YOSHISE, A .

MATHEMATICAL PROGRAMMING, 1989, 44 (01) :1-26

[19]

KOJIMA M., 1988, PROGR MATH PROGRAMMI, P29

[20] BOUNDARY-BEHAVIOR OF INTERIOR POINT ALGORITHMS IN LINEAR-PROGRAMMING [J].

MEGIDDO, N ;

SHUB, M .

MATHEMATICS OF OPERATIONS RESEARCH, 1989, 14 (01) :97-146

← 1 2 3 4 →