Aufgabenstellung und Lösungsprinzip

Gegeben ist das konvexe Optimierungsproblem

mit . Eine zulässige Abstiegsrichtung im Punkt wird auf folgende Weise ermittelt: Ist eine zulässige Richtung, dann wird gesetzt. Anderenfalls liegt auf dem Rand von M und zeigt aus M hinaus. Mittels einer linearen Abbildung wird der Vektor auf eine lineare Teilmannigfaltigkeit des Randes von M projiziert, die von einer Teilmenge der in aktiven Restriktionen gebildet wird. Die Projektion auf eine Kante zeigt die folgende linke Abbildung, die Projektion auf eine Seitenfläche die rechte Abbildung.

Unter der Voraussetzung der Nichtentartungsbedingung, d.h. für alle sind die Vektoren , linear unabhängig, ist eine solche Projektion gegeben durch

Dabei besteht aus allen den , deren entsprechende Nebenbedingungen die lineare Teilmannigfaltigkeit bilden, in die projiziert werden soll.