A PRIMAL DUAL INFEASIBLE-INTERIOR-POINT ALGORITHM FOR LINEAR-PROGRAMMING

被引：178

作者：

KOJIMA, M

MEGIDDO, N

MIZUNO, S

机构：

[1] IBM CORP,ALMADEN RES CTR,SAN JOSE,CA 95114

[2] TEL AVIV UNIV,SCH MATH SCI,IL-69978 TEL AVIV,ISRAEL

[3] INST STAT MATH,TOKYO,JAPAN

来源：

MATHEMATICAL PROGRAMMING | 1993年 / 61卷 / 03期

关键词：

INFEASIBLE-INTERIOR-POINT ALGORITHM; INTERIOR-POINT ALGORITHM; PRIMAL DUAL ALGORITHM; LINEAR PROGRAM; LARGE STEP; GLOBAL CONVERGENCE;

D O I：

10.1007/BF01582151

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

As in many primal-dual interior-point algorithms, a primal-dual infeasible-interior-point algorithm chooses a new point along the Newton direction towards a point on the central trajectory, but it does not confine the iterates within the feasible region. This paper proposes a step length rule with which the algorithm takes large distinct step lengths in the primal and dual spaces and enjoys the global convergence.

引用

页码：263 / 280

页数：18

共 26 条

[1]

CARPENTER TJ, IN PRESS SIAM J OPTI

[2]

CHOI IC, 1990, ORSA J COMPUTING, V2, P304

[3]

Fiacco AV, 1990, NONLINEAR PROGRAMMIN

[4] A LITTLE THEOREM OF THE BIG-MU IN INTERIOR-POINT ALGORITHMS [J].