Optimization Toolbox

Hauptmerkmale

  • Nichtlineare und Mehrzieloptimierung
  • Solver für die nichtlineare Methode der kleinsten Quadrate, die Datenanpassung und nichtlineare Gleichungen
  • Quadratisches und lineares Programmieren
  • Gemischt-ganzzahlige lineare Programmierung
  • Optimierungsanwendung zur Definition und Lösung von Optimierungsproblemen sowie Überwachung des Lösungsfortschritts
  • Beschleunigung von nichtlinearen Solvern mit Nebenbedingung mit Parallel Computing Toolbox™
Verwendung eines Problems aus der gemischt-ganzzahligen linearen Programmierung zur optimalen Lösung, um Verkaufsstandorte von Lagerhäusern und Fabriken aus zu versorgen.
Verwendung eines Problems aus der gemischt-ganzzahligen linearen Programmierung zur optimalen Lösung, um Verkaufsstandorte von Lagerhäusern und Fabriken aus zu versorgen.

Definieren und Lösen von Optimierungsproblemen

Definieren eines Optimierungsproblems

Es werden Techniken zur Optimierung verwendet, um eine Reihe von Design-Parametern zu suchen, die das bestmögliche Ergebnis bringen. Es gibt zwei Schlüsselkomponenten in einem Optimierungsproblem:

Die Zielfunktion berechnet die gewünschte Menge, die minimiert oder maximiert werden soll. Es können Nebenbedingungen hinzugefügt werden, die die möglichen Werte für die Design-Parameter begrenzen.

Mathematische Modellierung mit Optimierung, Teil 1 8:51
Überführung einer Problembeschreibung in ein mathematisches Programm, das durch Optimierung gelöst werden kann. Als Beispiel dient eine Anlage zur Dampf- und Stromerzeugung.

Mathematische Modellierung mit Optimierung, Teil 2 10:46
Lösung eines linearen Programms mit Solvern der Optimization Toolbox™. Als Beispiel dient eine Anlage zur Dampf- und Stromerzeugung.

Verwendung der Optimierungsanwendung

Alle Funktionen der Optimization Toolbox sowie Solver-Optionen sind programmatisch oder über die Optimization App verfügbar.

Die Optimization App vereinfacht übliche Optimierungsaufgaben. Sie können damit:

  • Solver auswählen und Optimierungsprobleme definieren
  • Optimierungsoptionen und Anfangswerte für ausgewählte Solver festlegen und ansehen
  • Zwischen- und Endergebnisse von Optimierungen grafisch darstellen
  • Die Dokumentation zu allen Solvern im optionalen Quick-Reference-Fenster anzeigen lassen
  • Problemdefinitionen, Algorithmusoptionen und Ergebnisse zwischen dem MATLAB®-Workspace und die Optimization App importieren und exportieren
  • Automatisch MATLAB-Code erzeugen und so Ihre Arbeit speichern oder Aufgaben automatisieren
  • Auf Solver der Global Optimization Toolbox zugreifen

Erste Schritte mit dem Optimization Tool 6:08
Einrichten und Lösen von Optimierungsproblemen und Visualisieren der Zwischen- und Endergebnisse.

Auswählen eines Solvers

Die Optimization Toolbox enthält unterschiedliche Solver für unterschiedliche Typen von Zielen und Nebenbedingungen. Die Tabelle der Optimierungsentscheidung unterstützt Sie bei der Auswahl des besten Solvers für Ihr Problem.

Einrichtungsoptionen

Solver-Optionen ermöglichen es Ihnen, den Optimierungsprozess zu optimieren oder zu ändern sowie den Fortschritt des Solvers zu visualisieren. Einrichtungsoptionen können programmatisch oder unter Verwendung der Optimierungsanwendung durchgeführt werden.

Setting Options for Optimizations 4:48
Set options with optimoptions in Optimization Toolbox™ to tune solvers and monitor optimization progress.

Nichtlineare Optimierung

