An O(n3L) Interior Point Algorithm for Convex Quadratic Programming.

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)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1987
Accession Number
ADA186001

Entities

People

  • I. Adler
  • R. C. Monteiro

Organizations

  • University of California, Berkeley

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Arithmetic
  • California
  • Computations
  • Convex Programming
  • Engineering
  • Equations
  • Geometry
  • Industrial Engineering
  • Inequalities
  • Linear Programming
  • Military Research
  • Numbers
  • Operations Research
  • Optimization
  • Quadratic Programming
  • Simplex Method

Fields of Study

  • Mathematics

Readers

  • Operations Research