Black box optimization with exact subsolvers

Christine Edman

Diese Publikation zitieren

Christine Edman, Black box optimization with exact subsolvers (2016), Logos Verlag, Berlin, ISBN: 9783832591465

24
Accesses

Beschreibung / Abstract

We consider expensive optimization problems, that is to say problems where each evaluation of the objective function is expensive in terms of computing time, consumption of resources, or cost. This often happens in situations where the objective function is not available in analytic form, e.g. crash tests, best composition of chemicals, or soil contamination. Due to this lack of analytical representation we also speak about `black box functions'. In order to use as few function evaluations as possible within the optimization process, a sophisticated strategy to determine the evaluation points is necessary. In this thesis we present an algorithm which belongs to the class of the wellknown Radial basis function (RBF)-methods. RBF-methods usually incorporate subproblems which are difficult to solve exact. In order to solve these problems exact, we developed a Branch & Bound routine. This routine computes lower bounds by using the property of `conditional positive definiteness' of the RBF. We present a formula for the inverse of a blockmatrix with solely singular diagonal blocks. We also present a partitioning rule for multidimensional rectangles, which gives much freedom in the choice of the bisection point subject to preserve the important property of `exhaustiveness'. We tested our algorithm and present results for both expensive problems with only box constraints and expensive problems with general convex constraints.

Inhaltsverzeichnis

  • BEGINN
  • 1 Introduction
  • 1.1 Expensive optimization problems
  • 1.2 Global optimization methods
  • 2 Optimization methods for expensive problems
  • 2.1 Surface methods
  • 2.2 Surface methods with radial basis functions
  • 2.3 Gutmann†™s RBF method
  • 3 An optimized choice of points to be evaluated
  • 3.1 The subproblems: Cheap global optimization problems
  • 3.2 Distances, properties of phi(r) and lower bounds for sn(x)
  • 3.3 Useful properties of the matrix Phi and the (inverse of the) matrix A
  • 3.4 Computation of lower bounds for the auxiliary problem and the weighted auxiliary problem
  • 3.5 The Branch and Bound algorithm
  • 4 Box partitioning
  • 4.1 The problem
  • 4.2 General bisection of d-dimensional rectangles
  • 5 General convex constraints
  • 5.1 Scaling down rectangles
  • 5.2 The modified Branch and Bound algorithm
  • 6 Numerical tests
  • 6.1 The implementation
  • 6.2 How to use the code
  • 6.3 Test instances and runtime
  • 7 Conclusions
  • A Testproblems
  • Bibliography

Ähnliche Titel

    Mehr von diesem Autor