DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click HERE
to register or log in.
An O(n(3)L) Primal-Dual Interior Point Algorithm for Linear Programming.
CALIFORNIA UNIV BERKELEY OPERATIONS RESEARCH CENTER
Pagination or Media Count:
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.
APPROVED FOR PUBLIC RELEASE