# Uncomputability of Global Optima for Nonconvex Functions in the Oracle Model

Source: [Uncomputability of Global Optima for Nonconvex Functions in the Oracle Model](<https://www.sota2.com/research/paper/68fa5d301e209131ce9d7f2a>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-25T18:06:13.057Z

Authors: K Lakshmanan

Published: 2023-12-19T18:24:20.000Z

## Abstract

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 $\\epsilon$-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.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2401.09436>)

[PDF](<https://arxiv.org/pdf/2401.09436.pdf>)