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

Juxin Li, Weizhi Liu, Giulia Pedrielli, Loo Hay Lee, Ek Peng Chew

Research output: Contribution to journalArticlepeer-review

22 Scopus citations


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).

Original languageEnglish (US)
Article number8128499
Pages (from-to)2913-2927
Number of pages15
JournalIEEE Transactions on Automatic Control
Issue number9
StatePublished - Sep 2018


  • Large deviation (LD) theory
  • Pareto optimality
  • multi-objective optimization
  • optimal computing budget allocation (OCBA)
  • ranking and selection (R&S)
  • simulation optimization

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Computer Science Applications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Optimal Computing Budget Allocation to Select the Nondominated Systems - A Large Deviations Perspective'. Together they form a unique fingerprint.

Cite this