  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 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, that only vary over a low-dimensional
subspace, 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.
