Interplanetary multiple gravity assist (MGA) trajectory optimization has long been a field of interest to space scientists and engineers. Gravity assist maneuvers alter a spacecraft's velocity vector and potentially allow spacecraft to achieve changes in velocity which would otherwise be unfeasible given our current technological limitations. Unfortunately, designing MGA trajectories is difficult and in order to find good solutions, deep space maneuvers (DSM) are often required which further increase the complexity of the problem. In addition, despite the active research in the field over the last 50 years, software for MGA trajectory optimization is scarce. A few good commercial, and even fewer open-source, options exist, but a majority of quality software remains proprietary. The intent of this thesis is twofold. The first part of this work explores the realm of global optimization applied to multiple gravity assist trajectories with deep space maneuvers (MGA-DSM). With the constant influx of new global optimization algorithms and heuristics being developed in the global optimization community, this work aims to be a high level optimization approach which makes use of those algorithms instead of trying to be one itself. Central to this approach is PaGMO, which is the open-source Parallel Multiobjective Global Optimizer created by ESA's Advanced Concepts Team (ACT). PaGMO is an implementation of the Island Model Paradigm which allows the parallelization of different global optimizers. The second part of this work introduces the IGATO software which improves PaGMO by complementing it with dynamic restart capabilities, a pruning algorithm which learns over time, subdomain decomposition, and other techniques to create a powerful optimization tool. IGATO aims to be an open-source platform independent C++ application with a robust graphical user interface (GUI). The application is equipped with 2D plotting and simulations, real time Porkchop Plot generation, and other useful features for analyzing various problems. The optimizer is tested on several challenging MGA-DSM problems and performs well: consistently performing as well or better than PaGMO on its own.

Many chemical engineering applications, such as safety verification and parameter estimation, require global optimization of dynamic models. Global optimization algorithms typically require obtaining global bounding information of the dynamic system, to aid in locating and verifying the global optimum. The typical approach for providing these bounds is to generate convex relaxations of the dynamic system and minimize them using a local optimization solver. Tighter convex relaxations typically lead to tighter lower bounds, so that the number of iterations in global optimization algorithms can be reduced. To carry out this local optimization efficiently, subgradient-based solvers require gradients or subgradients to be furnished. Smooth convex relaxations would aid local optimization even more. To address these issues and improve the computational performance of global dynamic optimization, this thesis proposes several novel formulations for constructing tight convex relaxations of dynamic systems. In some cases, these relaxations are smooth. Firstly, a new strategy is developed to generate convex relaxations of implicit functions, under minimal assumptions. These convex relaxations are described by parametric programs whose constraints are convex relaxations of the residual function. Compared with established methods for relaxing implicit functions, this new approach does not assume uniqueness of the implicit function and does not require the original residual function to be factorable. This new strategy was demonstrated to construct tighter convex relaxations in multiple numerical examples. Moreover, this new convex relaxation strategy extends to inverse functions, feasible-set mappings in constraint satisfaction problems, as well as parametric ordinary differential equations (ODEs). Using a proof-of-concept implementation in Julia, numerical examples are presented to illustrate the convex relaxations produced for various implicit functions and optimal-value functions. In certain cases, these convex relaxations are tighter than those generated with existing methods. Secondly, a novel optimization-based framework is introduced for computing time-varying interval bounds for ODEs. Such interval bounds are useful for constructing convex relaxations of ODEs, and tighter interval bounds typically translate into tighter convex relaxations. This framework includes several established bounding approaches, but also includes many new approaches. Some of these new methods can generate tighter interval bounds than established methods, which are potentially helpful for constructing tighter convex relaxations of ODEs. Several of these approaches have been implemented in Julia. Thirdly, a new approach is developed to improve a state-of-the-art ODE relaxation method and generate tighter and smooth convex relaxations. Unlike state-of-the-art methods, the auxiliary ODEs used in these new methods for computing convex relaxations have continuous right-hand side functions. Such continuity not only makes the new methods easier to implement, but also permits the evaluation of the subgradients of convex relaxations. Under some additional assumptions, differentiable convex relaxations can be constructed. Besides that, it is demonstrated that the new convex relaxations are at least as tight as state-of-the-art methods, which benefits global dynamic optimization. This approach has been implemented in Julia, and numerical examples are presented. Lastly, a new approach is proposed for generating a guaranteed lower bound for the optimal solution value of a nonconvex optimal control problem (OCP). This lower bound is obtained by constructing a relaxed convex OCP that satisfies the sufficient optimality conditions of Pontryagin's Minimum Principle. Such lower bounding information is useful for optimizing the original nonconvex OCP to a global minimum using deterministic global optimization algorithms. Compared with established methods for underestimating nonconvex OCPs, this new approach constructs tighter lower bounds. Moreover, since it does not involve any numerical approximation of the control and state trajectories, it provides lower bounds that are reliable and consistent. This approach has been implemented for control-affine systems, and numerical examples are presented. / Thesis / Doctor of Philosophy (PhD)

