Minkowski Descent: An Algorithm for Stochastic Global Optimization
Keshav Patel Keval, Vivek S. Borkar, Ananya Singhal · 2024
We introduce a novel stochastic global optimization algorithm called Minkowski descent for optimizing a black-box function over a convex domain. No assumptions are made about the function, such as Lipschitz smoothness or strong convexity. The novel algorithm is a two timescale scheme which uses a heuristic inspired by the Shapley-Folkman theorem in order to accelerate the search process. We compare the multi-start version of our algorithm with standard algorithms such as pure random search, multi-start simulated annealing and multi-start stochastic gradient descent, among other gradient based algorithms.