eCommons

 

Derivative-Free Optimization Algorithms For Computationally Expensive Functions

Other Titles

Abstract

This thesis concerns the development and analysis of derivative-free optimization algorithms for simulation-based functions that are computationally expensive to evaluate.

The first contribution is the introduction of data profiles as a tool for analyzing the performance of derivative-free optimization solvers when constrained by a computational budget. Using these profiles, together with a convergence test that measures the decrease in function value, we find that on three different sets of test problems, a model-based solver performs better than the two direct search solvers tested.

The next contribution is a new model-based derivative-free algorithm, ORBIT, for unconstrained local optimization. A trust-region framework using interpolating Radial Basis Function (RBF) models is employed. RBF models allow ORBIT to interpolate nonlinear functions using fewer function evaluations than many of the polynomial models considered by present techniques. We provide an analysis of the approximation guarantees obtained by interpolating the function at a set of sufficiently affinely independent points. We detail necessary and sufficient conditions that an RBF model must obey to fit within our framework and prove that this framework allows for convergence to first-order critical points. We present numerical results on test problems as well as three application problems from environmental engineering to support ORBIT's effectiveness when relatively few function evaluations are available. The framework used by ORBIT is also extended to include other models, in particular undetermined interpolating quadratics. These quadratics are flexible in their ability to interpolate at dynamic numbers of previously evaluated points.

The third contribution is a new multistart global optimization algorithm, GORBIT, that takes advantage of the expensive function evaluations done in the course of both the global exploration and local refinement phases. We modify ORBIT to handle both bound constraints and external functional evaluations and use it as the local solver. For the global exploration phase, a new procedure for making maximum use of the information from previous evaluations, MIPE, is introduced. Numerical tests motivating our approach are presented and we illustrate using GORBIT on the problem of finding error-prone systems for Gaussian elimination.

Journal / Series

Volume & Issue

Description

Sponsorship

Date Issued

2008-08-26T15:09:26Z

Publisher

Keywords

Derivative-Free Optimization; Nonlinear Programming; Global Optimization; Computational Budget

Location

Effective Date

Expiration Date

Sector

Employer

Union

Union Local

NAICS

Number of Workers

Committee Chair

Committee Co-Chair

Committee Member

Degree Discipline

Degree Name

Degree Level

Related Version

Related DOI

Related To

Related Part

Based on Related Item

Has Other Format(s)

Part of Related Item

Related To

Related Publication(s)

Link(s) to Related Publication(s)

References

Link(s) to Reference(s)

Previously Published As

Government Document

ISBN

ISMN

ISSN

Other Identifiers

Rights

Rights URI

Types

dissertation or thesis

Accessibility Feature

Accessibility Hazard

Accessibility Summary

Link(s) to Catalog Record