Global optimization using random embeddings

Cartis C. Massart E. Otemissov A.
July 2023 Springer Science and Business Media Deutschland GmbH

Mathematical Programming
2023 #200 Issue 2 781 - 829 pp.

We propose a random-subspace algorithmic framework for global optimization of Lipschitz-continuous objectives, and analyse its convergence using novel tools from conic integral geometry. X-REGO randomly projects, in a sequential or simultaneous manner, the high-dimensional original problem into low-dimensional subproblems that can then be solved with any global, or even local, optimization solver. We estimate the probability that the randomly-embedded subproblem shares (approximately) the same global optimum as the original problem. This success probability is then used to show almost sure convergence of X-REGO to an approximate global solution of the original problem, under weak assumptions on the problem (having a strictly feasible global solution) and on the solver (guaranteed to find an approximate global solution of the reduced problem with sufficiently high probability). In the particular case of unconstrained objectives with low effective dimension, we propose an X-REGO variant that explores random subspaces of increasing dimension until finding the effective dimension of the problem, leading to X-REGO globally converging after a finite number of embeddings, proportional to the effective dimension. We show numerically that this variant efficiently finds both the effective dimension and an approximate global minimizer of the original problem.

Conic integral geometry , Dimensionality reduction techniques , Functions with low effective dimensionality , Global optimization , Random subspaces

Text of the article Перейти на текст статьи

The Alan Turing Institute, The British Library, London, NW1 2DB, United Kingdom
Mathematical Institute, University of Oxford, Radcliffe Observatory Quarter, Woodstock Road, Oxford, OX2 6GG, United Kingdom
National Physical Laboratory, Hampton Road, Middlesex, Teddington, TW11 0LW, United Kingdom
Nazarbayev University, Qabanbay Batyr Ave 53, Nur-Sultan, 010000, Kazakhstan

The Alan Turing Institute
Mathematical Institute
National Physical Laboratory
Nazarbayev University

10 лет помогаем публиковать статьи Международный издатель

Книга Публикация научной статьи Волощук 2026 Book Publication of a scientific article 2026