线性规划的邻域跟踪算法

被引：13

作者：

艾文宝

机构：

[1] 北京邮电大学理学院教学部北京

来源：

中国科学(A辑:数学) | 2004年 / 01期

关键词：

线性规划; 原始-对偶内点算法; 宽邻域算法; 二次收敛;

D O I：

暂无

中图分类号：

O221.1 [线性规划];

学科分类号：

摘要：

提出了线性规划的邻域跟踪算法.当这个邻域是宽邻域时,该算法就是宽邻域原始-对偶内点算法;如果这个邻域退化成中心路径,则算法就退化成中心路径跟踪算法.证明了该算法具有O( nL)次迭代复杂性,而经典的宽邻域算法是O(nL)次迭代复杂性.也证明了该算法在非退化条件下是二次收敛的,并给出了一些计算结果.

引用

页码：40 / 47

页数：8

共 6 条

[1] The largest step path following algorithm for monotone linear complementarity problems [J].

Gonzaga, CC .

MATHEMATICAL PROGRAMMING, 1997, 76 (02) :309-332

[2]

Convergence behavior of interior-point algorithms[J] . Osman Güler,Yinyu Ye.Mathematical Programming . 1993 (1)

[3]

Interior path following primal-dual algorithms. part II: Convex quadratic programming[J] . Renato D. C. Monteiro,Ilan Adler.Mathematical Programming . 1989 (1)

[4]

Interior path following primal-dual algorithms. part I: Linear programming[J] . Renato D. C. Monteiro,Ilan Adler.Mathematical Programming . 1989 (1)

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

[6]

The largest step path following algorithm for monotone linear complementarity problems .2 Gonzaga,C. C. Mathematical Programming . 1997

← 1 →