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

Man betrachte min f(x) unter den Nebenbedingungen h_i(x) = 0, i ∈ I und g_j(x) ≥ 0, j ∈ J mit affin linearen Funktionen h_i, g_j 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 Dh_i(x) und Dg_j(x) für j ∈ J₀(x) (d. h. die aktiven Indizes). A habe vollen Rang. Wählt man eine Richtung d ∈ ℝⁿ 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(x)·d 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.