Talk:Stochastic optimization

Paragraph on probabilistic complexity, no free lunch, and Turing-completeness of stochastic local search recently removed: a volunteer to review its suitability?

User MrOllie has recently removed my contributions about the probabilistic classes, the No Free Lunch theorem, and the Turing-completeness of stochastic local search algorithms arguing citation spam. I would like to ask a volunteer to review the relevance to these contents, which were reverted by MrOllie at 23:03, 20 February 2024‎ (UTC). EXPTIME-complete (talk) 23:47, 20 February 2024 (UTC)

In particular, this is the text I would like to introduce again:

In fact, some important open problems in Complexity involve finding out whether randomness allows to solve problems in shorter time (e.g. the P = BPP problem). Sometimes the convergence of stochastic local search algorithm to the optimal solution comes as a direct consequence of the fact that, at each iteration, the algorithm has a probability greater than zero of jumping from any solution to any other solution in the search space, so the optimal solution will eventually be found. If no additional conditions can be taken into account, then the average time to find the solution of that random search is the same as if an exhaustive search were performed. The No free lunch theorem for optimization establishes conditions under which the computational cost of finding a solution, averaged over all problems in the class, is the same for any solution method. Moreover, it has been proved that essential semantic properties of stochastic local search algorithms such as e.g. whether they will find the optimal solution or a solution at some distance of the optimal value are undecidable in general. The reason for this is that these algorithms can simulate any program (i.e. they are Turing-complete) —in particular, also if their basic ingredients (e.g. fitness function, crossover and mutation operators, etc.) are required to be very simple.

This text was introduced right after the following paragraph, which remains in the current version:

In contrast, some authors have argued that randomization can only improve a deterministic algorithm if the deterministic algorithm was poorly designed in the first place.[21] Fred W. Glover[22] argues that reliance on random elements may prevent the development of more intelligent and better deterministic components. The way in which results of stochastic optimization algorithms are usually presented (e.g., presenting only the average, or even the best, out of N runs without any mention of the spread), may also result in a positive bias towards randomness.

References