# Optimization for sampling multiple points of maximized minimum distance

I'm trying to find a way to sample new points that have maximum minimum-distance (maximin distance). The current situation is where there are ns number of pre-existing sample points. I want N number of new sample points that are filling the space as much as possible (hence, the maximization of minimum distance).

The most conventional way would be to sample single points in a loop (performing N loops). However, what I want is to find multiple points that have distances maximized for each other as well as from the existing points. Currently, I'm using a population-based global optimizer where a variable is set as follows:

When sampling N points with nx number of variables, a single population would be a vector with a length of (N x nx). The objective function to be maximized would be the total sum of minimum distances between the N points and also the distance between N and ns (existing) points.

The problem with this method is that not only the problem is highly non-linear but also the size of the number of variables for the optimization problem (N x nx) increases rapidly as the number of variables for the sample space (in other words, dimension) nx increases.

I was wondering is there any other way than to vectorize multiple samples? And also, is there a global optimization algorithm that gives multiple individuals from a population as its optimum result (not a multi-objective optimization as the problem in my case has a single objective: distance)?

• You've just discovered why global optimization in high-dimensional spaces is difficult :-) – Wolfgang Bangerth Jun 17 '20 at 14:24