NASA Logo

NTRS

NTRS - NASA Technical Reports Server

Back to Results
An algorithm for the solution of dynamic linear programsThe algorithm's objective is to efficiently solve Dynamic Linear Programs (DLP) by taking advantage of their special staircase structure. This algorithm constitutes a stepping stone to an improved algorithm for solving Dynamic Quadratic Programs, which, in turn, would make the nonlinear programming method of Successive Quadratic Programs more practical for solving trajectory optimization problems. The ultimate goal is to being trajectory optimization solution speeds into the realm of real-time control. The algorithm exploits the staircase nature of the large constraint matrix of the equality-constrained DLPs encountered when solving inequality-constrained DLPs by an active set approach. A numerically-stable, staircase QL factorization of the staircase constraint matrix is carried out starting from its last rows and columns. The resulting recursion is like the time-varying Riccati equation from multi-stage LQR theory. The resulting factorization increases the efficiency of all of the typical LP solution operations over that of a dense matrix LP code. At the same time numerical stability is ensured. The algorithm also takes advantage of dynamic programming ideas about the cost-to-go by relaxing active pseudo constraints in a backwards sweeping process. This further decreases the cost per update of the LP rank-1 updating procedure, although it may result in more changes of the active set that if pseudo constraints were relaxed in a non-stagewise fashion. The usual stability of closed-loop Linear/Quadratic optimally-controlled systems, if it carries over to strictly linear cost functions, implies that the saving due to reduced factor update effort may outweigh the cost of an increased number of updates. An aerospace example is presented in which a ground-to-ground rocket's distance is maximized. This example demonstrates the applicability of this class of algorithms to aerospace guidance. It also sheds light on the efficacy of the proposed pseudo constraint relaxation scheme.
Document ID
19900013710
Acquisition Source
Legacy CDMS
Document Type
Conference Paper
Authors
Psiaki, Mark L.
(Cornell Univ. Ithaca, NY, United States)
Date Acquired
September 6, 2013
Publication Date
December 15, 1989
Publication Information
Publication: JPL, Proceedings of the 3rd Annual Conference on Aerospace Computational Control, Volume 1
Subject Category
Computer Programming And Software
Accession Number
90N23026
Funding Number(s)
CONTRACT_GRANT: NAG1-1009
Distribution Limits
Public
Copyright
Work of the US Gov. Public Use Permitted.
No Preview Available