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.

Report Date:

1987-05-01

Pagination or Media Count:

31.0

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