Accession Number:

ADA162048

Title:

An Implementation of the Projective Algorithm for Linear Programming.

Descriptive Note:

Master's thesis,

Corporate Author:

NAVAL POSTGRADUATE SCHOOL MONTEREY CA

Personal Author(s):

Report Date:

1985-09-01

Pagination or Media Count:

44.0

Abstract:

An algorithm to solve linear programming problems is presented in this thesis which is based on Karmarkars projective method. The algorithm includes a practical method to project a general linear programming problem onto a unit simplex and eliminates the a priori need to know the optimal value of the objective function. The implementation conserves sparsity. The key part of the implementation is the solution of a linear least-squares problem to find an improving direction a direct and an iterative method are implemented to solve this problem. The direct method employs the minimum-degree heuristic to reorder the system of normal equations, and thus conserve sparsity during the following Cholesky factor of the normal equation matrix as a preconditioner for conjugate gradient iterations which are performed implicity on the preconditioned matrix. The study concludes with implementation remarks, and computational results.

Subject Categories:

  • Statistics and Probability

Distribution Statement:

APPROVED FOR PUBLIC RELEASE