Ph. D. Thesis / In order to compute more realistic production plans and schedules, techniques using nonlinear programming (NLP) and mixed-integer nonlinear programming (MINLP) have gathered a lot of attention from the industry and academy. Efficient solution of these problems to a proven ε-global optimality remains a challenge due to their combinatorial, nonconvex, and large dimensionality attributes. The key contributions of this work are: 1) the generalization of the inventory pinch decomposition method to scheduling problems, and 2) the development of a deterministic global optimization method. An inventory pinch is a point at which the cumulative total demand touches its corresponding concave envelope. The inventory pinch points delineate time intervals where a single fixed set of operating conditions is most likely to be feasible and close to the optimum. The inventory pinch method decomposes the original problem in three different levels. The first one deals with the nonlinearities, while subsequent levels involve only linear terms by fixing part of the solution from previous levels. In this heuristic method, infeasibilities (detected via positive value of slack variables) are eliminated by adding at the first level new period boundaries at the point in time where infeasibilities are detected. The global optimization algorithm presented in this work utilizes both piecewise McCormick (PMCR) and Normalized Multiparametric Disaggregation (NMDT), and employs a dynamic partitioning strategy to refine the estimates of the global optimum. Another key element is the parallelized bound tightening procedure. Case studies include gasoline blend planning and scheduling, and refinery planning. Both inventory pinch method and the global optimization algorithm show promising results and their performance is either better or on par with other published techniques and commercial solvers, as exhibited in a number of test cases solved during the course of this work. / Thesis / Doctor of Philosophy (PhD) / Optimal planning and scheduling of production systems are two very important tasks in industrial practice. Their objective is to ensure optimal utilization of raw materials and equipment to reduce production costs. In order to compute realistic production plans and schedules, it is often necessary to replace simplified linear models with nonlinear ones including discrete decisions (e.g., “yes/no”, “on/off”). To compute a global optimal solution for this type of problems in reasonable time is a challenge due to their intrinsic nonlinear and combinatorial nature. The main goal of this thesis is the development of efficient algorithms to solve large-scale planning and scheduling problems. The key contributions of this work are the development of: i) a heuristic technique to compute near-optimal solutions rapidly, and ii) a deterministic global optimization algorithm. Both approaches showed results and performances better or equal to those obtained by commercial software and previously published methods.

There are many challenges that need to be met before efficient and reliable computation at the petascale is possible. Many scientific and engineering codes running at the petascale are likely to be memory intensive, which makes thrashing a serious problem for many petascale applications. One way to overcome this challenge is to use a dynamic number of processes, so that the total amount of memory available for the computation can be increased on demand. This thesis describes modifications made to the massively parallel global optimization code pVTdirect in order to allow for a dynamic number of processes. In particular, the modified version of the code monitors memory use and spawns new processes if the amount of available memory is determined to be insufficient. The primary design challenges are discussed, and performance results are presented and analyzed. / Master of Science

