Optimal computing budget allocation for Monte Carlo simulation with application to product design

https://doi.org/10.1016/S1569-190X(02)00095-3Get rights and content

Abstract

Ordinal optimization has emerged as an efficient technique for simulation and optimization, converging exponentially in many cases. In this paper, we present a new computing budget allocation approach that further enhances the efficiency of ordinal optimization. Our approach intelligently determines the best allocation of simulation trials or samples necessary to maximize the probability of identifying the optimal ordinal solution. We illustrate the approach’s benefits and ease of use by applying it to two electronic circuit design problems. Numerical results indicate the approach yields significant savings in computation time above and beyond the use of ordinal optimization.

Introduction

In developing a new product or manufacturing process, designers often break the system down into components and examine how each component should be designed to support a set of performance criterion for the overall system. This is often carried out by first defining a set of tolerance levels for each component and then identifying component designs that best meet these targets. Defining appropriate tolerance levels can be difficult if the value (e.g., dimensions, frequency, cycle time) of a component is highly variable for a given design or correlated with the designs of other components. Another method, which is commonly used in designing electronic circuits, is to evaluate the interaction of alternative component designs directly with the objective of identifying the design combination that achieves the highest expected performance. This approach is commonly referred to as ‘Statistical Design’. The method involves running a series of experiments or simulations to model the performance behavior of each design. The definition of a good design can be quite general in this framework. For example, performance objectives may include minimizing a product’s output deviation relative to a target value or range; or maximizing product yield relative to a set of firm performance criteria.

The advantage of the Statistical Design method is that it evaluates component alternatives in terms of their entire performance distribution and captures possible performance dependencies among components. This gives a more accurate characterization of a design’s performance and helps identify a more robust design. However, the Statistical Design method has the drawback that its computational cost grows quickly with the number of designs and the desired accuracy of the performance estimation. For example, estimating yield for a given design requires performing a series of simulation trials where random values are assigned to a design’s statistical variables and the system performance targets are checked against each trial. The number of trials needed to guarantee a good estimate is often quite large due to the slow convergence rate of Monte Carlo simulation. In general, the rate of convergence is at best O(1/N), where N is the number of simulation trials [12], [16]. If N and the number of design alternatives, k, are both large, the total number of simulation trials, kN, may be prohibitively high. In such a case, the designer must either limit the number of design alternatives considered or settle for a less accurate yield comparison across designs.

In this paper we introduce a design optimization scheme, which utilizes Statistical Design in a more efficient manner than traditional Monte Carlo approaches. This allows a designer, with a fixed computing budget, to compare a larger set of designs with no loss in solution accuracy. The scheme utilizes ordinal optimization to significantly reduce the number of simulation trials needed to accurately compare designs. Ordinal optimization is appropriate in this context since we are interested in identifying the design with the highest performance, rather than an accurate estimation of performance for all designs. Dai, [10] shows that the convergence rate for ordinal optimization can be exponential, which is much faster than the convergence rate O(1/N) of a value estimate. The convergence rate increases significantly under ordinal comparison since an inferior design can be disregarded when the value estimate is still poor. This is valuable when selecting among finite design alternatives [15], [18] and over a continuous design space [1], [2], [6], [14], [20].

Our scheme further improves the performance of ordinal optimization by intelligently determining the number of simulation trials to perform across different designs as the algorithm unfolds. Intuitively, to ensure a high ordinal comparison probability, a larger portion of the computing budget should be allocated to those designs that are critical in the process of identifying the best design. On the other hand, limited computational effort should be expended on non-critical designs that have little effect on determining the optimal solution. Overall simulation efficiency is improved as less computational effort is spent on simulating non-critical designs and more is spent on critical designs. Ideally, one would like to allocate simulation trials to designs in a way that maximizes the probability of selecting the best design within a given computing budget. We present an innovative optimal computing budget allocation (OCBA) technique to accomplish this goal.

Previous researchers have examined various approaches for efficiently allocating a fixed computing budget across solution alternatives. Chen, [3] formulates the procedure of allocating computational efforts as a nonlinear optimization problem. Chen et al., [5] applies the steepest-ascent method to solve the budget allocation problem. The major drawback of the steepest-ascent method is that extra computation cost is incurred to iteratively search for a solution to the budget allocation problem. This extra cost could be significant if the number of iterations is large. Chen et al., [7] introduces a greedy heuristic to solve the budget allocation problem. This greedy heuristic iteratively determines which design appears to be the most promising for further simulation based on a simple metric. However, the budget allocation selected by the greedy heuristic is not necessarily optimal. For the special case where the simulation costs of all designs are equal, Chen et al., [8] offer an asymptotic solution to the budget allocation problem.

