Elementwise Adaptive Random Search for High-Dimensional Constrained Continuous Global Optimization

Abstract

We propose a new stochastic method for high-dimensional constrained continuous global optimization without convexity assumptions. The algorithm combines global exploration and local refinement through coordinate-wise adaptive perturbations, whose scale is proportional to the current iterate. We show that global exploration reaches any feasible region with positive probability, while local search benefits from strong concentration properties, enabling efficient decline near optima. Their combination yields convergence to a global minimizer under mild regularity conditions. Applications to LASSO sparsity improvement as well as similar BPDN (Basis Pursuit DeNoising) problems, and to neural network pruning, illustrate the practical effectiveness of the approach.