Green computing, an emerging field of research that seeks to reduce excess power consumption in high performance computing (HPC), is gaining popularity among researchers. Research in this field often relies on simulation or only uses a small cluster, typically 8 or 16 nodes, because of the lack of hardware support. In contrast, System G at Virginia Tech is a 2592 processor supercomputer equipped with power aware components suitable for large scale green computing research. DIRECT is a deterministic global optimization algorithm, implemented in the mathematical software package VTDIRECT95. This thesis explores the potential energy savings for the parallel implementation of DIRECT, called pVTdirect, when used with a large scale computational biology application, parameter estimation for a budding yeast cell cycle model, on System G. Two power aware approaches for pVTdirect are developed and compared against the CPUSPEED power saving system tool. The results show that knowledge of the parallel workload of the underlying application is beneficial for power management. / Master of Science

Ever since the advent of the simplex algorithm, linear programming (LP) has been extensively used with great success in many diverse fields. The field of discrete optimization came to the forefront as a result of the impressive developments in the area of linear programming. Although discrete optimization problems can be viewed as belonging to the class of nonconvex programs, it has only been in recent times that optimization research has confronted the more formidable class of continuous nonconvex optimization problems, where the objective function and constraints are often highly nonlinear and nonconvex functions, defined in terms of continuous (and bounded) decision variables. Typical classes of such problems involve polynomial, or more general factorable functions. This dissertation focuses on employing the Reformulation-Linearization Technique (RLT) to enhance model formulations and to design effective solution techniques for solving several practical instances of continuous nonconvex optimization problems, namely, the hard and fuzzy clustering problems, risk management problems, and problems arising in control systems. Under the umbrella of the broad RLT framework, the contributions of this dissertation focus on developing models and algorithms along with related theoretical and computational results pertaining to three specific application domains. In the basic construct, through appropriate surrogation schemes and variable substitution strategies, we derive strong polyhedral approximations for the polynomial functional terms in the problem, and then rely on the demonstrated (robust) ability of the RLT for determining global optimal solutions for polynomial programming problems. The convergence of the proposed branch-and-bound algorithm follows from the tailored branching strategy coupled with consistency and exhaustive properties of the enumeration tree. First, we prescribe an RLT-based framework geared towards solving the hard and fuzzy clustering problems. In the second endeavor, we examine two risk management problems, providing novel models and algorithms. Finally, in the third part, we provide a detailed discussion on studying stability margins for control systems using polynomial programming models along with specialized solution techniques. / Ph. D.

The DIRECT (DIviding RECTangles) algorithm JONESJOTi, a variant of Lipschitzian methods for bound constrained global optimization, has been applied to the optimal transmitter placement for indoor wireless systems. Power coverage and BER (bit error rate) are considered as two criteria for optimizing locations of a specified number of transmitters across the feasible region of the design space. The performance of a DIRECT implementation in such applications depends on the characteristics of the objective function, the problem dimension, and the desired solution accuracy. Implementations with static data structures often fail in practice because of unpredictable memory requirements. This is especially critical in S⁴W (Site-Specific System Simulator for Wireless communication systems), where the DIRECT optimization is just one small component connected to a parallel 3D propagation ray tracing modeler running on a 200-node Beowulf cluster of Linux workstations, and surrogate functions for a WCDMA (wideband code division multiple access) simulator are also used to estimate the channel performance. Any component failure of this large computation would abort the entire design process. To make the DIRECT global optimization algorithm efficient and robust, a set of dynamic data structures is proposed here to balance the memory requirements with execution time, while simultaneously adapting to arbitrary problem size. The focus is on design issues of the dynamic data structures, related memory management strategies, and application issues of the DIRECT algorithm to the transmitter placement optimization for wireless communication systems. Results for two indoor systems are presented to demonstrate the effectiveness of the present work. / Master of Science

