CONVERGENCE BEHAVIOR OF INTERIOR-POINT ALGORITHMS

被引：84

作者：

GULER, O ^{[1
]}

YE, YY ^{[1
]}

机构：

[1] UNIV IOWA,DEPT MANAGEMENT SCI,IOWA CITY,IA 52242

来源：

MATHEMATICAL PROGRAMMING | 1993年 / 60卷 / 02期

关键词：

STRICT COMPLEMENTARITY; MAXIMAL COMPLEMENTARITY; INTERIOR POINT ALGORITHMS; LINEAR PROGRAMMING; MONOTONE COMPLEMENTARITY PROBLEM;

D O I：

10.1007/BF01580610

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We show that most interior-point algorithms for linear programming generate a solution sequence in which every limit point satisfies the strict complementarity condition. These algorithms include all path-following algorithms and some potential reduction algorithms. The result also holds for the monotone complementarity problem if a strict complementarity solution exists. In general, the limit point is a solution that maximizes the number of its nonzero components among all solutions.

引用

页码：215 / 228

页数：14

共 39 条

[1] LONG STEPS IN AN O(N3L) ALGORITHM FOR LINEAR-PROGRAMMING [J].