Direkt zum Inhalt

Lexikon der Mathematik: Methode der projizierten Gradienten

ein bestimmtes Abstiegsverfahren, das speziell für Optimierungsprobleme mit linearen Nebenbedingungen geeignet ist.

Man betrachte min f(x) unter den Nebenbedingungen hi(x) = 0, iI und gj(x) ≥ 0, jJ mit affin linearen Funktionen hi, gj und endlichen Indexmengen I, J. Von einem zulässigen Punkt x aus (der etwa durch Anwendung eines linearen Programmierungsverfahrens ermittelt werden kann) konstruiert man eine Abstiegsrichtung nach fol-gender Idee. Sei A die Matrix mit Zeilen Dhi(x) und Dgj(x) für jJ0(x) (d. h. die aktiven Indizes). A habe vollen Rang. Wählt man eine Richtung d ∈ ℝn mit A · d = 0, so ist d sicher zulässig. Daher sucht man ein d im Kern von A mit ∥d∥ = 1, das grad f(xd minimiert. Unter obigen Annahmen leistet dies gerade die normierte Projektion des negativen Gradienten – grad f(x) auf den Kern von A. Diese ist durch \begin{eqnarray}\mathrm{proj}(f,x)\,:=\,-(Id-{A}^{T}\cdot {(A\cdot {A}^{T})}^{-1}\cdot A)\cdot \mathrm{grad}\,f(x)\end{eqnarray}

gegeben. Sofern dieser Vektor nicht verschwindet, setzt man \begin{eqnarray}d:=\frac{\mathrm{proj}(f,x)}{||\mathrm{proj}(f,x)||}.\end{eqnarray}

Dann berechnet man die maximale Schrittweite t > 0 von x aus in Richtung d so, daß der neue Punkt x + t · d zulässig bleibt. Danach fährt man analog fort.

Probleme treten auf, wenn die Projektion den Nullvektor ergibt. Wichtig ist dann der Vektor \begin{eqnarray}p:=-{(A\cdot {A}^{T})}^{-1}\cdot A\cdot \mathrm{grad}f(x).\end{eqnarray}

Ist p ≥ 0, so erfüllt x die Karush-Kuhn-Tucker-Bedingung und ist (unter den bekannten Voraussetzungen) ein lokaler Minimalpunkt. Hat p dagegen negative Komponenten, so muß eine andere Abstiegsrichtung gewählt werden. Dies kann derart geschehen, daß eine in x aktive Ungleichung, die zu einer negativen Komponente in p führt, gestrichen wird.

Auch für nichtlineare Nebenbedingungen läßt sich ein ähnliches Verfahren entwerfen. Dann werden allerdings einzelne Aspekte wesentlich komplizierter, wie etwa der Umstand, daß die konstruierte Abstiegsrichtung i. allg. aus dem Zulässigkeitsbereich hinausführt. In diesem Fall muß eine Projektion in die zulässige Menge zurück durchgeführt werden.

  • Die Autoren
- Prof. Dr. Guido Walz

Schreiben Sie uns!

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.