In this paper, we develop an asymptotically optimal approach for solving the budget allocation problem. This is accomplished by replacing the objective function with an approximation that can be solved analytically. The computation cost required to solve the approximate allocation problem is significantly lower than previous approaches (it is essentially negligible). This approach also allows for a more general formulation of the allocation problem, than that of previous approaches, by relaxing the restriction that the cost of simulation is identical for all designs.

In sum, this paper offers both a theoretical and practical contribution. At a theoretical level, we introduce a new OCBA solution technique that is asymptotically optimal and more general than previous approaches. This technique is quite general and thus could be applied within any ordinal optimization procedure. At a practical level, we introduce a new approach for efficiently incorporating Statistical Design evaluation techniques within a design optimization framework. We offer two circuit design problem examples to illustrate the benefits this approach offers over traditional ordinal optimization methods.

The paper continues in Section 2 with a formulation of the optimal computing budget allocation problem and discussion of major solution issues. We also provide background on the Bayesian model on which our solution technique is based. Section 3 presents our asymptotic solution technique. We illustrate the performance of this technique, as well as the overall optimization scheme, in Section 4, through two circuit design problems. Section 5 provides final conclusions.

Section snippets

Notation and problem formulation

In this section, we introduce the necessary notation and formulate the OCBA problem. Because our solution technique is quite general, we define the following notation in general terms rather than specifically in the context of a product design problem.

    k:

    the total number of alternative designs,

    ci:

    the computation cost per simulation run for design i,

    Xij:

    the result of the jth i.i.d. simulation run from design i,

    Xi:

    the vector representing all simulation output for design i; Xi={Xij: j=1,2,…,Ni},

    Ni:

An asymptotic allocation rule

To simplify the analysis of problem (II) we initially ignore the non-negativity constraints (3). We will show later that our solution technique always provides positive values for Ni, i=1,…,k. We also assume that Ni is a continuous variable, which is a reasonable approximation for large T. We will denote this simplified version of the problem as problem III.

The major issue in solving problem III is the estimation of the gradient information of i=1,i≠bkP{μ̂b<μ̂i}. This is difficult because

Applications and numerical testing

To illustrate how our algorithm can be used to solve a range of optimization problems, we offer two diverse circuit design examples. The first example identifies the optimal design of a double-T filter circuit, where the design’s performance is defined in terms of its deviation from a fixed performance target. The second example identifies the optimal design of a 2-to-1 impedance matching transformer with a passband of one octave. Here performance is defined in terms of the design’s expected

Conclusions

In this paper, we introduced an OCBA technique for efficiently solving a general design selection problem. The technique is based on an asymptotic allocation rule developed in the paper. We apply this technique to a series of circuit design problems to show how it can be effectively incorporated into a design optimization study. Numerical results suggest that the technique further enhances the simulation efficiency of ordinal optimization. When the technique is combined with ordinal

References (20)

  • C.G. Cassandras, G. Bao, A stochastic comparison algorithm for continuous optimization with estimations, Proceedings of...
  • C.G. Cassandras, V. Julka, Descent algorithms for discrete resource allocation problems, Proceedings of the 33rd IEEE...
  • C.H. Chen, An effective approach to smartly allocate computing budget for discrete event simulation, Proceedings of the...
  • C.H. Chen

    A lower bound for the correct subset-selection probability and its application to discrete event system simulations

    IEEE Transactions on Automatic Control

    (1996)
  • H.C. Chen, C.H. Chen, L. Dai, E. Yücesan, New development of optimal computing budget allocation for discrete event...
  • C.H. Chen et al.

    Motion planning of walking robots using ordinal optimization

    IEEE Robotics and Automation Magazine

    (1998)
  • C.H. Chen et al.

    Ordinal comparison of heuristic algorithms using stochastic optimization

    IEEE Transactions on Robotics and Automation

    (1999)
  • C.H. Chen et al.

    Simulation budget allocation for further enhancing the efficiency of ordinal optimization

    Journal of Discrete Event Dynamic Systems: Theory and Applications

    (2000)
  • E. Christian

    Filter Design Tables And Graphs

    (1966)
  • L. Dai

    Convergence properties of ordinal comparison in the simulation of discrete event dynamic systems

    Journal of Optimization Theory and Applications

    (1996)
There are more references available in the full text version of this article.

Cited by (0)

This work has been supported in part by NSF under grants DMI-9732173, DMI-0002900, DMI-0049062, by Sandia National Laboratories under contract BD-0618, and by George Mason University Research Foundation.

View full text