Die Optimization Toolbox verfügt über häufig verwendete Optimierungsalgorithmen zur Lösung von nichtlinearen Programmierungsproblemen in MATLAB. Die Toolbox bietet dazu Solver für nichtlineare Optimierungen mit und ohne Nebenbedingungen sowie Solver für kleinste Quadrate-Optimierungen.

Nichtlineare Optimierung ohne Nebenbedingungen

Die Optimization Toolbox enthält drei Methoden zur Lösung nichtlinearer Minimierungsprobleme ohne Nebenbedingungen:

  • Der Quasi-Newton-Algorithmus nutzt ein gemischtes quadratisches und kubisches Liniensuchverfahren sowie die Broyden-Fletcher-Goldfarb-Shanno -Formel (BFGS ) zur Aktualisierung der Näherung der Hesse-Matrix.
  • Der Nelder-Mead-Algorithmus (auch als Downhill-Simplex bezeichnet) ist eine direkte Suchmethode, die nur Funktionswerte verwendet (also keine Ableitungen berechnet) und für diskrete Zielfunktionen eingesetzt wird. Die Global Optimization Toolbox enthält weitere ableitungsfreie Optimierungsalgorithmen für die nichtlineare Optimierung.
  • Die Vertrauensbereich-Methode wird für unbeschränkte nicht-lineare Probleme verwendet und ist besonders bei komplexen Problemen nützlich, bei denen die Seltenheit oder Struktur ausgenutzt werden kann.
Ermittlung der optimalen Effizienz in einem Motorkennfeld durch nichtlineare Optimierung ohne Nebenbedingungen.
Ermittlung der optimalen Effizienz in einem Motorkennfeld durch nichtlineare Optimierung ohne Nebenbedingungen.

Nichtlineare Optimierung unter Nebenbedingungen

Nichtlineare Optimierungsprobleme mit Nebenbedingungen bestehen aus linearen oder nichtlinearen Zielfunktionen und können linearen oder ebenfalls nichtlinearen Nebenbedingungen unterliegen. Die Optimization Toolbox bietet vier Verfahren zur Lösung dieser Probleme:

  • Der Interior-Point-Algorithmus wird für allgemeine nicht-lineare Optimierungen verwendet. und eignet sich besonders für umfangreiche und komplexe Probleme. Basierend auf einer Barrierefunktion kann so gesteuert werden, dass alle Iterationswerte im Optimierungsverlauf streng in den zulässigen Grenzen bleiben.
  • Der SQP-Algorithmus wird für allgemeine nichtlineare Optimierungen verwendet. Er hält bei allen Iterationen immer die Grenzen ein und toleriert Berechnungsfehler anwenderdefinierter Ziel- und Beschränkungsfunktionen.
  • Die Active-Set-Methode wird für allgemeine nichtlineare Optimierungen verwendet.
  • Der Trust-Region-Reflective-Algorithmus kann nur für Probleme mit oberen und unteren Schranken oder für lineare Gleichungen als Nebenbedingungen verwendet werden. Er eignet sich besonders für Probleme mit sehr vielen Variablen.

Mit den Interior Point- und Trust-Region-Reflective-Algorithmen lassen sich Hesse-Matrizen mithilfe unterschiedlicher Verfahren berechnen.

Der Interior-Point-Algorithmus ermöglicht die näherungsweise Berechnung von Hesse-Matrizen durch die folgenden Verfahren:

  • BFGS (dicht besetzt)
  • Speicherreduziertes BFGS (für umfangreiche Probleme)
  • Hesse-Multiplikationsfunktion
  • Explizite Hesse-Matrix (dünn oder dicht besetzt)
  • Endliche Gradienten-Differenz (Besetzungsstruktur muss hier nicht bekannt sein)

Der Trust-Region-Reflective-Algorithmus verfügt über die Optionen:

  • Endliche Gradienten-Differenzen, Seltenheitsstruktur der Hessematrix
  • Explizite Hesse-Matrix (dünn oder dicht besetzt)
  • Hesse-Multiplikationsfunktion

