Quadratische Optimierung

Das Wichtigste auf einen Blick

• Quadratische Optimierung behandelt Optimierungsprobleme mit quadratischen Zielfunktionen und linearen Nebenbedingungen.
• Sie ist eine Verallgemeinerung der linearen Optimierung und kann konvex oder nicht-konvex sein.
• Konvexe quadratische Optimierungsprobleme lassen sich effizient mit speziellen Algorithmen lösen.
• Anwendungen finden sich in Finanzwesen, Technik, KI und Statistik.
• Die Lösungsmethoden umfassen u.a. das KKT-System, Interior-Point-Methoden und aktive Mengenverfahren.
• Quadratische Optimierung kann sowohl Minimierungs- als auch Maximierungsprobleme umfassen.

Überblick: Quadratische Optimierung

Die quadratische Optimierung ist ein zentraler Bereich der mathematischen Optimierung, bei dem die Zielfunktion eine quadratische Form annimmt. Dabei werden häufig lineare Nebenbedingungen berücksichtigt. Diese Art der Optimierung ist in vielen Disziplinen von Bedeutung, etwa in der Finanzwirtschaft zur Portfolio-Optimierung, in der Technik zur Steuerung von Systemen oder im maschinellen Lernen bei Support Vector Machines. Ziel ist es, die Werte der Variablen so zu bestimmen, dass die quadratische Funktion minimal oder maximal wird, während alle Nebenbedingungen erfüllt sind.

Definition der quadratischen Optimierung

Quadratische Optimierung bezeichnet die Klasse von Optimierungsproblemen, bei denen die Zielfunktion eine quadratische Form ist, also eine Funktion, die sich als xᵀQx + cᵀx + r darstellen lässt, wobei Q eine symmetrische Matrix, c ein Vektor und r ein Skalar ist. Die Optimierung erfolgt unter linearen Nebenbedingungen der Form Ax ≤ b oder Ax = b.

Mathematische Formulierung

Das allgemeine quadratische Optimierungsproblem kann formuliert werden als:

Minimiere f(x) = 1/2 xᵀQx + cᵀx
unter den Nebenbedingungen:
Ax ≤ b

Hierbei ist Q eine symmetrische n×n-Matrix, c ein n-dimensionaler Vektor, A eine m×n-Matrix und b ein m-dimensionaler Vektor.

Konvexe vs. nicht-konvexe quadratische Optimierung

Wenn die Matrix Q positiv semidefinit ist, spricht man von konvexer quadratischer Optimierung. Diese Probleme besitzen eine eindeutige globale Lösung und können effizient gelöst werden. Ist Q nicht positiv semidefinit, handelt es sich um nicht-konvexe Probleme, die deutlich schwieriger zu lösen sind und mehrere lokale Optima besitzen können.

Lösungsmethoden

Zur Lösung quadratischer Optimierungsprobleme werden verschiedene Verfahren eingesetzt:
- KKT-Bedingungen (Karush-Kuhn-Tucker) zur Charakterisierung von Optima
- Interior-Point-Methoden für große konvexe Probleme
- Aktive-Mengen-Methoden, die schrittweise Nebenbedingungen aktivieren oder deaktivieren
- Spezialisierte Algorithmen für spezielle Problemklassen, z.B. Support Vector Machines

Vergleich ausgewählter Lösungsverfahren

Anwendungsgebiete

Quadratische Optimierung wird in zahlreichen Bereichen angewandt:
- Finanzwesen: Portfolio-Optimierung zur Minimierung von Risiko bei gegebenem Ertrag
- Maschinelles Lernen: Training von Support Vector Machines
- Steuerungstechnik: Optimale Regelung von dynamischen Systemen
- Statistik: Regression mit quadratischen Kostenfunktionen
- Operations Research: Planung und Ressourcenallokation

Beispiel: Portfolio-Optimierung

Bei der Portfolio-Optimierung wird die Varianz des Portfolios (Risiko) minimiert, während eine bestimmte Rendite erreicht wird. Die Varianz lässt sich als quadratische Funktion der Portfolioanteile darstellen, und die Rendite als lineare Nebenbedingung.

Wichtig

Zusatzinformationen