Nothing Special   »   [go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

MISO: mixed-integer surrogate optimization framework

  • Published:
Optimization and Engineering Aims and scope Submit manuscript

Abstract

We introduce MISO, the mixed-integer surrogate optimization framework. MISO aims at solving computationally expensive black-box optimization problems with mixed-integer variables. This type of optimization problem is encountered in many applications for which time consuming simulation codes must be run in order to obtain an objective function value. Examples include optimal reliability design and structural optimization. A single objective function evaluation may take from several minutes to hours or even days. Thus, only very few objective function evaluations are allowable during the optimization. The development of algorithms for this type of optimization problems has, however, rarely been addressed in the literature. Because the objective function is black-box, derivatives are not available and numerically approximating the derivatives requires a prohibitively large number of function evaluations. Therefore, we use computationally cheap surrogate models to approximate the expensive objective function and to decide at which points in the variable domain the expensive objective function should be evaluated. We develop a general surrogate model framework and show how sampling strategies of well-known surrogate model algorithms for continuous optimization can be modified for mixed-integer variables. We introduce two new algorithms that combine different sampling strategies and local search to obtain high-accuracy solutions. We compare MISO in numerical experiments to a genetic algorithm, NOMAD version 3.6.2, and SO-MI. The results show that MISO is in general more efficient than NOMAD and the genetic algorithm with respect to finding improved solutions within a limited budget of allowable evaluations. The performance of MISO depends on the chosen sampling strategy. The MISO algorithm that combines a coordinate perturbation search with a target value strategy and a local search performs best among all algorithms.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

Abbreviations

DYCORS:

DYnamic COordinate search using response surface models (Regis and Shoemaker 2013 )

EGO:

Efficient global optimization (Jones et al. 1998)

MISO:

Mixed-integer surrogate optimization

MISO-CP:

MISO-coordinate perturbation

MISO-EI:

MISO-expected improvement

MISO-RS:

MISO-random sampling

MISO-SM:

MISO-surface minimum

MISO-TV:

MISO-target value

MISO-CPTV:

MISO with combination of CP and TV

MISO-CPTV-local:

MISO with combination of CP, TV, and a local search

MISO-CPTV-l(f):

MISO-CPTV-local that uses fmincon as local optimizer

MISO-CPTV-l(o):

MISO-CPTV-local that uses ORBIT (Wild et al. 2007) as local optimizer

NOMAD:

Nonlinear optimization by mesh-adaptive direct search (Le Digabel 2011), version 3.6.2

RBF:

Radial basis function

SO-MI:

Surrogate optimization-mixed integer (Müller et al. 2013b)

SRBF:

Stochastic radial basis function algorithm (Regis and Shoemaker 2007)

f(·):

Computationally expensive objective function

d :

Problem dimension

d 1 :

Number of integer variables

d 2 :

Number of continuous variables

\({\mathbf {z}}\) :

Variable vector

\(z_i^l\), \(z_i^u\) :

Lower and upper variable bounds of the ith variable

\({\mathcal {Z}}\) :

Set of evaluated points, \({\mathcal {Z}}=\{{\mathbf {z}}_1,\ldots ,{\mathbf {z}}_n\}\)

\({\mathcal {Z}}_l\) :

Set of points evaluated during the local search (l-step)

n 0 :

Number of points in the initial experimental design

n 1 :

Number of function evaluations done in the local search (l-step)

n :

Number of already evaluated points

\(s_n(\cdot )\) :

Surrogate model fit to n data points

\({\mathbb {I}}\) :

Indices of the integer variables

References

  • Abramson M, Audet C, Chrissis J, Walston J (2009) Mesh adaptive direct search algorithms for mixed variable optimization. Optim Lett 3:35–47

    Article  MathSciNet  MATH  Google Scholar 

  • Booker A, Dennis J Jr, Frank P, Serafini D, Torczon V, Trosset M (1999) A rigorous framework for optimization of expensive functions by surrogates. Struct Multidiscip Optim 17:1–13

    Article  Google Scholar 

  • Conn A, Scheinberg K, Vicente L (2009) Introduction to Derivative-Free Optimization. SIAM

  • Currie J, Wilson D (2012) Foundations of computer-aided process operations. OPTI: lowering the barrier between open source optimizers and the industrial MATLAB user. Savannah, Georgia, USA

  • Davis E, Ierapetritou M (2009) Kriging based method for the solution of mixed-integer nonlinear programs containing black-box functions. J Glob Optim 43:191–205

    Article  MathSciNet  MATH  Google Scholar 

  • Forrester A, Sóbester A, Keane A (2008) Engineering design via surrogate modelling—a practical guide. Wiley, Chichester

    Book  Google Scholar 

  • Friedman J (1991) Multivariate adaptive regression splines. Ann Stat 19:1–141

    Article  MATH  Google Scholar 

  • Giunta A, Balabanov V, Haim D, Grossman B, Mason W, Watson L, Haftka R (1997) Aircraft multidisciplinary design optimisation using design of experiments theory and response surface modelling. Aeronaut J 101:347–356

    Google Scholar 

  • Glaz B, Friedmann P, Liu L (2008) Surrogate based optimization of helicopter rotor blades for vibration reduction in forward flight. Struct Multidiscip Optim 35:341–363

    Article  Google Scholar 

  • Goel T, Haftka RT, Shyy W, Queipo NV (2007) Ensemble of surrogates. Struct Multidiscip Optim 33:199–216

    Article  Google Scholar 

  • Gutmann H (2001) A radial basis function method for global optimization. J Glob Optim 19:201–227

    Article  MathSciNet  MATH  Google Scholar 

  • Hemker T, Fowler K, Farthing M, von Stryk O (2008) A mixed-integer simulation-based optimization approach with surrogate functions in water resources management. Optim Eng 9:341–360

    Article  MathSciNet  MATH  Google Scholar 

  • Holmström K (2008a) An adaptive radial basis algorithm (ARBF) for expensive black-box global optimization. J Glob Optim 41:447–464

    Article  MATH  Google Scholar 

  • Holmström K (2008b) An adaptive radial basis algorithm (ARBF) for expensive black-box mixed-integer global optimization. J Glob Optim 9:311–339

    MATH  Google Scholar 

  • Jones D, Schonlau M, Welch W (1998) Efficient global optimization of expensive black-box functions. J Glob Optim 13:455–492

    Article  MathSciNet  MATH  Google Scholar 

  • Koziel S, Leifsson L (2013) Surroagte-based modeling and optimization: applications in engineering. Springer, New York

    Book  Google Scholar 

  • Le Digabel S (2011) Algorithm 909: NOMAD: nonlinear optimization with the mads algorithm. ACM Trans Math Softw 37:44

    Article  MathSciNet  Google Scholar 

  • Li R, Emmerich M, Eggermont J, Bovenkamp E, Back T, Dijkstra J, Reiber H (2008) Metamodel-assisted mixed-integer evolution strategies and their applications to intravascular ultrasound image analysis. In: IEEE World Congress on Computational Intelligence, IEEE, pp 2764–2771

  • Marsden A, Wang M, Dennis J Jr, Moin P (2004) Optimal aeroacoustic shape design using the surrogate management framework. Optim Eng 5:235–262

    Article  MathSciNet  MATH  Google Scholar 

  • Moré J, Wild S (2009) Benchmarking derivative-free optimization algorithms. SIAM J Optim 20:172–191

    Article  MathSciNet  MATH  Google Scholar 

  • Müller J (2014) MATSuMoTo: The MATLAB surrogate model toolbox for computationally expensive black-box global optimization problems. arXiv:14044261

  • Müller J, Shoemaker C, Piché R (2013a) SO-I: a surrogate model algorithm for expensive nonlinear integer programming problems including global optimization applications. J Glob Optim 59:865–889. doi:10.1007/s10,898-013-0101-y

    Article  Google Scholar 

  • Müller J, Shoemaker C, Piché R (2013b) SO-MI: a surrogate model algorithm for computationally expensive nonlinear mixed-integer black-box global optimization problems. Comput Oper Res 40:1383–1400

    Article  MathSciNet  Google Scholar 

  • Müller J, Piché R (2011) Mixture surrogate models based on Dempster–Shafer theory for global optimization problems. J Glob Optim 51:79–104

    Article  MATH  Google Scholar 

  • Müller J, Shoemaker C (2014) Influence of ensemble surrogate models and sampling strategy on the solution quality of algorithms for computationally expensive black-box global optimization problems. J Glob Optim 60:123–144. doi:10.1007/s10898-014-0184-0

    Article  MATH  Google Scholar 

  • Myers R, Montgomery D (1995) Response surface methodology: process and product optimization using designed experiments. Wiley-Interscience Publication, Hoboken

    MATH  Google Scholar 

  • Powell M (1992) Advances in numerical analysis, vol. 2: wavelets, subdivision algorithms and radial basis functions. In: Light WA (ed) The theory of radial basis function approximation in 1990. Oxford University Press, Oxford, pp 105–210

    Google Scholar 

  • Rashid S, Ambani S, Cetinkaya E (2012) An adaptive multiquadric radial basis function method for expensive black-box mixed-integer nonlinear constrained optimization. Eng Optim 45:185–206. doi:10.1080/0305215X.2012.665450

    Article  MathSciNet  Google Scholar 

  • Regis R, Shoemaker C (2007) A stochastic radial basis function method for the global optimization of expensive functions. INFORMS J Comput 19:497–509

    Article  MathSciNet  MATH  Google Scholar 

  • Regis R, Shoemaker C (2009) Parallel stochastic global optimization using radial basis functions. INFORMS J Comput 21:411–426

    Article  MathSciNet  MATH  Google Scholar 

  • Regis R, Shoemaker C (2013) Combining radial basis function surrogates and dynamic coordinate search in high-dimensional expensive black-box optimization. Eng Optim 45:529–555

    Article  MathSciNet  Google Scholar 

  • Simpson T, Mauery T, Korte J, Mistree F (2001) Kriging metamodels for global approximation in simulation-based multidisciplinary design optimization. AIAA J 39:2233–2241

    Article  Google Scholar 

  • Viana F, Haftka R, Steffen V (2009) Multiple surrogates: how cross-validation errors can help us to obtain the best predictor. Struct Multidiscip Optim 39:439–457

    Article  Google Scholar 

  • Wild S, Regis R, Shoemaker C (2007) ORBIT: optimization by radial basis function interpolation in trust-regions. SIAM J Sci Comput 30:3197–3219

    Article  MathSciNet  Google Scholar 

  • Wild S, Shoemaker C (2013) Global convergence of radial basis function trust-region algorithms for derivative-free optimization. SIAM Rev 55:349–371

    Article  MathSciNet  MATH  Google Scholar 

  • Zhuang L, Tang K, Jin Y (2013) Metamodel assisted mixed-integer evolution strategies based on Kendall rank correlation coefficient. In: Hea Yin (ed) IDEAL 2013. Springer-Verlag, Berlin, pp 366–375

    Google Scholar 

Download references

Acknowledgments

This material is based upon work supported by the U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, Applied Mathematics program under contract number DE-AC02005CH11231. Partial support was also provided by NSF CISE 1116298 to Prof. Shoemaker at Cornell University, School of Civil and Environmental Engineering.

Author information

Authors and Affiliations

  1. Center for Computational Sciences and Engineering, Lawrence Berkeley National Laboratory, Berkeley, CA, 94720, USA

    Juliane Müller

Authors
  1. Juliane Müller
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Juliane Müller.

Electronic supplementary material

Below is the link to the electronic supplementary material.

Supplementary material 1 (PDF 96 kb)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Müller, J. MISO: mixed-integer surrogate optimization framework. Optim Eng 17, 177–203 (2016). https://doi.org/10.1007/s11081-015-9281-2

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11081-015-9281-2

Keywords

Search

Navigation