Mit den Interior-Point - und Trust-Region -Verfahren lassen sich außerdem Produkte aus Hesse-Matrizen und Vektoren von Funktionen berechnen, ohne dass die Hesse-Matrix explizit formuliert werden muss.

Optimierung einer Fahrwerksaufhängung durch nichtlineare Optimierung mit Nebenbedingungen.
Optimierung einer Fahrwerksaufhängung durch nichtlineare Optimierung mit Nebenbedingungen.

Lineares und quadratisches Programmieren

Optimization Toolbox kann umfangreiche Probleme in der linearen und quadratischen Programmierung lösen.

Lineare Programmierung

Probleme in der linearen Programmierung umfassen die Minimierung oder Maximierung linearer Zielfunktionen mit Schranken, linearer Gleichheit sowie Ungleichungen als Nebenbedingungen. Lineare Programmierung wird im Finanzwesen, in der Energiegewinnung, im Operations Research Gebiet und in anderen Anwendungen angewendet, bei denen Beziehungen zwischen Variablen linear ausgedrückt werden können.

Die Optimization Toolbox umfasst drei Algorithmen zur Lösung von Problemen in der linearen Programmierung:

  • Der Algorithmus Simplex ist ein systematisches Verfahren zum Erstellen und Testen möglicher Eckpunktlösungen für ein lineares Programm und ist die am häufigsten verwendete Methode in der linearen Programmierung.
  • Das Interior-Point-Verfahren basiert auf einem Primal-Dual-Prädiktor-Korrektor-Algorithmus und wird für umfangreiche lineare Probleme eingesetzt. Diese Methode eignet sich vor allem für große Probleme, die eine definierte Struktur besitzen oder durch dünn besetzte Matrizen dargestellt werden können.
  • Das Active-Set-Verfahren minimiert die Zielfunktion bei jeder Iteration nur auf der Untermenge der lokal aktiven Nebenbedingungen, bis eine Lösung gefunden ist.
Nutzung der linearen Programmierung bei der Konstruktion einer Anlage zur Dampf- und Stromerzeugung.
Nutzung der linearen Programmierung bei der Konstruktion einer Anlage zur Dampf- und Stromerzeugung.

Quadratische Programmierung

Bei Problemen aus der Quadratischen Programmierung wird eine multivariate quadratische Funktion mit linearen Gleichungen oder Ungleichungen als Nebenbedingungen minimiert. Quadratische Programmierung wird für die Portfolio-Optimierung im Finanzwesen, Optimierung der Energiegewinnung in Elektrizitätswerken, Designoptimierung im Maschinenbau sowie für andere Anwendungen verwendet.

Die Optimization Toolbox bietet drei Methoden zur Lösung solcher Probleme an:

  • Der Interior-Point-Konvex-Algorithmus löst konvexe Probleme mit beliebigen Nebenbedingungen.
  • Das Trust-Region-Reflective-Verfahren wird zur Lösung von Problemen mit oberen und unteren Schranken sowie mit linearen Gleichungen als Nebenbedingungen eingesetzt.
  • Die Active-Set-Optimierung minimiert die Zielfunktion bei jeder Iteration nur auf der Untermenge der lokal aktiven Nebenbedingungen.

Optimization in MATLAB: An Introduction to Quadratic Programming 36:35
In this webinar, you will learn how MATLAB can be used to solve optimization problems using an example quadratic optimization problem and the symbolic math tools in MATLAB.

Sowohl der Interior-Point-Konvex-Algorithmus als auch der Trust-Region-Reflective-Algorithmus sind umfangreich und können darum für sehr große Probleme mit dünn besetzten Matrizen verwendet werden. Darüber hinaus verfügt der Interior-Point-Konvex-Algorithmus intern über optimierte Routinen für die Lineare Algebra sowie ein neues Presolve-Modul, das die Geschwindigkeit, die numerische Stabilität und das Erkennen unlösbarer Problemstellungen verbessert.

