An Implementation of the Projective Algorithm for Linear Programming.
NAVAL POSTGRADUATE SCHOOL MONTEREY CA
Pagination or Media Count:
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.
- Statistics and Probability