Can someone tell if it is known that if finding global optima is unsolvable (in Turing sense). I have posted an arXiv paper https://arxiv.org/pdf/2103.13821.pdf showing this. But I'm not sure if it is already known.
General global optimisation problems are solvable in finite time and in a finite number of steps, under the following assumptions:
- All mathematical expressions are available (i.e. not black-box problems). We use those to produce rigorous bounds that improve deterministically.
- The primitives do not include functions that cannot be bounded properly (in the general case), such as error functions, integrals, or differentials.
- The underlying software/hardware supports bounding numerical error rigorously, and the software is bug-free.
In the general case, unless these assumptions hold, an arbitrary global optimisation problem can be solved in infinite time, unless it is bounded and discrete in which case the solutions can be enumerated in finite time.
Note that "solving" a global optimisation problem means not only finding the global solution, but also proving that it is the global solution.
Further note that "finite time" or "finite number of steps" often mean little in practice, as said finite time can be trillions of years. An "infinite time" algorithm can often outperform a finite time algorithm in practice.
I had a look at your paper. Here are two errors that I think are worth reflecting about:
- You are assuming computations in finite precision, and consider solving a continous optimization problem. We could stop there: it is impossible to represent an arbitrary real number with finite precision. Most works in continuous optimization assume an abstract computation model with arithmetic over the real numbers. Others may consider problems that are solvable over the rational numbers, that can indeed be represented by a Turing machine.
- A Turing machine may halt/not halt on infinitely many inputs. Consider one that detects odd numbers, for example.
Don't let a few errors discourage you. If you are interested in the mathematical aspects of optimization, I suggest you do not start right away looking for new theorems. Online courses are a good way to know the basics (MIT's opencourseware comes to mind), but a direct contact with the academic community is a must if you want to do research in the field.