Quadratische Programmierung zur ertragsorientierten Analyse von drei Anlagefonds.
Quadratische Programmierung zur ertragsorientierten Analyse von drei Anlagefonds.

Gemischt-ganzzahlige lineare Programmierung

Bei der gemischt-ganzzahligen linearen Programmierung wird das Problem der linearen Programmierung mit der zusätzlichen Nebenbedingung weiterentwickelt, dass einige oder alle Variablen in der optimalen Lösung ganzzahlig sein müssen.

Für einige Optimierungsprobleme sollten die Variablen keine gebrochenen Werte umfassen. Wenn beispielsweise eine Variable die Anzahl von Aktien repräsentiert, die gekauft werden sollen, sollte diese nur aus ganzzahligen Werten bestehen. Gleichermaßen sollte eine Variable nur aus binären Werten (0 oder 1) bestehen, wenn diese den Status Ein/Aus eines Generators repräsentiert. Das Problem der gemischt-ganzzahligen linearen Programmierung ermöglicht durch Hinzufügen der Nebenbedingungen – nämlich, dass diese Variablen in der optimalen Lösung nur aus ganzen oder natürlichen Zahlen bestehen können – eine Modellierung dieses Verhaltens.

Gemischt-ganzzahlige lineare Programmierung in MATLAB 34:08
Einsatz des neuen Optimierungs-Solvers für gemischt-ganzzahlige lineare Programmierung in Release 2014a. Dieser neue Solver ermöglicht das Lösen von Optimierungsproblemen, bei denen eine oder alle Variablen ganzzahlige Werte annehmen müssen.

Optimization Toolbox löst Probleme gemischt-ganzzahliger linearer Programmierung durch die Verwendung eines Algorithmus, der Folgendes ausführt:

  • Vorverarbeitung der Programmierung ganzer Zahlen zur Einschränkung des ausführbaren Gebiets
  • Anwendung von Schnittebenen zur Einschränkung des ausführbaren Gebiets
  • Anwendung von Heuristik für die Suche nach ganzzahligen, ausführbaren Lösungen
  • Sicherstellung, dass keine bessere, ausführbare Lösung existiert, durch Lösung einer Reihe von linearen Relaxationsproblemen mit einem Zweig-und-Schranken-Algorithmus
Verwendung eines ganzzahligen Programmierungsproblems, um zu bestimmen, welche Investitionen gemacht werden sollten.
Verwendung eines ganzzahligen Programmierungsproblems, um zu bestimmen, welche Investitionen gemacht werden sollten.

Weitergabe der Anwendungen

Mit Solvern der Optimization Toolbox können Sie den MATLAB Compiler™ verwenden, um Werkzeuge zur Entscheidungsunterstützung zu erstellen, die mit Anwendern geteilt werden können, denen MATLAB nicht zur Verfügung steht. Diese Standalone-Anwendungen können ohne Lizenzgebühren für eine unbegrenzte Anzahl von Endnutzern angewendet werden. MATLAB Optimierungs-Algorithmen können auch mit anderen Sprachen integriert werden, z. B. Java® und .NET, welche Produkte der MATLAB Builder™-Reihe verwenden.

Mehrzieloptimierung

Aufgabe einer Mehrzieloptimierung ist die gleichzeitige Minimierung mehrerer Zielfunktionen mit verschiedenen Nebenbedingungen. Die Optimization Toolbox enthält Funktionen für zwei unterschiedliche Formulierungen von Mehrzielproblemen:

  • Beim Goal Attainment-Problem wird der Wert einer linearen oder nichtlinearen Vektorfunktion reduziert, bis die für einen Zielvektor vorgegebenen Zielwerte erreicht sind. Die relative Bedeutung der einzelnen Ziele wird in einem Gewichtungsvektor definiert. Das Goal Attainment-Problem kann dabei linearen und nichtlinearen Nebenbedingungen unterliegen.
  • Beim Minimax-Verfahren wird der ungünstigste Wert (oder Worst-Case-Wert) eines Systems multivariater Funktionen minimiert, die ebenfalls sowohl linearen als auch nichtlinearen Nebenbedingungen unterliegen können.

