An optimally fast objective-function-free minimization algorithm using random subspaces
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_ | 1866915128490852352 |
|---|---|
| author | Bellavia, S. Gratton, S. Morini, B. Toint, Ph. L. |
| author_facet | Bellavia, S. Gratton, S. Morini, B. Toint, Ph. L. |
| contents | An algorithm for unconstrained non-convex optimization is described, which does not evaluate the objective function and in which minimization is carried out, at each iteration, within a randomly selected subspace. It is shown that this random approximation technique does not affect the method's convergence nor its evaluation complexity for the search of an $ε$-approximate first-order critical point, which is $\mathcal{O}(ε^{-(p+1)/p})$, where $p$ is the order of derivatives used. A variant of the algorithm using approximate Hessian matrices is also analysed and shown to require at most $\mathcal{O}(ε^{-2})$ evaluations. Preliminary numerical tests show that the random-subspace technique can significantly improve performance when used with $p=2$ in the correct context, making it very competitive when compared to standard first-order algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_16580 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | An optimally fast objective-function-free minimization algorithm using random subspaces Bellavia, S. Gratton, S. Morini, B. Toint, Ph. L. Optimization and Control 60G99, 65K05, 68M20, 68Q17, 90C26 G.6.1; F.2.1 An algorithm for unconstrained non-convex optimization is described, which does not evaluate the objective function and in which minimization is carried out, at each iteration, within a randomly selected subspace. It is shown that this random approximation technique does not affect the method's convergence nor its evaluation complexity for the search of an $ε$-approximate first-order critical point, which is $\mathcal{O}(ε^{-(p+1)/p})$, where $p$ is the order of derivatives used. A variant of the algorithm using approximate Hessian matrices is also analysed and shown to require at most $\mathcal{O}(ε^{-2})$ evaluations. Preliminary numerical tests show that the random-subspace technique can significantly improve performance when used with $p=2$ in the correct context, making it very competitive when compared to standard first-order algorithms. |
| title | An optimally fast objective-function-free minimization algorithm using random subspaces |
| topic | Optimization and Control 60G99, 65K05, 68M20, 68Q17, 90C26 G.6.1; F.2.1 |
| url | https://arxiv.org/abs/2310.16580 |