The Non-Linear PARallel OPtimization Tool (NLPAROPT): A Software Overview and Efficiency Analysis

[摘要] Modern spacecraft trajectory mission planning regularly involves some component of numerical optimization to provide a significant improvement in a solution, and in some instances is the only manner for finding an acceptable solution to a problem. One of the most useful constrained optimization formulations is the Non-Linear Programming (NLP) problem. NLP problem solvers have been used to analyze complex optimization problems by space mission designers as well as a wide variety of other fields such as economics and city planning.There are several state-of-the-art software packages that are currently used to solve NLPs in the aerospace industry, such as SNPOT, IPOPT, and WORHP. Most of the critical space trajectory design software tools in use today, such as OTIS, EMTG, and MALTO, are dependent on a drop-in NLP solver (typically SNOPT or IPOPT); this dependence is not unwarranted, as the existing solvers are especially adept at solving very large-scale, preferably sparse, non-linear programming problems. However, neither SNOPT nor any other NLP solver available exploits parallel programming techniques. Most trajectory design tools have already started to implement parallel techniques, and it is now the serial-execution nature of the existing packages that represents the largest bottleneck. A high-fidelity trajectory optimization NLP can take days, weeks, or even months before converging to a solution, resulting in a prohibitively expensive mission planning design tool, both in terms of time and cost. CU Aerospace in partnership with the University of Illinois at Urbana-Champaign (UIUC) has developed a novel, ground-up redesign NLP solver that takes advantage of high performance parallel computing called the Non-Linear PARallel Optimization Tool (NLPAROPT). NLPAROPT utilizes the Boost.MPI library, a message-passing interface that allows for point-to-point communication among the processors, as well as the Linear Algebra PACKAGE (LAPACK) and the Basic Linear Algebra Subprogram (BLAS) functions to carry out complex linear algebra calculations in a parallel fashion. Preliminary tests have shown NLPAROPT’s ability to reduce the runtime by orders of magnitude when compared to its serial counterpart. A full discussion of NLPAROPT’s speed-up results can be found in the SBIR Phase I final report [1].The primary topics of this thesis are a software overview followed by an in-depth analysis of NLPAROPT’s efficiency. A trade-off analysis was conducted to determine the optimal number of processors to run a given problem with a certain computational complexity measured in Floating Point OPerations (FLOPs). Additionally, a series of algorithms were developed in MATLAB to output the optimal number of two-dimensional block-cyclic blocking factors to ensure the processor idling time is minimized, thereby minimizing the overall runtime of the program. The results of using optimal versus non-optimal blocking factors have proven the processor idling time is significantly reduced. Based on these analyses, any astrodynamics researcher can use the trends from these results to efficiently run any optimization problem in NLPAROPT.NLPAROPT already shows great promise as a rapid, robust NLP solver. Unexplored parallelization opportunities still exist within NLPAROPT. After these parallelization techniques have been implemented and the core algorithm is further refined, NLPAROPT will be transparently usable by the existing optimal trajectory solvers used by astrodynamicists, scientists, and researchers of all kinds across the globe.

[效力级别] Astrodynamics

[关键词] Aerospace;Astrodynamics;Nonlinear Programming;Message Passing Interface (MPI);Compute Unified Device Architecture (CUDA);Non-Linear PARallel Optimization Tool (NLPAROPT);optimization