A Multiplicative Barrier Function Method for Linear Programming

被引：48

作者：

Iri, Masao ^{[1
]}

Imai, Hiroshi ^{[2
]}

机构：

[1] Univ Tokyo, Fac Engn, Dept Math Engn & Instrumentat Phys, Bunkyo Ku, Tokyo 113, Japan

[2] Kyushu Univ, Dept Comp Sci & Commun Engn, Fukuoka 812, Japan

来源：

ALGORITHMICA | 1986年 / 1卷 / 1-4期

关键词：

Linear programming; Interior method; Barrier function; Newton method;

D O I：

10.1007/BF01840457

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

A simple Newton-like descent algorithm for linear programming is proposed together with results of preliminary computational experiments on small- and medium-size problems. The proposed algorithm gives local superlinear convergence to the optimum and, experimentally, shows global linear convergence. It is similar to Karmarkar's algorithm in that it is an interior feasible direction method and self-correcting, while it is quite different from Karmarkar's in that it gives superlinear convergence and that no artificial extra constraint is introduced nor is projective geometry needed, but only affine geometry suffices.

引用

页码：455 / 482

页数：28