Abstract. 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 jth 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.

PACS numbers: 02.50.Cw, 05.40.−a, 89.20.Ff, 89.75.Da

Print publication: Issue 47 (23 November 2007)
Received 19 September 2007, in final form 10 October 2007
Published 6 November 2007