
Accession Number : ADA186001
Title : An O(n3L) Interior Point Algorithm for Convex Quadratic Programming.
Descriptive Note : Technical rept.,
Corporate Author : CALIFORNIA UNIV BERKELEY OPERATIONS RESEARCH CENTER
Personal Author(s) : Monteiro, R C ; Adler, I
PDF Url : ADA186001
Report Date : Jun 1987
Pagination or Media Count : 34
Abstract : The authors describe a primaldual interior point algorithm for convex quadratic programming problems which requires a total of O(cu n L) arithmetic operations. Each iteration updates a penalty parameter and finds an approximate Newton's 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 n L). Keywords: Interiorpoint methods; Convex quadratic programming; Karmarkar's algorithm; Polynomialtime algorithms; Barrier function; Path following. (Author)
Descriptors : *ALGORITHMS, *QUADRATIC PROGRAMMING, CONVEX SETS, ITERATIONS, LOGARITHM FUNCTIONS, MATHEMATICAL PROGRAMMING, PENALTIES, POLYNOMIALS, SQUARE ROOTS
Subject Categories : Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE