Optimal hierarchical system design via sequentially decomposed programming.

Abstract

This dissertation focuses on how existing optimization algorithms can be modified to take advantage of the type of structure known as hierarchical decomposition, which is frequently found in the design of large complex engineering systems. Hierarchical decomposition allows a system design problem to be broken down into smaller distinct but related optimization problems. By modifying existing algorithms, the subproblems can be used during the solution process without hindering the convergence of the new algorithm. Three guidelines are developed for modifying general NLP algorithms to take advantage of the hierarchically decomposed structure while still retaining both global and local convergence properties of the original algorithm. They are: (1) the coordination of subproblem solutions is performed at the system level employing an approximate problem (for instance a quadratic program) which uses all of the constraints and variables in the original problem; (2) when near a solution, decomposition (i.e., solving subproblems separately) is not explicitly performed; and (3) subproblems are used not only to improve their own objective and constraints, but also to improve estimates of other parameters used by the algorithm. The modifications are applied to the sequential quadratic programming algorithm of Wilson, Han, and Powell, and to the 1995 trust region algorithm of Yuan. Although it is not possible to prove that the modified algorithm performs better, it is proven for both algorithms that global and local convergence properties are retained. The modified algorithms were implemented and applied to several small- to medium-sized design problems. Each example is solved with the original sequential quadratic programming and trust region algorithms. It is then decomposed into a hierarchical form and solved again with the modified algorithms. As problem size increases, the modified algorithms are in general more robust and find solutions with less effort.