An implementation of the projective algorithm for linear programming
Bretschneider, Guenter W.
Wood, R. Kevin
Brown, Gerald G.
MetadataShow full item record
An algorithm to solve linear programming problems is presented which is based on Karmarkar's 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 factorization. The iterative method uses the incomplete Cholesky factor of the normal equation matrix as a preconditioner for conjugate gradient iterations which are performed implicitly on the preconditioned matrix. The study concludes with implementation remarks, and computational results.
Approved for public release; distribution is unlimited
Showing items related by title, author, creator and subject.
Valenzuela, Zaldy M. (Monterey California. Naval Postgraduate School, 2005-06);The realization of high-speed numeric computation is a sought-after commodity for real world applications, including high-speed scientific computation, digital signal processing, and embedded computers. An example of ...
McCamish, Shawn B. (Monterey, California. Naval Postgraduate School, 2007., 2007-12);This research contributes to multiple spacecraft control by developing an autonomous distributed control algorithm for close proximity operations of multiple spacecraft systems, including rendezvous and docking scenarios. ...
McCamish, Shawn B.; Romano, Marcello; Nolet, Simon; Edwards, Christine M.; Miller, David W. (2009-12);A multiple-spacecraft close-proximity control algorithm was implemented and tested with the Synchronized Position Hold Engage and Reorient Experimental Satellites (SPHERES) facility onboard the International Space Station. ...