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 similar to 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, P(y(j)) similar to ( y(j))(-alpha j-1), with a(j) = j d-k/k-j for 1 <= j <= k - 1. The average number of partial minima grows logarithmically, A similar or equal to 1/(d- 1)! (ln N)(d- 1), when k = d. The full distribution of the number of minima is obtained in closed form in two dimensions.
Duke University * Arts & Sciences * Physics * Faculty * Staff * Grad * Researchers * Reload * Login
Copyright (c) 2001-2002 by Duke University Physics.