  


Global optimization using random embeddings
Coralia Cartis(cartismaths.ox.ac.uk) Abstract: We propose a randomsubspace algorithmic framework for global optimization of Lipschitzcontinuous objectives, and analyse its convergence using novel tools from conic integral geometry. XREGO randomly projects, in a sequential or simultaneous manner, the high dimensional original problem into lowdimensional subproblems that can then be solved with any global, or even local, optimization solver. We estimate the probability that the randomlyembedded subproblem shares (approximately) the same global optimum as the original problem. This success probability is then used to show convergence of XREGO 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 lowdimensional subspace, we propose an XREGO variant that explores random subspaces of increasing dimension until finding the effective dimension of the problem, leading to XREGO 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 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  