On the convergence of the Mizuno-Todd-Ye algorithm to the analytic center of the solution set

被引：11

作者：

Gonzaga, CC

Tapia, RA

机构：

[1] RICE UNIV,DEPT COMPUTAT & APPL MATH,HOUSTON,TX 77251

[2] RICE UNIV,CTR RES PARALLEL COMPUTAT,HOUSTON,TX 77251

来源：

SIAM JOURNAL ON OPTIMIZATION | 1997年 / 7卷 / 01期

关键词：

linear programming; primal-dual interior-point algorithm; predictor-corrector algorithm; analytic center;

D O I：

10.1137/S1052623493243557

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In this work we demonstrate that the Miauno-Todd-Ye predictor-corrector primal-dual interior-point method for linear programming generates iteration sequences that converge to the analytic center of the solution set.

引用

页码：47 / 65

页数：19

共 27 条

[1] LIMITING BEHAVIOR OF THE AFFINE SCALING CONTINUOUS TRAJECTORIES FOR LINEAR-PROGRAMMING PROBLEMS [J].

ADLER, I ;

MONTEIRO, RDC .

MATHEMATICAL PROGRAMMING, 1991, 50 (01) :29-51

[2]

Charnes A., 1991, J PROD ANAL, V2, P197, DOI DOI 10.1007/BF00159732

[3] PATH-FOLLOWING METHODS FOR LINEAR-PROGRAMMING [J].

GONZAGA, CC .

SIAM REVIEW, 1992, 34 (02) :167-224

[4] POINT-TO-SET MAPS IN MATHEMATICAL PROGRAMMING [J].

HOGAN, WW .

SIAM REVIEW, 1973, 15 (03) :591-603

[5]

HUARD P, 1979, MATH PROGRAMMING STU, V10

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

[7]

Kojima M, 1989, PROGR MATH PROGRAMMI, P29, DOI DOI 10.1007/978-1-4613-9617-8_2

[8] COMPUTATIONAL EXPERIENCE WITH A PRIMAL-DUAL INTERIOR POINT METHOD FOR LINEAR-PROGRAMMING [J].

LUSTIG, IJ ;

MARSTEN, RE ;

SHANNO, DF .

LINEAR ALGEBRA AND ITS APPLICATIONS, 1991, 152 :191-222

[9] AN ANALOG OF MOREAU PROXIMATION THEOREM, WITH APPLICATION TO THE NON-LINEAR COMPLEMENTARITY-PROBLEM [J].

MCLINDEN, L .

PACIFIC JOURNAL OF MATHEMATICS, 1980, 88 (01) :101-161

[10] SUPERLINEARLY CONVERGENT O(ROOT-NL)-ITERATION INTERIOR-POINT ALGORITHMS FOR LINEAR-PROGRAMMING AND THE MONOTONE LINEAR COMPLEMENTARITY-PROBLEM [J].

MCSHANE, K .

SIAM JOURNAL ON OPTIMIZATION, 1994, 4 (02) :247-261

← 1 2 3 →