Optimal Computing Budget Allocation to Select the Nondominated Systems - A Large Deviations Perspective

We consider the optimal computing budget allocation problem to select the nondominated systems on finite sets under a stochastic multi-objective ranking and selection setting. This problem has been addressed in the settings of correct selection guarantee when all the systems have normally distributed objectives with no correlation within and between solutions. We revisit this problem from a large deviation perspective and present a mathematically robust formulation that maximizes the lower bound of the rate function of the probability of false selection (P(FS)) defined as the probability of not identifying the true Pareto set. The proposed formulation allows general distributions and explicitly characterizes the sampling correlations across performance measures. Three budget allocation strategies are proposed. One of the approaches is guaranteed to attain the global optimum of the lower bound of the rate function but has high computational cost. Therefore, a heuristic to approximate the global optimal strategy is proposed to save computational resources. Finally, for the case of normally distributed objectives, a computationally efficient procedure is proposed, which adopts an iterative algorithm to find the optimal budget allocation. Numerical experiments illustrate the significant improvements of the proposed strategies over others in the existing literature in terms of the rate function of P(FS).