Nesterov's method of dichotomy via Order Oracle: The problem of optimizing a two-variable function on a square
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910611989856256 |
|---|---|
| author | Chervonenkis, Boris Krasnov, Andrei Gasnikov, Alexander Lobanov, Aleksandr |
| author_facet | Chervonenkis, Boris Krasnov, Andrei Gasnikov, Alexander Lobanov, Aleksandr |
| contents | The challenges of black box optimization arise due to imprecise responses and limited output information. This article describes new results on optimizing multivariable functions using an Order Oracle, which provides access only to the order between function values and with some small errors. We obtained convergence rate estimates for the one-dimensional search method (golden ratio method) under the condition of oracle inaccuracy, as well as convergence results for the algorithm on a "square" (also with noise), which outperforms its alternatives. The results obtained are similar to those in problems with oracles providing significantly more information about the optimized function. Additionally, the practical application of the algorithm has been demonstrated in maximizing a preference function, where the parameters are the acidity and sweetness of the drink. This function is expected to be convex or at least quasi-convex. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_11077 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Nesterov's method of dichotomy via Order Oracle: The problem of optimizing a two-variable function on a square Chervonenkis, Boris Krasnov, Andrei Gasnikov, Alexander Lobanov, Aleksandr Optimization and Control The challenges of black box optimization arise due to imprecise responses and limited output information. This article describes new results on optimizing multivariable functions using an Order Oracle, which provides access only to the order between function values and with some small errors. We obtained convergence rate estimates for the one-dimensional search method (golden ratio method) under the condition of oracle inaccuracy, as well as convergence results for the algorithm on a "square" (also with noise), which outperforms its alternatives. The results obtained are similar to those in problems with oracles providing significantly more information about the optimized function. Additionally, the practical application of the algorithm has been demonstrated in maximizing a preference function, where the parameters are the acidity and sweetness of the drink. This function is expected to be convex or at least quasi-convex. |
| title | Nesterov's method of dichotomy via Order Oracle: The problem of optimizing a two-variable function on a square |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2409.11077 |