TY - JOUR

T1 - Bound-constrained global optimization of functions with low effective dimensionality using multiple random embeddings

AU - Cartis, Coralia

AU - Massart, Estelle

AU - Otemissov, Adilet

N1 - Publisher Copyright:
© 2022, The Author(s).

PY - 2023/3

Y1 - 2023/3

N2 - We consider the bound-constrained global optimization of functions with low effective dimensionality, that are constant along an (unknown) linear subspace and only vary over the effective (complement) subspace. We aim to implicitly explore the intrinsic low dimensionality of the constrained landscape using feasible random embeddings, in order to understand and improve the scalability of algorithms for the global optimization of these special-structure problems. A reduced subproblem formulation is investigated that solves the original problem over a random low-dimensional subspace subject to affine constraints, so as to preserve feasibility with respect to the given domain. Under reasonable assumptions, we show that the probability that the reduced problem is successful in solving the original, full-dimensional problem is positive. Furthermore, in the case when the objective’s effective subspace is aligned with the coordinate axes, we provide an asymptotic bound on this success probability that captures its polynomial dependence on the effective and, surprisingly, ambient dimensions. We then propose X-REGO, a generic algorithmic framework that uses multiple random embeddings, solving the above reduced problem repeatedly, approximately and possibly, adaptively. Using the success probability of the reduced subproblems, we prove that X-REGO converges globally, with probability one, and linearly in the number of embeddings, to an ϵ-neighbourhood of a constrained global minimizer. Our numerical experiments on special structure functions illustrate our theoretical findings and the improved scalability of X-REGO variants when coupled with state-of-the-art global—and even local—optimization solvers for the subproblems.

AB - We consider the bound-constrained global optimization of functions with low effective dimensionality, that are constant along an (unknown) linear subspace and only vary over the effective (complement) subspace. We aim to implicitly explore the intrinsic low dimensionality of the constrained landscape using feasible random embeddings, in order to understand and improve the scalability of algorithms for the global optimization of these special-structure problems. A reduced subproblem formulation is investigated that solves the original problem over a random low-dimensional subspace subject to affine constraints, so as to preserve feasibility with respect to the given domain. Under reasonable assumptions, we show that the probability that the reduced problem is successful in solving the original, full-dimensional problem is positive. Furthermore, in the case when the objective’s effective subspace is aligned with the coordinate axes, we provide an asymptotic bound on this success probability that captures its polynomial dependence on the effective and, surprisingly, ambient dimensions. We then propose X-REGO, a generic algorithmic framework that uses multiple random embeddings, solving the above reduced problem repeatedly, approximately and possibly, adaptively. Using the success probability of the reduced subproblems, we prove that X-REGO converges globally, with probability one, and linearly in the number of embeddings, to an ϵ-neighbourhood of a constrained global minimizer. Our numerical experiments on special structure functions illustrate our theoretical findings and the improved scalability of X-REGO variants when coupled with state-of-the-art global—and even local—optimization solvers for the subproblems.

KW - Constrained optimization

KW - Dimensionality reduction techniques

KW - Functions with low effective dimensionality

KW - Global optimization

KW - Random embeddings

UR - http://www.scopus.com/inward/record.url?scp=85132608600&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85132608600&partnerID=8YFLogxK

U2 - 10.1007/s10107-022-01812-9

DO - 10.1007/s10107-022-01812-9

M3 - Article

AN - SCOPUS:85132608600

SN - 0025-5610

VL - 198

SP - 997

EP - 1058

JO - Mathematical Programming

JF - Mathematical Programming

IS - 1

ER -