Seminar Details
2023-09-19 (14h) : Global optimization using random embeddings
At Euler building (room A.002)
Organized by Mathematical Engineering
Speaker :
Massart, Estelle
Abstract :
We address global high-dimensional optimization problems in which the objective is mostly varying along a low-dimensional subspace of the search space. These problems appear, e.g., in complex engineering and physical simulation/inverse problems. We propose a random-subspace algorithmic framework (referred to as X-REGO) that 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. For Lipschitz-continuous objectives, we analyse its convergence using novel tools from probability theory as well as conic integral geometry; our analysis relies on an estimation of 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).
This is joint work with C. Cartis (University of Oxford) and A. Otemissov (Nazarbayev University).