Quadratische Programmierung - Quadratic programming

Quadratische Programmierung ( QP ) ist der Prozess sicher zur Lösung mathematische Optimierungsprobleme die quadratische Funktionen . Insbesondere versucht man, eine multivariate quadratische Funktion zu optimieren (minimieren oder maximieren), die linearen Beschränkungen der Variablen unterliegt . Quadratische Programmierung ist eine Art der nichtlinearen Programmierung .

"Programmieren" bezeichnet in diesem Zusammenhang ein formales Verfahren zur Lösung mathematischer Probleme. Diese Verwendung stammt aus den 1940er Jahren und ist nicht speziell an den neueren Begriff der "Computerprogrammierung" gebunden. Um Verwirrung zu vermeiden, bevorzugen einige Praktiker den Begriff "Optimierung" - zB "quadratische Optimierung".

Problem Formulierung

Das quadratische Programmierproblem mit $n$ Variablen und $m$ Randbedingungen kann wie folgt formuliert werden. Gegeben:

ein echter -wertige, $n$ -dimensionalen Vektors $c$ ,
eine $n \times n-$ dimensionale reelle symmetrische Matrix $Q$ ,
eine $m \times n-$ dimensionale reelle Matrix $A$ , und
ein $m-$ dimensionaler reeller Vektor $b$ ,

Das Ziel der quadratischen Programmierung besteht darin, einen $n-$ dimensionalen Vektor $x zu$ finden, der

minimieren	${\tfrac {1}{2}}\mathbf {x} ^{\mathrm {T} }Q\mathbf {x} +\mathbf {c} ^{\mathrm {T} }\mathbf {x }$
unterliegt	$A\mathbf{x}\preceq\mathbf{b},$

wobei $x T$ bezeichnet den Vektor Transponierte von $x$ , und die Notation $A x ⪯ b$ bedeutet , daß jeder Eintrag des Vektors $A x$ weniger als oder auf den entsprechenden Eintrag des Vektors gleich $b$ (komponentenweisen Ungleichheit).

Kleinsten Quadrate

Als Sonderfall , wenn Q ist symmetrisch positiv-definite verringert die Kostenfunktion der kleinsten Quadrate:

minimieren	${\tfrac {1}{2}}\\|R\mathbf {x} -\mathbf {d} \\|^{2}$
unterliegt	$A\mathbf{x}\preceq\mathbf{b},$

wobei $Q = R T R$ aus der Cholesky-Zerlegung von $Q$ folgt und $c = - R T d$ . Umgekehrt kann jedes solche eingeschränkte Kleinste-Quadrate-Programm äquivalent als QP gerahmt werden, sogar für eine generische nicht-quadratische $R-$ Matrix.

Verallgemeinerungen

Beim Minimieren einer Funktion $f$ in der Nähe eines Referenzpunkts $x 0$ wird $Q$ auf ihre Hesse-Matrix $H (f (x 0)) gesetzt$ und $c$ wird auf ihren Gradienten $\nabla f (x 0) gesetzt$ . Ein verwandtes Programmierproblem, quadratisch beschränkte quadratische Programmierung , kann durch Hinzufügen von quadratischen Beschränkungen zu den Variablen gestellt werden.

Lösungsmethoden

Für allgemeine Probleme werden häufig verschiedene Methoden verwendet, darunter

In dem Fall , in dem $Q$ ist positiv definit ist das Problem , ein Spezialfall des allgemeineren Bereich der konvexen Optimierung .

Gleichstellungsbeschränkungen

Quadratic - Programmierung ist besonders einfach , wenn $Q$ ist positiv definit und es gibt nur Gleichheitsbedingungen; insbesondere ist der Lösungsprozess linear. Indem man Lagrange-Multiplikatoren verwendet und das Extremum des Lagrange-Operators sucht, kann man leicht zeigen, dass die Lösung des gleichheitsbeschränkten Problems

{\text{Minimieren}}\quad {\tfrac {1}{2}}\mathbf {x} ^{\mathrm {T}}Q\mathbf {x} +\mathbf {c} ^{\ Mathrm {T} }\mathbf {x}

{\text{vorbehaltlich}}\quad E\mathbf {x} =\mathbf {d}

ist gegeben durch das lineare System

{\begin{bmatrix}Q&E^{\top }\\E&0\end{bmatrix}}{\begin{bmatrix}\mathbf {x} \\\lambda \end{bmatrix}}={\begin{ bmatrix}-\mathbf {c} \\\mathbf {d} \end{bmatrix}}

wobei $λ$ eine Menge von Lagrange-Multiplikatoren ist, die neben $x$ aus der Lösung hervorgehen .

Der einfachste Weg, sich diesem System zu nähern, ist die direkte Lösung (zB LU-Faktorisierung ), die für kleine Probleme sehr praktisch ist. Bei großen Problemen wirft das System einige ungewöhnliche Schwierigkeiten auf, vor allem, dass das Problem nie positiv definit ist (selbst wenn $Q$ ist), was es möglicherweise sehr schwierig macht, einen guten numerischen Ansatz zu finden, und es gibt viele Ansätze zur Auswahl, abhängig von der Problem.

