Optimization Online


Global optimization using random embeddings

Coralia Cartis(cartis***at***maths.ox.ac.uk)
Estelle Massart(estelle.massart***at***maths.ox.ac.uk)
Adilet Otemissov(aotemissov***at***gmail.com)

Abstract: 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.

Keywords: global optimization, random subspaces, conic integral geometry, dimensionality reduction, functions with low effective dimension

Category 1: Global Optimization

Category 2: Nonlinear Optimization

Citation: Oxford University Technical Report, 2021.

Download: [PDF]

Entry Submitted: 07/24/2021
Entry Accepted: 07/28/2021
Entry Last Modified: 07/24/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society