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.
2
-
$\begingroup$ I only know this paper which goes in a similar direction but is restricted to Mixed-Integer quadratically constrained programs and not in a Turing sense. Maybe it is still useful for you? Jeroslow, Robert C. "There cannot be any algorithm for integer programming with quadratic constraints." Operations Research 21.1 (1973): 221-224. $\endgroup$– YukiJSep 23, 2021 at 8:11
-
$\begingroup$ Thank you for the reference $\endgroup$– Lakshmanan KSep 23, 2021 at 9:24
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
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.
The field of optimisation that studies such algorithms is called deterministic global optimisation. The basics of the theory were nicely summarised by Neumaier in Acta Numerica 2004.
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.
-
$\begingroup$ Thanks for the reference. Is it the case here that function is known analytically not just by its Oracle ? $\endgroup$ Sep 27, 2021 at 23:29
-
1$\begingroup$ Yes, the function has to be known analytically. Strictly speaking, there has to exist a way to rigorously derive bounds on that function which can improve as the domain shrinks. $\endgroup$ Sep 28, 2021 at 22:23
$\begingroup$
$\endgroup$
1
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.
-
1$\begingroup$ Thanks , I'm not saying reals can be represented by finite precision or Turing machine does not halt on infinite inputs. I'm only using that there is a sequence of finite precision numbers converging to any real. $\endgroup$ Sep 27, 2021 at 23:26