Gradient Surfing: A New Deterministic Approach for Low-Dimensional Global Optimization

Efrat Taig () and Ohad Ben-Shahar ()
Additional contact information
Efrat Taig: Ben-Gurion University of the Negev
Ohad Ben-Shahar: Ben-Gurion University of the Negev

Journal of Optimization Theory and Applications, 2019, vol. 180, issue 3, No 10, 855-878

Abstract: Abstract We describe a novel global optimization technique which utilizes global minima basins of attraction in order to quickly converge to a global minima. A key to the proposed method is the “steeper goes deeper” heuristic: coupling between magnitudes of gradients on different level sets of a basin of attraction and the depth of its minima. Local minima are avoided with a combination of local optimization and a heuristic-based leaping step. Gradient surfing performance is evaluated across a set of small-scale problems from the literature, and results are compared to those of 12 previously published methods. A practical six-dimensional non-convex image registration application is presented as well, where GS performance exceeds that of classic global optimization methods in both speed and accuracy. Additionally, we validate the optimization method by applying a new Gaussian mixture model benchmark for non-convex function. Finally, the “steeper goes deeper” heuristic is validated empirically on five different classes of non-convex functions using two different evaluation approaches. In all cases, steeper gradients are shown to lead to deeper optima with a high probability.

Keywords: Global optimization; Local optimization; Basin of attraction; Level set; Gradient descent (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10957-018-1397-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:joptap:v:180:y:2019:i:3:d:10.1007_s10957-018-1397-z

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-018-1397-z

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().