The design of water distribution systems has received a great deal of attention in the last three decades because of its importance to industrial growth and its crucial role in society for community health, firefighting capability, and quality of life. The cost of installing a water distribution system is typically in the tens of millions of dollars. These systems also account for the largest costs in the municipal maintenance budgets. Furthermore, existing systems are being burdened by increasing urban development and water use. All these factors cause the pipe sizing decisions to be a critical task in designing a cost effective water distribution system that is capable of handling the demand and satisfying the minimum pressure head and hydraulic redundancy requirements. A number of research efforts have focused on the least cost pipe sizing decision, each of them generating improved solutions for several standard test problems from literature, but so far, very little work has been done to test the quality of these solutions. In this thesis, two lower bounding schemes are proposed to evaluate the quality of these solutions. These lower bounding schemes make use of the special concave-convex nature of the nonlinear frictional loss terms. We show that the first is a dual to <i>Eiger et al.’s</i> [1994] bounding procedure while the second method produces far tighter lower bounds with comparable ease. Results on applying these lower bounding schemes to some standard test problems from literature are presented. The second lower bounding scheme is then embedded in a branch-and-bound procedure along with an upper bounding scheme by suitably restricting the flows at each node of the search tree. By branching successively, we attempt to narrow the gap from optimality to generate near optimal solutions to the least cost pipe sizing problem. This results in a comprehensive reduced cost network design that satisfies all pressure and flow requirements for realistically sized problems. The proposed method is applied to standard test problems from the literature. It is hoped that this method will provide a useful tool for city engineers to design a cost effective water distribution system that meets specified hydraulic requirements. / Master of Science

The application of stochastic modeling for learning the behavior of multibody dynamics models is investigated. The stochastic modeling technique is also known as Kriging or random function approach. Post-processing data from a simulation run is used to train the stochastic model that estimates the relationship between model inputs, such as the suspension relative displacement and velocity, and the output, for example, sum of suspension forces. Computational efficiency of Multibody Dynamics (MBD) models can be improved by replacing their computationally-intensive subsystems with stochastic predictions. The stochastic modeling technique is able to learn the behavior of a physical system and integrate its behavior in MBS models, resulting in improved real-time simulations and reduced computational effort in models with repeated substructures (for example, modeling a train with a large number of rail vehicles). Since the sampling plan greatly influences the overall accuracy and efficiency of the stochastic predictions, various sampling plans are investigated, and a space-filling Latin Hypercube sampling plan based on the traveling salesman problem (TPS) is suggested for efficiently representing the entire parameter space. The simulation results confirm the expected increased modeling efficiency, although further research is needed for improving the accuracy of the predictions. The prediction accuracy is expected to improve through employing a sampling strategy that considers the discrete nature of the training data and uses infill criteria that considers the shape of the output function and detects sample spaces with high prediction errors. It is recommended that future efforts consider quantifying the computation efficiency of the proposed learning behavior by overcoming the inefficiencies associated with transferring data between multiple software packages, which proved to be a limiting factor in this study. These limitations can be overcome by using the user subroutine functionality of SIMPACK and adding the stochastic modeling technique to its force library. / Ph. D.

With rapid growth in the complexity of large scale engineering systems, the application of multidisciplinary analysis and design optimization (MDO) in the engineering design process has garnered much attention. MDO addresses the challenge of integrating several different disciplines into the design process. Primary challenges of MDO include computational expense and poor scalability. The introduction of a distributed, collaborative computational environment results in better utilization of available computational resources, reducing the time to solution, and enhancing scalability. SORCER, a Java-based network-centric computing platform, enables analyses and design studies in a distributed collaborative computing environment. Two different optimization algorithms widely used in multidisciplinary engineering design---VTDIRECT95 and QNSTOP---are implemented on a SORCER grid. VTDIRECT95, a Fortran 95 implementation of D. R. Jones' algorithm DIRECT, is a highly parallelizable derivative-free deterministic global optimization algorithm. QNSTOP is a parallel quasi-Newton algorithm for stochastic optimization problems. The purpose of integrating VTDIRECT95 and QNSTOP into the SORCER framework is to provide load balancing among computational resources, resulting in a dynamically scalable process. Further, the federated computing paradigm implemented by SORCER manages distributed services in real time, thereby significantly speeding up the design process. Results are included for an aircraft design application. / Master of Science