Wenn die Beschränkungen die Variablen nicht zu eng koppeln, besteht ein relativ einfacher Angriff darin, die Variablen so zu ändern, dass Beschränkungen bedingungslos erfüllt werden. Nehmen wir zum Beispiel an, dass $d = 0 ist$ (eine Verallgemeinerung auf einen Wert ungleich Null ist unkompliziert). Betrachten Sie die Randbedingungsgleichungen:

E\mathbf{x} =0

eine neue Variable $y$ einführen, die durch . definiert ist

Z\mathbf{y} =\mathbf{x}

wobei $y$ die Dimension $x$ minus der Anzahl der Randbedingungen hat. Dann

EZ\mathbf {y} =\mathbf {0}

und wenn $Z$ so gewählt wird, dass $EZ = 0 ist, wird$ die Randbedingungsgleichung immer erfüllt. Um ein solches $Z$ zu finden, muss man den Nullraum von $E finden$ , was je nach Struktur von $E$ mehr oder weniger einfach ist . Das Einsetzen in die quadratische Form ergibt ein uneingeschränktes Minimierungsproblem:

{\tfrac {1}{2}}\mathbf {x} ^{\top}Q\mathbf {x} +\mathbf {c} ^{\top}\mathbf {x} \quad \implies\ quad {\tfrac {1}{2}}\mathbf {y} ^{\top }Z^{\top }QZ\mathbf {y} +\left(Z^{\top}\mathbf {c} \right )^{\top}\mathbf{y}

deren Lösung ist gegeben durch:

Z^{\top}QZ\mathbf{y} =-Z^{\top}\mathbf{c}

Unter bestimmten Bedingungen auf $Q$ wird die reduzierte Matrix $Z T QZ$ positiv definit sein. Es ist möglich, eine Variation des konjugierten Gradientenverfahrens zu schreiben , die die explizite Berechnung von $Z$ vermeidet .

Lagrangesche Dualität

Das Lagrange- Dual eines QP ist auch ein QP. Um dies zu sehen, konzentrieren wir uns auf den Fall, in dem $c = 0$ und $Q$ positiv definit ist. Wir schreiben die Lagrange- Funktion als

L(x,\lambda)={\tfrac {1}{2}}x^{\top }Qx+\lambda^{\top}(Ax-b).

Definieren wir die (Lagrangesche) Dualfunktion $g (λ)$ als , finden wir ein Infimum von $L$ , indem wir eine positive Bestimmtheit von $Q verwenden$ : $g(\lambda)=\inf_{x}L(x,\lambda)$ $\nabla_{x}L(x,\lambda)=0$

x^{*}=-Q^{-1}A^{\top}\lambda .

Daher ist die Doppelfunktion

g(\lambda)=-{\tfrac {1}{2}}\lambda ^{\top }AQ^{-1}A^{\top }\lambda -\lambda ^{\top }b ,

und damit ist das Lagrange-Dual der QP

{\text{maximieren}}_{\lambda \geq 0}\quad -{\tfrac {1}{2}}\lambda ^{\top }AQ^{-1}A^{\top } \lambda -\lambda^{\top}b

Neben der Lagrangeschen Dualitätstheorie gibt es noch andere Dualitätspaarungen (zB Wolfe etc.).

Komplexität

Für positiv definit $Q$ löst die Ellipsoidmethode das Problem in (schwach) polynomieller Zeit . Ist $Q$ hingegen unbestimmt, dann ist das Problem NP-schwer . Für diese nichtkonvexen Probleme kann es mehrere stationäre Punkte und lokale Minima geben. Selbst wenn $Q$ nur einen negativen Eigenwert hat , ist das Problem (stark) NP-schwer .

Integer-Beschränkungen

Es gibt einige Situationen, in denen ein oder mehrere Elemente des Vektors $x$ ganzzahlige Werte annehmen müssen . Dies führt zur Formulierung eines gemischt-ganzzahligen quadratischen Programmierproblems (MIQP). Anwendungen von MIQP umfassen Wasserressourcen und den Aufbau von Indexfonds .

Solver und Skript-(Programmier-)Sprachen

Name	Kurzinfo
ZIELE	Ein Softwaresystem zur Modellierung und Lösung von Optimierungs- und Scheduling-Problemen
ALGLIB	Dual lizenzierte (GPL/proprietäre) numerische Bibliothek (C++, .NET).
AMPL	Eine beliebte Modellierungssprache für die groß angelegte mathematische Optimierung.
APMonitor	Modellierung und Optimierung Suite für LP , QP, NLP , MILP , MINLP und DAE - Systeme in MATLAB und Python.
Artelys Knitro	Ein integriertes Paket für die nichtlineare Optimierung
CGAL	Ein Open-Source-Computational-Geometrie-Paket, das einen Solver für die quadratische Programmierung enthält.
CPLEX	Beliebter Solver mit einer API (C, C++, Java, .Net, Python, Matlab und R). Kostenlos für Akademiker.
Excel Solver-Funktion	Ein nichtlinearer Solver, der an Tabellenkalkulationen angepasst ist, in denen Funktionsbewertungen auf den neu berechneten Zellen basieren. Basisversion als Standard-Add-On für Excel verfügbar.
GAMS	Ein High-Level-Modellierungssystem zur mathematischen Optimierung
GNU Oktave	Eine kostenlose (seine Lizenz ist GPLv 3) universelle und matrixorientierte Programmiersprache für numerisches Rechnen, ähnlich MATLAB. Quadratische Programmierung in GNU Octave ist über den Befehl qp verfügbar
Gurobi	Solver mit parallelen Algorithmen für große lineare Programme, quadratische Programme und gemischt-ganzzahlige Programme. Kostenlos für den akademischen Gebrauch.
IMSL	Eine Reihe mathematischer und statistischer Funktionen, die Programmierer in ihre Softwareanwendungen einbetten können.
IPOPT	IPOPT (Interior Point OPtimizer) ist ein Softwarepaket zur großräumigen nichtlinearen Optimierung.
Ahorn	Universelle Programmiersprache für die Mathematik. Das Lösen eines quadratischen Problems in Maple erfolgt über den QPSolve- Befehl.
MATLAB	Eine universelle und matrixorientierte Programmiersprache für numerisches Rechnen. Quadratische Programmierung in MATLAB erfordert die Optimization Toolbox zusätzlich zum MATLAB-Basisprodukt
Mathematik	Eine universelle Programmiersprache für die Mathematik, einschließlich symbolischer und numerischer Fähigkeiten.
MOSEK	Ein Solver für die groß angelegte Optimierung mit API für mehrere Sprachen (C++, Java, .Net, Matlab und Python).
Numerische Bibliothek der NAG	Eine Sammlung mathematischer und statistischer Routinen, die von der Numerical Algorithms Group für mehrere Programmiersprachen (C, C++, Fortran, Visual Basic, Java und C#) und Pakete (MATLAB, Excel, R, LabVIEW) entwickelt wurden. Das Kapitel Optimierung der NAG-Bibliothek enthält Routinen für quadratische Programmierprobleme mit sowohl dünnbesetzten als auch nicht dünnbesetzten linearen Randbedingungsmatrizen, zusammen mit Routinen zur Optimierung von linearen, nichtlinearen Quadratsummen von linearen oder nichtlinearen Funktionen mit nichtlinearen, beschränkten oder keinen Randbedingungen . Die NAG-Bibliothek verfügt über Routinen sowohl für die lokale als auch für die globale Optimierung und für kontinuierliche oder ganzzahlige Probleme.
Python	High-Level-Programmiersprache mit Bindungen für die meisten verfügbaren Solver. Quadratische Programmierung ist über die Funktion sole_qp oder durch direkten Aufruf eines bestimmten Solvers verfügbar .
R (Fortra)	GPL- lizensiertes universelles plattformübergreifendes statistisches Berechnungs-Framework.
SAS /OR	Eine Suite von Solvern für lineare, ganzzahlige, nichtlineare, ableitungsfreie, Netzwerk-, kombinatorische und Beschränkungsoptimierung; die algebraische Modellierungssprache OPTMODEL; und eine Vielzahl von vertikalen Lösungen für spezifische Probleme/Märkte, die alle vollständig in das SAS-System integriert sind .
SuanShu	eine Open-Source-Suite von Optimierungsalgorithmen zur Lösung von LP , QP, SOCP , SDP , SQP in Java
TK-Löser	Softwaresystem für mathematische Modellierung und Problemlösung basierend auf einer deklarativen, regelbasierten Sprache, kommerzialisiert von Universal Technical Systems, Inc..
TOMLAB	Unterstützt globale Optimierung, Integer-Programmierung, alle Arten von kleinsten Quadraten, lineare, quadratische und uneingeschränkte Programmierung für MATLAB . TOMLAB unterstützt Solver wie Gurobi , CPLEX , SNOPT und KNITRO .
XPRESS	Solver für große lineare Programme, quadratische Programme, allgemeine nichtlineare und gemischt-ganzzahlige Programme. Hat API für mehrere Programmiersprachen, hat auch eine Modellierungssprache Mosel und arbeitet mit AMPL, GAMS . Kostenlos für den akademischen Gebrauch.

Siehe auch

Verweise

Weiterlesen

Cottle, Richard W.; Pang, Jong-Shi; Stein, Richard E. (1992). Das lineare Komplementaritätsproblem . Informatik und Wissenschaftliches Rechnen. Boston, MA: Academic Press, Inc. S. xxiv+762 S. ISBN 978-0-12-192350-1. MR 1.150.683 .
Garey, Michael R. ; Johnson, David S. (1979). Computer und Widerspenstigkeit: Ein Leitfaden zur Theorie der NP-Vollständigkeit . WH Freeman. ISBN 978-0-7167-1045-5. A6: MP2, S.245.
Gould, Nicholas IM; Toint, Philippe L. (2000). "Eine Bibliographie zur quadratischen Programmierung" (PDF) . Interner Bericht der RAL-Gruppe für Numerische Analyse 2000-1.

Externe Links

Languages

In other projects