- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Numerical analysis for derivative-free optimization
Open Collections
UBC Theses and Dissertations
UBC Theses and Dissertations
Numerical analysis for derivative-free optimization Jarry-Bolduc, Gabriel
Abstract
In many optimization problems, the objective function is available only as the output of a blackbox. In this context, derivative-free optimization (DFO) methods can be used to solve the optimization problem. Derivative-free optimization methods may be classified into two main categories: direct search methods and model-based methods. This thesis presents novel theory and algorithms in both categories. Model-based methods often approximate the gradient or the Hessian of the objective function. The properties of the gradient approximation technique called generalized simplex gradient are scrutinized. Second, two Hessian approximation techniques called generalized simplex Hessian (GSH) and generalized centered simplex Hessian (GCSH) are defined and analyzed. In particular, we investigate how to approximate partial Hessians, and minimize the number of function evaluations when employing the GSH/GCSH. A useful notion in direct search methods is that of positive spanning set. In this thesis, we present the first deterministic algorithm to compute the cosine measure of any finite positive spanning set. Then we investigate the structure of positive bases with maximal cosine measure. We focus on positive bases of intermediate sizes. Last, the main theoretical concepts discussed in this thesis are utilized in DFO algorithms. The GSH are employed in a derivative-free trust-region algorithm and positive bases with high cosine measure are employed in a direct search algorithm. We examine how the theoretical advancements made in this thesis translate to gains in efficiency in DFO algorithms.
Item Metadata
Title |
Numerical analysis for derivative-free optimization
|
Creator | |
Supervisor | |
Publisher |
University of British Columbia
|
Date Issued |
2023
|
Description |
In many optimization problems, the objective function is available only
as the output of a blackbox. In this context, derivative-free optimization
(DFO) methods can be used to solve the optimization problem. Derivative-free optimization methods may be classified into two main categories: direct
search methods and model-based methods. This thesis presents novel theory
and algorithms in both categories.
Model-based methods often approximate the gradient or the Hessian
of the objective function. The properties of the gradient approximation
technique called generalized simplex gradient are scrutinized. Second, two
Hessian approximation techniques called generalized simplex Hessian (GSH)
and generalized centered simplex Hessian (GCSH) are defined and analyzed.
In particular, we investigate how to approximate partial Hessians, and minimize the number of function evaluations when employing the GSH/GCSH.
A useful notion in direct search methods is that of positive spanning
set. In this thesis, we present the first deterministic algorithm to compute
the cosine measure of any finite positive spanning set. Then we investigate
the structure of positive bases with maximal cosine measure. We focus on
positive bases of intermediate sizes.
Last, the main theoretical concepts discussed in this thesis are utilized
in DFO algorithms. The GSH are employed in a derivative-free trust-region
algorithm and positive bases with high cosine measure are employed in a
direct search algorithm. We examine how the theoretical advancements
made in this thesis translate to gains in efficiency in DFO algorithms.
|
Genre | |
Type | |
Language |
eng
|
Date Available |
2023-07-24
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
DOI |
10.14288/1.0434276
|
URI | |
Degree | |
Program | |
Affiliation | |
Degree Grantor |
University of British Columbia
|
Graduation Date |
2023-09
|
Campus | |
Scholarly Level |
Graduate
|
Rights URI | |
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International