A Randomised Non-descent Method for Global Optimisation

Dmitry Pasechnyuk, Alexander GornovCommunications 2023 · DOI · OpenAlex

Abstract: This paper proposes a novel algorithm for non-convex multimodal constrained optimisation problems. It is based on sequentially solving restrictions of the problem to sections of the feasible set by random subspaces (in general, manifolds) of low dimensionality. This approach varies in the way subspaces are drawn, the dimensionality of those subspaces, and the method used to solve the restricted problems. We provide an empirical study of the algorithm on convex, unimodal, and multimodal optimisation problems and compare it with efficient algorithms intended for each class of problems.

Introduction

In mathematical optimization, finding the global minimum in a landscape filled with numerous local minima is a significant challenge. Traditional descent-based methods often act like a hiker who only looks at their feet, walking downhill until they hit a local trap, potentially missing much deeper global minima. Dmitry A. Pasechnyuk and Alexander Gornov propose a fresh strategy called the Solar method. Instead of following local gradients, this algorithm casts "rays" in random directions and jumps to the best spot found along those paths.

The Solar Method: A Meta-Algorithmic Scheme

The Solar method operates by exploring random low-dimensional "slices" of a complex problem. The name is derived from a metaphor: the algorithm stands at a "sun-like" point and explores along random "rays."

Core Mechanics

  1. Subspace Sampling: Instead of optimizing all $N$ dimensions simultaneously, the algorithm selects a random low-dimensional subspace. This can be done via completely random directions (Vanilla) or directions biased toward a "dominant" direction, such as a previous gradient (Cone-restricted).
  2. Restricted Optimization: Within this low-dimensional slice (often just 1 or 2 dimensions), a standard solver (e.g., Nelder-Mead simplex method) is used to find the best possible point.
  3. The Jump: If the solver finds a point superior to the current best, the algorithm "jumps" to that new location.
  4. Memory Management: The system maintains a data structure of the $p$ best points found so far to ensure it retains knowledge of promising regions.

Key Insights

  • Exploration over Exploitation: By choosing random directions, the Solar method prioritizes global landscape exploration, allowing it to "jump" over ridges that would halt gradient-based methods.
  • Dimensionality Reduction: Solving many low-dimensional sub-problems is often more efficient than tackling one high-dimensional problem. Empirical evidence suggests that lower-dimensional subspaces generally lead to better convergence.
  • Robustness: The method is less sensitive to hyperparameters than classic heuristics like Simulated Annealing. The "jump length" is determined by solving a sub-problem, removing the need for manual tuning of step sizes or "temperatures."

Empirical Evaluation

The authors evaluated the Solar method using standard mathematical benchmarks, including convex quadratic functions, the non-convex Rosenbrock–Skokov valley, and the highly multimodal Rastrigin function.

Performance on Convex Problems

On convex quadratic problems, the Solar method exhibits nearly linear convergence in its early stages. While it is slightly outperformed by steepest descent, it remains highly competitive against other zeroth-order methods.

Figure 2: Comparison of the Solar method with standard descent methods on a quadratic problem.

In the Rosenbrock–Skokov test, where the minimum lies in a narrow, curved valley, the Solar method maintained a steady convergence rate. Unlike Conjugate Gradient (CG) methods, which can stall or slow down significantly in such environments, the Solar method's ability to jump across valley walls proved advantageous.

Figure 4: Performance of Solar method variants compared to Conjugate Gradient methods on the Rosenbrock-Skokov problem.

On the 200-dimensional Rastrigin problem, the Solar method was significantly more efficient at finding deeper local optima than Simulated Annealing or Monotonic Sequence Basin Hopping (MSBH).

Conclusion and Future Work

The Solar method presents a robust alternative for global optimization, particularly in high-dimensional, non-convex spaces. While it shows great promise, current limitations include computational overhead from maintaining the best-points list and potential error accumulation from sub-problem solvers. Future research may explore more efficient data structures like k-d trees and "multi-level" optimization, where the Solar method is used recursively to solve its own restricted sub-problems.

Summary updated

BibTeX
@inproceedings{pasechnyuk2023randomised,
  author = {Dmitry Pasechnyuk and Alexander Gornov},
  title = {{A Randomised Non-descent Method for Global Optimisation}},
  booktitle = {Communications},
  year = {2023},
  doi = {10.1007/978-3-031-48751-4\_1},
}

Loading related content...

Figure