Efficient Global Optimization of Expensive Black-Box Functions

Journal of Global Optimization - Tập 13 Số 4 - Trang 455-492 - 1998
Jones, Donald R.1, Schonlau, Matthias2, Welch, William J.3
1Operations Research Department, General Motors R&D Operations, Warren, USA
2National Institute of Statistical Sciences, Research Triangle Park, USA
3Department of Statistics and Actuarial Science and The Institute for Improvement in Quality and Productivity, University of Waterloo, Waterloo, Canada

Tóm tắt

In many engineering optimization problems, the number of function evaluations is severely limited by time or cost. These problems pose a special challenge to the field of global optimization, since existing methods often require more function evaluations than can be comfortably afforded. One way to address this challenge is to fit response surfaces to data collected by evaluating the objective and constraint functions at a few points. These surfaces can then be used for visualization, tradeoff analysis, and optimization. In this paper, we introduce the reader to a response surface methodology that is especially good at modeling the nonlinear, multimodal functions that often occur in engineering. We then show how these approximating functions can be used to construct an efficient global optimization algorithm with a credible stopping rule. The key to using response surfaces for global optimization lies in balancing the need to exploit the approximating surface (by sampling where it is minimized) with the need to improve the approximation (by sampling where prediction error may be high). Striking this balance requires solving certain auxiliary problems which have previously been considered intractable, but we show how these computational obstacles can be overcome.

Từ khóa


Tài liệu tham khảo

citation_journal_title=Structural Optimization; citation_title=A trust-region framework for managing the use of approximation models in optimization; citation_author=N. M. Alexandrov, J. E. Dennis, R. M. Lewis, V. Torczon; citation_volume=15; citation_publication_date=1998; citation_pages=16-23; citation_id=CR1

citation_journal_title=Journal of Global Optimization; citation_title=αBB: a global optimization method for general constrained nonconvex problems; citation_author=I. P. Androulakis, C. D. Maranas, C. A. Floudas; citation_volume=7; citation_publication_date=1995; citation_pages=337-363; citation_id=CR2

citation_journal_title=Applied Statistics; citation_title=Circuit optimization via sequential computer experiments: design of an output buffer; citation_author=R. Aslett, R. J. Buck, S. G. Duvall, J. Sacks, W. J. Welch; citation_volume=47; citation_publication_date=1998; citation_pages=31-48; citation_id=CR3

citation_journal_title=Journal of Global Optimization; citation_title=Bayesian methods in global optimization; citation_author=B. Betro; citation_volume=1; citation_publication_date=1991; citation_pages=1-14; citation_id=CR4

citation_title=Stochastic methods; citation_inbook_title=Handbook of Global Optimization; citation_publication_date=1995; citation_pages=829-869; citation_id=CR5; citation_author=C. G. E. Boender; citation_author=H. E. Romeijn; citation_publisher=Kluwer Academic Publishers

Booker, A. J., Conn, A. R., Dennis, J. E., Frank, P. D., Trossett, M. and Torczon, V. (1995), Global modeling for optimization, Boeing Information and Support Services, Technical Report ISSTECH–95-032.

Booker, A. J., Dennis, J. E., Frank, P. D., Serafini, D. B. and Torczon, V. (1997), Optimization using surrogate objectives on a helicopter test example, Boeing Shared Services Group, Technical Report SSGTECH–97-027.

citation_title=Statistics for Experimenters; citation_publication_date=1978; citation_id=CR8; citation_author=G. E. P. Box; citation_author=W. G. Hunter; citation_author=J. S. Hunter; citation_publisher=John Wiley

citation_title=SDO: A statistical method for global optimization; citation_inbook_title=Multidisciplinary Design Optimization: State of the Art; citation_publication_date=1997; citation_pages=315-329; citation_id=CR9; citation_author=D. D. Cox; citation_author=S. John; citation_publisher=SIAM

citation_journal_title=The American Statistician; citation_title=Geostatistics; citation_author=N. Cressie; citation_volume=43; citation_publication_date=1989; citation_pages=197-202; citation_id=CR10

citation_journal_title=Mathematical Geology; citation_title=The origins of kriging; citation_author=N. Cressie; citation_volume=22; citation_publication_date=1990; citation_pages=239-252; citation_id=CR11

citation_title=Statistics for Spatial Data; citation_publication_date=1993; citation_id=CR12; citation_author=N. Cressie; citation_publisher=John Wiley

citation_journal_title=Journal of the American Statistical Association; citation_title=Bayesian prediction of deterministic functions, with applications to the design and analysis of computer experiments; citation_author=C. Currin, T. Mitchell, M. Morris, D. Ylvisaker; citation_volume=86; citation_publication_date=1991; citation_pages=953-963; citation_id=CR13

citation_title=The global optimisation problem: an introduction; citation_inbook_title=Towards Global Optimisation; citation_publication_date=1978; citation_pages=1-15; citation_id=CR14; citation_author=L. C. W. Dixon; citation_author=G. P. Szego; citation_publisher=North Holland

Eby, D., Averill, R. C., Punch III, W. F. and Goodman, E. D. (1998), Evaluation of injection island GA performance on flywheel design optimization, in I. C. Parmee (ed.), Adaptive Computing in Design and Manufacture, Springer Verlag.

Elder IV, J. F. (1992), Global R d optimization when probes are expensive: the GROPE algorithm. Proceedings of the 1992 IEEE International Conference on Systems, Man, and Cybernetics, Vol. 1, pp. 577–582, Chicago.