Die Optimization Toolbox wandelt beide Arten von Mehrzielproblemen in gewöhnliche Optimierungsprobleme mit Nebenbedingungen um und löst sie dann mithilfe des Active-Set-Verfahrens.

Die Global Optimization Toolbox enthält einen weiteren Mehrziel-Solver für nichtstetige Probleme.

Entwicklung eines Tiefpassfilters durch Mehrzieloptimierung.
Entwicklung eines Tiefpassfilters durch Mehrzieloptimierung.

Nichtlineare Methode der kleinsten Quadrate, Datenanpassung und nichtlineare Gleichungen

Die Optimization Toolbox kann nichtlineare kleinste Quadratprobleme, Datenanpassungsprobleme sowie nichtlineare Gleichungssysteme lösen.

Lineare und nichtlineare kleinste Quadrate

Die Toolbox bietet zwei Methoden zur Lösung linearer kleinste Quadrate-Probleme mit Nebenbedingungen an:

  • Der Active-Set Algorithmus dient der Lösung von Problemen mit Schranken und linearen Gleichungen und Ungleichungen.
  • Der Trust-Region-Reflective Algorithmus wird zur Lösung von umfangreichen Problemen verwendet, die ausschließlich Randbedingungen unterworfen sind.

Zur Lösung nichtlinearer kleinste Quadrate-Probleme stehen in der Toolbox ebenfalls zwei Algorithmen zur Verfügung:

  • Der Algorithmus Trust-region reflective implementiert den Levenberg-Marquardt-Algorithmus mithilfe von Vertrauensbereichen. Er wird für unbeschränkte und durch Randbedingungen beschränkte Probleme eingesetzt.
  • Das implementierte Levenberg-Marquardt-Verfahren basiert auf dem Standard-Levenberg-Marquardt-Algorithmus. Es wird für Probleme ohne Beschränkungen eingesetzt.
Anpassung einer transzendenten Gleichung mithilfe nichtlinearer kleinster Quadrate.
Anpassung einer transzendenten Gleichung mithilfe nichtlinearer kleinster Quadrate.

Daten-Fitting

Die Toolbox enthält eine spezielle Benutzeroberfläche für das Daten-Fitting. Mit diesem Tool lässt sich aus einer Familie nichtlinearer Funktionen diejenige Funktion ermitteln, die am besten zu einem gegebenen Satz von Datenpunkten passt. Für die dafür nötigen Datenanpassungen verwendet die Toolbox dieselben Methoden wie für nichtlineare kleinste Quadrate-Probleme.

Fitting einer nichtlinearen Exponentialgleichung durch kleinste Quadrate-Anpassung.
Fitting einer nichtlinearen Exponentialgleichung durch kleinste Quadrate-Anpassung.

Lösung nichtlinearer Gleichungen

Zur Lösung nichtlinearer Gleichungssysteme mit genau so vielen Gleichungen wie Unbekannten bietet die Optimization Toolbox ein Dogleg-Trust-Region-Verfahren an. Die Toolbox kann solche Probleme aber auch mithilfe der Trust-Region- und Levenberg-Marquardt-Verfahren lösen.

Lösung einer <em>n</em>-dimensionalen Rosenbrock-Funktion mit dem Solver für nichtlineare Gleichungen.
Lösung einer n-dimensionalen Rosenbrock-Funktion mit dem Solver für nichtlineare Gleichungen.

Parallel Computing und Ableitungen

Solver der Optimization Toolbox für nichtlineare Probleme verwenden gradientenbasierte Methoden zur Minimierung oder Maximierung eines Ziels. Informationen über den Gradienten der Zielfunktion können entweder unter Verwendung endlicher Differenzen durch den Solver geschätzt werden oder dem Solver durch den Anwender zur Verfügung gestellt werden.

