A COMPLEXITY REDUCTION FOR THE LONG-STEP PATH-FOLLOWING ALGORITHM FOR LINEAR PROGRAMMING

被引：13

作者：

Den Hertog, D. ^{[1
]}

Roos, C. ^{[1
]}

Vial, J. -Ph. ^{[2
]}

机构：

[1] Delft Univ Technol, Dept Math & Comp Sci, NL-2600 GA Delft, Netherlands

[2] Univ Geneva, Dept Commercial & Ind Econ, CH-1211 Geneva 4, Switzerland

来源：

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

关键词：

linear programming; interior point method; logarithmic barrier function; polynomial algorithm; Goldstein-Armijo rule;

D O I：

10.1137/0802006

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A modification of previously published long-step path-following algorithms for the solution of the linear programming problem is presented. This modification uses the simple Goldstein-Armijo rule. A root n reduction in the complexity bound is obtained, while a linesearch may still be done. Depending on the updating scheme for the barrier parameter, the resulting complexity bounds are O(n(3)L) or O(n(3.5)L).

引用

页码：71 / 87

页数：17

共 17 条

[1]

ANSTREICHER K. M., 1988, PREPRINT

[2] A STANDARD FORM VARIANT, AND SAFEGUARDED LINESEARCH, FOR THE MODIFIED KARMARKAR ALGORITHM [J].

ANSTREICHER, KM .

MATHEMATICAL PROGRAMMING, 1990, 47 (03) :337-351

[3]

Fiacco AV, 1990, NONLINEAR PROGRAMMIN

[4]

FREUND R. M., 1988, POLYNOMIAL TIME ALGO

[5] ON PROJECTED NEWTON BARRIER METHODS FOR LINEAR-PROGRAMMING AND AN EQUIVALENCE TO KARMARKAR PROJECTIVE METHOD [J].

GILL, PE ;

MURRAY, W ;

SAUNDERS, MA ;

TOMLIN, JA ;

WRIGHT, MH .

MATHEMATICAL PROGRAMMING, 1986, 36 (02) :183-209

[6]

Gonzaga C.C., 1989, PROGR MATH PROGRAMMI, P1

[7]

GONZAGA C. C., 1989, ES21089 COPPE FED U

[8] LARGE STEP PATH-FOLLOWING METHODS FOR LINEAR PROGRAMMING, PART I: BARRIER FUNCTION METHOD [J].

Gonzaga, Clovis C. .

SIAM JOURNAL ON OPTIMIZATION, 1991, 1 (02) :268-279

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

KARMARKAR, N .

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

[10] 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

← 1 2 →