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 primal-dual 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 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 n L). Keywords: Interior-point methods; Convex quadratic programming; Karmarkar's algorithm; Polynomial-time 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