Uncomputability of Global Optima for Nonconvex Functions in the Oracle Model

K Lakshmanan

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 mode…