Statistics of partial minima
Eli Ben-Naim, M. B. Hastings, David Izraelevitz · Journal of Physics A Mathematical and Theoretical · 2007
We study pseudo-optimal solutions to multi-objective optimization problems by introducing partial minima defined as follows. Point x k -dominates x ' when at least k of the coordinates of x are smaller than the corresponding coordinates of x '. A point not k -dominated by any other point in the set is a k -minimum or a partial minimum, generalizing the global minimum. We study statistical properties of partial minima for a set of N points independently distributed inside the d -dimensional unit hypercube using exact probabilistic methods and heuristic scaling techniques. The average number of partial minima, A , decays algebraically with the total number of points, A ∼ N −( d − k )/ k , when 1 ⩽ k < d . Interestingly, there are k − 1 distinct scaling laws characterizing the largest coordinates: the distribution P ( y j ) of the j th largest coordinate, y j , decays algebraically, , with for 1 ⩽ j ⩽ k − 1. The average number of partial minima grows logarithmically, , when k = d . The full distribution of the number of minima is obtained in closed form in two dimensions.