Parallel Computing

Die Optimization Toolbox kann mit der Parallel Computing Toolbox kombiniert werden, um Probleme zu lösen, die von parallelen Rechenvorgängen profitieren. Durch parallele Berechnungen lässt sich in vielen Fällen die zur Lösung eines Problems benötigte Zeit verkürzen. Die Optimization Toolbox bietet die einfache Nutzung bereits implementierter Unterstützung für parallele Berechnungen oder erlaubt eine durch den Anwender definierte ParallelisierungMithilfe der integrierten Unterstützung für paralleles Rechnen lässt sich in verschiedenen Solvern der Schritt der Gradientenschätzung für nichtlineare Optimierungsprobleme mit Nebenbedingungen, Mehrziel-Goal-Attainment-Problemen und Minimax-Problemen beschleunigen.

Verkürzung der Lösungszeit eines Problems aus der Elektrostatik durch Nutzung der in einen Solver für die nichtlineare Optimierung integrierten Unterstützung für Parallel Computing. Diese integrierte Fähigkeit wird durch das Setzen der <tt>UseParallel</tt>-Option (links) für die Zielfunktion (Mitte rechts) und die Nebenbedingungsfunktion (unten rechts) aktiviert. Die Lösung ist oben rechts angezeigt.

Verkürzung der Lösungszeit eines Problems aus der Elektrostatik durch Nutzung der in einen Solver für die nichtlineare Optimierung integrierten Unterstützung für Parallel Computing. Diese integrierte Fähigkeit wird durch das Setzen der UseParallel-Option (links) für die Zielfunktion (Mitte rechts) und die Nebenbedingungsfunktion (unten rechts) aktiviert. Die Lösung ist oben rechts angezeigt.

Bei einer selbst definierten Parallelisierung muss der Anwender sein Optimierungsproblem explizit so einrichten, dass es parallele Berechnungen unterstützt. Dazu können sowohl die Zielfunktion als auch die Nebenbedingungs-Funktion parallelisiert werden. Je nach Bedarf können also die zur Ermittlung des Ziels und/oder der Nebenbedingung benötigte Zeit verkürzt werden.

Verkürzung der Rechenzeit (oben rechts) für ein Modell einer Fahrwerksaufhängung (unten links und unten rechts) mit Messunsicherheiten; die Zielfunktion muss dazu lediglich durch Veränderung einer einzigen Codezeile angepasst werden (oben links).

Verkürzung der Rechenzeit (oben rechts) für ein Modell einer Fahrwerksaufhängung (unten links und unten rechts) mit Messunsicherheiten; die Zielfunktion muss dazu lediglich durch Veränderung einer einzigen Codezeile angepasst werden (oben links).

Beschleunigen der Lösung von Optimierungsproblemen durch Parallel Computing 55:41
Schnellere Lösung von Optimierungsproblemen mit der Parallel Computing Toolbox.

Ableitungen liefern

Solver der Optimization Toolbox minimieren nichtlineare Funktionen, indem sie die partiellen Ableitungen der Zielfunktion unter Verwendung endlicher Differenzen schätzen. Alternativ dazu können Sie Funktionen definieren, die die Werte der partiellen Ableitungen berechnen und somit den Aufwand zur Schätzung der Ableitung deutlich verringern.

Die Berechnung partieller Ableitungen einer Zielfunktion kann eine langwierige Aufgabe sein. Durch symbolisches Ausdrücken des Problems mittels Symbolic Math Toolbox™ können Sie eingebaute Funktionen zur automatischen Berechnung partieller Ableitungen der Zielfunktion verwenden. Der MATLAB-Code kann zur Verwendung mit Solvern der Optimization Toolbox generiert werden.

Optimierung mit symbolischen Ableitungen (Technischer Artikel)

Probieren Sie Optimization Toolbox

Testsoftware anfordern

Mathematische Optimierung mit MATLAB

Webinar anzeigen