$Q$-fully Quadratic Modeling and its Application in a Random Subspace Derivative-free Method
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916007319175168 |
|---|---|
| author | Chen, Yiwen Hare, Warren Wiebe, Amy |
| author_facet | Chen, Yiwen Hare, Warren Wiebe, Amy |
| contents | Model-based derivative-free optimization (DFO) methods are an important class of DFO methods that are known to struggle with solving high-dimensional optimization problems. Recent research has shown that incorporating random subspaces into model-based DFO methods has the potential to improve their performance on high-dimensional problems. However, most of the current theoretical and practical results are based on linear approximation models due to the complexity of quadratic approximation models. This paper proposes a random subspace trust-region algorithm based on quadratic approximations. Unlike most of its precursors, this algorithm does not require any special form of objective function. We study the geometry of sample sets, the error bounds for approximations, and the quality of subspaces. In particular, we provide a technique to construct $Q$-fully quadratic models, which is easy to analyze and implement. We present an almost-sure global convergence result of our algorithm and give an upper bound on the expected number of iterations to find a sufficiently small gradient. We also develop numerical experiments to compare the performance of our algorithm using both linear and quadratic approximation models. The numerical results demonstrate the strengths and weaknesses of using quadratic approximations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_03169 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | $Q$-fully Quadratic Modeling and its Application in a Random Subspace Derivative-free Method Chen, Yiwen Hare, Warren Wiebe, Amy Optimization and Control 90C56, 65K05, 90C06 Model-based derivative-free optimization (DFO) methods are an important class of DFO methods that are known to struggle with solving high-dimensional optimization problems. Recent research has shown that incorporating random subspaces into model-based DFO methods has the potential to improve their performance on high-dimensional problems. However, most of the current theoretical and practical results are based on linear approximation models due to the complexity of quadratic approximation models. This paper proposes a random subspace trust-region algorithm based on quadratic approximations. Unlike most of its precursors, this algorithm does not require any special form of objective function. We study the geometry of sample sets, the error bounds for approximations, and the quality of subspaces. In particular, we provide a technique to construct $Q$-fully quadratic models, which is easy to analyze and implement. We present an almost-sure global convergence result of our algorithm and give an upper bound on the expected number of iterations to find a sufficiently small gradient. We also develop numerical experiments to compare the performance of our algorithm using both linear and quadratic approximation models. The numerical results demonstrate the strengths and weaknesses of using quadratic approximations. |
| title | $Q$-fully Quadratic Modeling and its Application in a Random Subspace Derivative-free Method |
| topic | Optimization and Control 90C56, 65K05, 90C06 |
| url | https://arxiv.org/abs/2312.03169 |