Statistics of Global Stochastic Optimisation: How Many Steps to Hit the Target?

Godehard Sutmann ()
Additional contact information
Godehard Sutmann: Jülich Supercomputing Centre (JSC), Forschungszentrum Jülich (FZJ), D-52425 Jülich, Germany

Mathematics, 2025, vol. 13, issue 20, 1-36

Abstract: Random walks are considered in a one-dimensional monotonously decreasing energy landscape. To reach the minimum within a region Ω ϵ , a number of downhill steps have to be performed. A stochastic model is proposed which captures this random downhill walk and to make a prediction for the average number of steps, which are needed to hit the target. Explicit expressions in terms of a recurrence relation are derived for the density distribution of a downhill random walk as well as probability distribution functions to hit a target region Ω ϵ within a given number of steps. For the case of stochastic optimisation, the number of rejected steps between two successive downhill steps is also derived, providing a measure for the average total number of trial steps. Analytical results are obtained for generalised random processes with underlying polynomial distribution functions. Finally the more general case of non-monotonously decreasing energy landscapes is considered for which results of the monotonous case are transferred by applying the technique of decreasing rearrangement . It is shown that the global stochastic optimisation can be fully described analytically, which is verified by numerical experiments for a number of different distribution and objective functions. Finally we discuss the transition to higher dimensional objective functions and discuss the change in computational complexity for the stochastic process.

Keywords: stochastic optimisation; random walks; random search (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/20/3269/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/20/3269/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:13:y:2025:i:20:p:3269-:d:1770156

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().