Skip to main content


eCommons@Cornell >
Cornell University Graduate School >
Cornell Theses and Dissertations >

Please use this identifier to cite or link to this item:
Title: Efficient Optimization Of Computationally Expensive Problems Using A New Parallel Algorithm And Response Surface Based Methods
Authors: Singh, Amandeep
Keywords: Parallel
Mixed Integer
Radial Basis Functions
Issue Date: 31-May-2011
Abstract: This thesis concerns the development and implementation of efficient optimization algorithms for simulation based functions (real world problems) that are computationally expensive to evaluate. The first contribution is a new parallel algorithm, RODDS for global optimization. RODDS algorithm is a stochastic heuristic global search algorithm, which effectively uses multi-core computers to reduce the computational expense of an optimization problem. The RODDS algorithm introduces the use of hyperspheres in candidate point generation. The optimization search is based on the concept of dynamically changing the dimensions perturbed to direct the search from a global to a local focus. Hyperspheres are used to prevent clustering of candidate points in optimization process to efficiently search the domain. We present numerical results on test problems as well as real world application problems from environmental engineering (groundwater management and watershed calibration) to document RODDS effectiveness when the computational budget is limited. RODDS algorithm achieves efficiencies greater than 1 for most applications which is very significant since implementation of parallel processing usually results in efficiency well below 1. We also present numerical results to show the efficiency of the use of hyperspheres in candidate point generation in RODDS by comparing with a parallel implementation without the hyperspheres. The next contribution is application of Radial basis function (RBF) based methods on computationally expensive optimization problems. We compare the performance of RBF methods with several popular global optimization algorithms (derivative based and heuristic) on two Groundwater superfund remediation sites (Pump and Treat system). These are two field sites Umatilla Chemical Depot (19,728 acres) and Blaine Ammunition Depot (48,800 acres). We present numerical results to indicate that RBF based methods are much more effective algorithms for computationally expensive groundwater problems, followed by a heuristic algorithm DDS. Under limited budget RBF based methods on average outperform traditional methods by an order of 100. The third contribution is a new methodology of integrating a new integer value optimizer (Search over Integers with Tabu (SIT)) with continuous value optimizer (RBF based method) to solve fixed cost problems (which are Mixed Integer value problems, MIVP). Mixed integer value problems (MIVP) in general have large search domain thus the optimization process is computationally very expensive. This approach tries to take advantage of the fact that SIT is effective for optimizing discrete variables, while response surface method is much more efficient for optimizing continuous value variables. This study tries to limit the computational expense of such kind of problems by implementing a Sequential Response Surface method in conjunction with SIT. We present numerical results to show the effectiveness of integration methodology in comparison to Genetic Algorithm based NSGA-II (Deb et. al., 2003) and the MIVP optimizer, NOMAD (Abramson et. al. 2008). The SIT-RBF methodology is shown to be distinctly better than GA (SIT-RBF resulting in 150 times better solution than GA) under limited computational budget.
Committee Chair: Shoemaker, Christine Ann
Committee Member: Diamessis, Peter J.
Liu, Philip Li-Fan
Discipline: Civil & Environmental Engr
Degree Name: Ph.D. of Civil & Environmental Engr
Degree Level: Doctor of Philosophy
Degree Grantor: Cornell University
No Access Until: 2016-09-29
Appears in Collections:Cornell Theses and Dissertations

Files in This Item:

File Description SizeFormat
as547thesisPDF.pdf1.55 MBAdobe PDFView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us