A Polynomial Newton Method for Linear Programming

被引：73

作者：

de Ghellinck, Guy ^{[1
]}

Vial, Jean-Philippe ^{[1
,2
]}

机构：

[1] Univ Catholique Louvain, CORE, B-1348 Louvain, Belgium

[2] Univ Geneva, Dept COMIN, CH-1211 Geneva 4, Switzerland

来源：

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

关键词：

Linear programming; Polynomial complexity; Newton method;

D O I：

10.1007/BF01840456

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

An algorithm is presented for solving a set of linear equations on the nonnegative orthant. This problem can be made equivalent to the maximization of a simple concave function subject to a similar set of linear equations and bounds on the variables. A Newton method can then be used which enforces a uniform lower bound which increases geometrically with the number of iterations. The basic steps are a projection operation and a simple line search. It is shown that this procedure either proves in at most O(n(2)m(2)L) operations that there is no solution or, else, computes an exact solution in at most O(n(3)m(2)L) operations. The linear programming problem is treated as a parametrized feasibility problem and solved in at most O(n(3)m(2)L) operations.

引用

页码：425 / 453

页数：29