Accession Number : ADA183792
Title : An O(n(3)L) Primal-Dual 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 primal-dual 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 Kuhn-Tucker 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; Polynomial-time 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