An O(n(3)L) Primal-Dual Interior Point Algorithm for Linear Programming.

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1987
Accession Number
ADA183792

Entities

People

  • I. Adler
  • R. C. Monteiro

Organizations

  • University of California, Berkeley

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Arithmetic
  • Blood Coagulation Factors
  • Computer Programming
  • Convergence
  • Engineering
  • Equations
  • Industrial Engineering
  • Inequalities
  • Iterations
  • Linear Programming
  • Military Research
  • Notation
  • Operations Research
  • Quadratic Programming
  • Standards
  • United States

Fields of Study

  • Mathematics

Readers

  • Operations Research