Was ist quadratische Programmierung?

Quadratische Programmierung ist ein Verfahren, das verwendet wird, um eine multivariable quadratische Funktion zu optimieren, die linear beschränkt sein kann oder nicht. Viele reale Probleme, wie die Optimierung des Portfolios eines Unternehmens oder die Reduzierung der Kosten eines Herstellers, können mit einem quadratischen Programm beschrieben werden. Wenn die Zielfunktion konvex ist, dann kann eine zulässige Lösung existieren und kann durch bekannte Algorithmen wie den erweiterten Simplex-Algorithmus gelöst werden. Es gibt Methoden zum Lösen einiger nicht-konvexer quadratischer Funktionen, aber sie sind kompliziert und nicht ohne weiteres verfügbar.

Bei der quadratischen Programmierung werden mathematische Optimierungstechniken verwendet, um eine Zielfunktion zu minimieren. Die Zielfunktion besteht aus einer Anzahl von Entscheidungsvariablen, die begrenzt sein können oder nicht. Die Entscheidungsvariablen haben Potenzen 0, 1 oder 2. Die Zielfunktion kann einer Reihe von linearen Gleichheits- und Ungleichheitsbeschränkungen bezüglich der Entscheidungsvariablen unterworfen werden. Ein Beispiel für quadratische Programmierung ist: Minimiere f(x,y) = x2 + 3y2 – 12y + 12 wobei x + y = 6 und x > 0 und y ≥ 0 sind.

Es ist oft interessant, multivariate quadratische Funktionen zu verwenden, um Probleme der realen Welt zu beschreiben. Beispielsweise versucht ein Finanzanalyst mit der modernen Portfoliotheorie, das Portfolio eines Unternehmens zu optimieren, indem er den Anteil der Vermögenswerte wählt, der das mit einer bestimmten erwarteten Rendite verbundene Risiko minimiert. Eine quadratische Gleichung aus Asset-Gewichten und der Korrelation zwischen Assets beschreibt die Portfolio-Varianz, die durch quadratische Programmierung minimiert werden kann. Ein anderes Beispiel könnte ein Hersteller sein, der eine quadratische Gleichung verwendet, um die Beziehung zwischen verschiedenen Qualitätskomponenten und den Kosten eines Produkts zu beschreiben. Der Hersteller kann die Kosten minimieren und gleichzeitig bestimmte Standards beibehalten, indem er dem quadratischen Programm lineare Randbedingungen hinzufügt.

Eine der wichtigsten Bedingungen beim Lösen eines quadratischen Programms ist die Konvexität der Zielgleichung. Die Konvexität einer quadratischen Funktion wird durch die Hessesche oder die Matrix ihrer zweiten Ableitungen bestimmt. Die Funktion heißt konvex, wenn die Hesse-Matrix entweder positiv definit oder positiv semidefinit ist, dh wenn alle Eigenwerte positiv bzw. nicht negativ sind. Wenn der Hesse-Wert positiv ist und eine zulässige Lösung existiert, dann ist dieses lokale Minimum eindeutig und ein globales Minimum. Wenn das Hessische halbpositiv ist, ist eine zulässige Lösung möglicherweise nicht eindeutig. Nichtkonvexe quadratische Funktionen können lokale oder globale Minima haben, aber sie sind schwieriger zu bestimmen.

Es gibt viele Ansätze, eine konvexe quadratische Funktion mit quadratischer Programmierung zu lösen. Der gebräuchlichste Ansatz ist eine Erweiterung des Simplex-Algorithmus. Einige andere Verfahren umfassen die Methode des inneren Punktes oder der Barriere, die Methode des aktiven Satzes und die Methode des konjugierten Gradienten. Diese Methoden sind in bestimmte Programme wie Mathematica® und Matlab® integriert und in Bibliotheken für viele Programmiersprachen verfügbar.