taramath: Das Gbb-Paket

Beschreibung

Das Gbb-Paket stellt mit dem geometrischen Branch-and-Bound Verfahren eine grundlegende Technik der globalen Optimierung bereit. Neben der Zielfunktion muss jedoch auch eine Funktion zur Berechnung von unteren Schranke spezifiziert werden, welche während des Branch-and-Bound Algorithmus zum Einsatz kommt. Möglichkeiten zur Berechnung von unteren Schranken liefern beispielsweise DC-Funktionen oder aber es werden Methoden der Intervallanalysis verwendet.

Beispiel

Das folgende Beispiel löst ein zweidimensionales Optimierungsproblem mit dem geometrischen Branch-and-Bound Verfahren. Die dafür notwendigen Schranken werden unter Verwendung der natürlichen Intervallerweiterung berechnet.

<!DOCTYPE html>
<html>
<head>
  <script src="taramath.js"></script>
</head>
<body>
<textarea id="output"></textarea>
<script>

  // Zielfunktion mit x = (x[0], x[1])
  function f (x) {
    var h1 = x[0] + 2*x[1] - 7;
    var h2 = 2*x[0] + x[1] - 5;
    return h1*h1 + h2*h2;
  };

  // Untere Schranke mittels Intervallanalysis
  function LB (X) {
    var H1 = Interval.add(X[0], Interval.mult(2, X[1]), -7);
    var H2 = Interval.add(Interval.mult(2, X[0]), X[1], -5);
    var H = Interval.add(Interval.sq(H1), Interval.sq(H2));
    return H[0];
  };

  // Initiale Box
  var X = [[-10,10],[-10,10]];

  // Optimierungsproblem loesen
  var S = Gbb.minimize(f, LB, X);

  // Ergebnis ausgeben
  Print.init("output");
  if (typeof(S) == "string") {
    Print.object(S);
  } else {
    Print.object("Optimalloesung:");
    Print.object(S[0]);
    Print.object("Zielfunktionswert:");
    Print.object(S[1]);
    Print.object("Anzahl Iterationen:");
    Print.object(Gbb.get_number_of_iterations());
  };

</script>
</body>

Vorschau aktualisieren

Das Gbb-Paket

zur Anwendung des geometrischen Branch-and-Bound Verfahrens