
Accession Number : ADA183792
Title : An O(n(3)L) PrimalDual Interior Point Algorithm for Linear Programming.
Descriptive Note : Technical rept.,
Corporate Author : CALIFORNIA UNIV BERKELEY OPERATIONS RESEARCH CENTER
Personal Author(s) : Monteiro,R C ; Adler,I
PDF Url : ADA183792
Report Date : May 1987
Pagination or Media Count : 31
Abstract : The authors describe a primaldual interior point algorithm for linear programming problems which requires a total of O cubed L arithmetic operations. Each iteration updates a penalty parameter and finds an approximate Newtons direction associated with the KuhnTucker system of equations which characterizes a solution of the logarithm barrier function problem. This direction is then used to find the next iterate. The algorithm is based on the path following idea. The total number of iterations is shown to be of the order of O square root of nL. Keywords: Convergence; Polynomialtime algorithms; Barrier function; Path following.
Descriptors : *ALGORITHMS, *LINEAR PROGRAMMING, QUADRATIC PROGRAMMING, BARRIERS, ITERATIONS, LOGARITHM FUNCTIONS, PENALTIES, POLYNOMIALS, SQUARE ROOTS
Subject Categories : Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE