A LOW COMPLEXITY INTERIOR-POINT ALGORITHM FOR LINEAR PROGRAMMING

被引：15

作者：

Todd, Michael J. ^{[1
]}

机构：

[1] Cornell Univ, Sch Operat Res & Ind Engn, Coll Engn, Ithaca, NY 14853 USA

来源：

SIAM JOURNAL ON OPTIMIZATION | 1992年 / 2卷 / 02期

基金：

美国国家科学基金会;

关键词：

linear programming; interior-point methods;

D O I：

10.1137/0802011

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

This paper describes an interior-point algorithm for linear programming that is almost as simple as the affine-scaling method and yet achieves the currently best complexity of O(root n t) iterations to attain precision t. The basic algorithm needs neither dual estimates nor lower bounds, although its analysis is based on Ye's results for the primal-dual potential function. Some computationally preferable variants are also presented.

引用

页码：198 / 209

页数：12

共 33 条

[1]

ANSTREICHER K. M., 1989, 8939 CORE CATH U LOU

[2] ON MONOTONICITY IN THE SCALED POTENTIAL ALGORITHM FOR LINEAR-PROGRAMMING [J].

ANSTREICHER, KM .

LINEAR ALGEBRA AND ITS APPLICATIONS, 1991, 152 :223-232

[3] A Monotonic Projective Algorithm for Fractional Linear Programming [J].

Anstreicher, Kurt M. .

ALGORITHMICA, 1986, 1 (1-4) :483-498

[4]

BARNES E. R., 1988, 13965 RC IBM TJ WATS

[5] A VARIATION ON KARMARKAR ALGORITHM FOR SOLVING LINEAR-PROGRAMMING PROBLEMS [J].

BARNES, ER .

MATHEMATICAL PROGRAMMING, 1986, 36 (02) :174-182

[6] THE NONLINEAR GEOMETRY OF LINEAR-PROGRAMMING .2. LEGENDRE TRANSFORM COORDINATES AND CENTRAL TRAJECTORIES [J].

BAYER, DA ;

LAGARIAS, JC .

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1989, 314 (02) :527-581

[7] THE NONLINEAR GEOMETRY OF LINEAR-PROGRAMMING .1. AFFINE AND PROJECTIVE SCALING TRAJECTORIES [J].

BAYER, DA ;

LAGARIAS, JC .

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1989, 314 (02) :499-526

[8] A Polynomial Newton Method for Linear Programming [J].

de Ghellinck, Guy ;

Vial, Jean-Philippe .

ALGORITHMICA, 1986, 1 (1-4) :425-453

[9]

Dikin I. I., 1967, SOVIET MATH DOKLADY, V8, P674

[10] POLYNOMIAL-TIME ALGORITHMS FOR LINEAR-PROGRAMMING BASED ONLY ON PRIMAL SCALING AND PROJECTED GRADIENTS OF A POTENTIAL FUNCTION [J].

FREUND, RM .

MATHEMATICAL PROGRAMMING, 1991, 51 (02) :203-222

← 1 2 3 4 →