Aufgabenstellung und Lösungsprinzip

Es wird das Optimierungsproblem

(18.114)

über dem beschränkten Bereich , der mit konvexen Funktionen durch beschrieben ist, betrachtet. Ein Problem mit nichtlinearer, aber konvexer Zielfunktion wird in diese Form überführt, indem

(18.115)

als weitere Nebenbedingung aufgenommen und

(18.116)

mit gelöst wird.
Die Grundidee des Verfahrens besteht in der iterativen linearen Approximation von M in der Nähe des Minimalpunktes durch konvexe Polyeder, womit das Ausgangsproblem auf eine Folge linearer Programme zurückgeführt wird.

Zunächst wird ein Polyeder

(18.117)

bestimmt. Aus dem linearen Programm

(18.118)

wird ein bezüglich optimaler Eckpunkt von P1 erhalten. Ist , dann ist die Optimallösung des Ausgangsproblems gefunden. Anderenfalls wird eine Hyperebene


die den Punkt von M trennt, ermittelt, so daß das neue Polyeder
(18.119)

erhalten wird.
Die Abbildung zeigt eine schematische Darstellung des Schnittebenenverfahrens.

Bild