Uncomputability of Global Optima for Nonconvex Functions in the Oracle Model
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909555513884672 |
|---|---|
| author | Lakshmanan, K |
| author_facet | Lakshmanan, K |
| contents | While it is well known that finding approximate optima of non-convex functions is computationally intractable, we show that the problem is, in fact, uncomputable in the oracle model. Specifically, we prove that no algorithm with access only to a function oracle can compute the global minimum or even an $ε$-approximation of the minimizer or minimal value. We then characterize a necessary and sufficient condition under which global optima become computable, based on the existence of a computable predicate that subsumes the global optimality condition. As an illustrative example, we consider the basin of attraction around a global minimizer as such a property and propose a simple algorithm that converges to the global minimum when a bound on the basin is known. Finally, we provide numerical experiments on standard benchmark functions to demonstrate the algorithm's practical performance. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_09436 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Uncomputability of Global Optima for Nonconvex Functions in the Oracle Model Lakshmanan, K Optimization and Control 68Q17, 90C26 While it is well known that finding approximate optima of non-convex functions is computationally intractable, we show that the problem is, in fact, uncomputable in the oracle model. Specifically, we prove that no algorithm with access only to a function oracle can compute the global minimum or even an $ε$-approximation of the minimizer or minimal value. We then characterize a necessary and sufficient condition under which global optima become computable, based on the existence of a computable predicate that subsumes the global optimality condition. As an illustrative example, we consider the basin of attraction around a global minimizer as such a property and propose a simple algorithm that converges to the global minimum when a bound on the basin is known. Finally, we provide numerical experiments on standard benchmark functions to demonstrate the algorithm's practical performance. |
| title | Uncomputability of Global Optima for Nonconvex Functions in the Oracle Model |
| topic | Optimization and Control 68Q17, 90C26 |
| url | https://arxiv.org/abs/2401.09436 |