citation_journal_title=Journal of Agricultural, Biological, and Environmental Statistics; citation_title=Predicting urban ozone levels and trends with semiparametric modeling; citation_author=F. Gao, J. Sacks, W. J. Welch; citation_volume=1; citation_publication_date=1996; citation_pages=404-425; citation_id=CR17

citation_title=Computer experiments; citation_inbook_title=Handbook of Statistics, 13: Design and Analysis of Experiments; citation_publication_date=1996; citation_pages=261-308; citation_id=CR18; citation_author=J. Koehler; citation_author=A. Owen; citation_publisher=Elsevier

citation_journal_title=Journal of Basic Engineering; citation_title=A new method of locating the maximum point of an arbitrary multipeak curve in the presence of noise; citation_author=H. J. Kushner; citation_volume=86; citation_publication_date=1964; citation_pages=97-106; citation_id=CR19

citation_journal_title=Journal of Global Optimization; citation_title=Bayesian algorithms for one-dimensional global optimization; citation_author=M. Locatelli; citation_volume=10; citation_publication_date=1997; citation_pages=57-76; citation_id=CR20

citation_journal_title=Economic Geology; citation_title=Principles of geostatistics; citation_author=G. Matheron; citation_volume=58; citation_publication_date=1963; citation_pages=1246-1266; citation_id=CR21

citation_journal_title=Technometrics; citation_title=A comparison of three methods for selecting values of input variables in the analysis of output from a computer code; citation_author=M. D. McKay, W. J. Conover, R. J. Beckman; citation_volume=21; citation_publication_date=1979; citation_pages=239-245; citation_id=CR22

citation_journal_title=Journal of Global Optimization; citation_title=Application of Bayesian approach to numerical methods of global and stochastic optimization; citation_author=J. Mockus; citation_volume=4; citation_publication_date=1994; citation_pages=347-365; citation_id=CR23

citation_title=The application of Bayesian methods for seeking the extremum; citation_inbook_title=Towards Global Optimisation; citation_publication_date=1978; citation_pages=117-129; citation_id=CR24; citation_author=J. Mockus; citation_author=V. Tiesis; citation_author=A. Zilinskas; citation_publisher=North Holland

citation_journal_title=Technometrics; citation_title=Bayesian design and analysis of computer experiments: use of derivatives in surface prediction; citation_author=M. D. Morris, T. J. Mitchell, D. Ylvisaker; citation_volume=35; citation_publication_date=1993; citation_pages=243-255; citation_id=CR25

citation_title=A new approach to the synthesis of optimal smoothing and prediction systems; citation_inbook_title=Mathematical Optimization Techniques; citation_publication_date=1963; citation_pages=75-108; citation_id=CR26; citation_author=E. Parzen; citation_publisher=University of California Press

citation_journal_title=Proceedings of the 1991 IEEE Conference on Systems, Man, and Cybernetics; citation_title=A computational geometric approach to feasible region division in constrained global optimization; citation_author=C. Perttunen; citation_volume=1; citation_publication_date=1991; citation_pages=585-590; citation_id=CR27

Press, W. H., Flannery, B. P., Teukolsky, S. A. and Vetterling, W. T. (1993), Numerical Recipes in FORTRAN, Cambridge University Press.

citation_journal_title=Statistical Science; citation_title=Design and analysis of computer experiments (with discussion); citation_author=J. Sacks, W. J. Welch, T. J. Mitchell, H. P. Wynn; citation_volume=4; citation_publication_date=1989; citation_pages=409-435; citation_id=CR29

citation_title=Statistical designs and integral approximation; citation_inbook_title=Proceedings of the Twelfth Biennial Seminar of the Canadian Mathematical Congress; citation_publication_date=1970; citation_pages=115-136; citation_id=CR30; citation_author=J. Sacks; citation_author=D. Ylvisaker; citation_publisher=Canadian Mathematical Congress

citation_title=Computer experiments and global optimization; citation_publication_date=1997; citation_id=CR31; citation_author=M. Schonlau; citation_publisher=University of Waterloo

Schonlau, M., Welch, W. J. and Jones, D. R. (1998), Global versus local search in constrained optimization of computer models, to appear in N. Flournoy, W. F. Rosenberger and W. K. Wong (eds.), New Developments and Applications in Experimental Design, Institute of Mathematical Statistics. Also available as Technical Report RR–97-11, Institute for Improvement in Quality and Productivity, University of Waterloo, Waterloo, Ontario, Canada, December 1997.

citation_journal_title=IEEE Transactions on Systems, Man, and Cybernetics; citation_title=A global search method for optimizing nonlinear systems; citation_author=B. E. Stuckman; citation_volume=18; citation_publication_date=1988; citation_pages=965-977; citation_id=CR33

citation_title=Principles of Econometrics; citation_publication_date=1971; citation_id=CR34; citation_author=H. Theil; citation_publisher=John Wiley

citation_journal_title=Mathematical Geology; citation_title=Multivariable spatial prediction; citation_author=J. M. Ver Hoef, N. Cressie; citation_volume=25; citation_publication_date=1993; citation_pages=219-240; citation_id=CR35

citation_journal_title=Technometrics; citation_title=Screening, predicting, and computer experiments; citation_author=W. J. Welch, R. J. Buck, J. Sacks, H. P. Wynn, T. J. Mitchell, M. D. Morris; citation_volume=34; citation_publication_date=1992; citation_pages=15-25; citation_id=CR36

citation_journal_title=Journal of Global Optimization; citation_title=A review of statistical models for global optimization; citation_author=A. Zilinskas; citation_volume=2; citation_publication_date=1992; citation_pages=145-153; citation_id=CR37

Thông tin
Thông tin xuất bản

Journal of Global Optimization

Tập 13 Số 4

455-492

Thông tin tác giả