Yacas Reloaded - Freies Computer Algebra System

Inhalt

Grundlagen der Mathematik

Differentialgleichungen

Funktionalanalysis

Differentialgeometrie

Topologie

Numerik

Numerische Verfahren

Optimierung

Lineare Optimierung

Konvexe Optimierung

Ausgleichungsrechnung

Optimale Steuerung

Stochastik

Unsortiertes

Anbieterkennzeichnung

Weiterbildung für alle! Über 200 Fernlehrgänge an Deutschlands größter Fernschule!

Konvexe Optimierung

Neu: Das Wurzelzieher Mathepedia Forum.

Jetzt registrieren und mit anderen Nutzern über Mathematik diskutieren!

Die Konvexe Optimierung ist ein Teilgebiet der mathematischen Optimierung. Es ist eine bestimmte Größe zu minimieren, die sogenannte Zielfunktion, welche von einem Parameter, welcher mit x bezeichnet wird, abhängt. Außerdem sind bestimmte Nebenbedingungen einzuhalten, d.h. die Werte x, die man wählen darf, sind gewissen Einschränkungen unterworfen. Diese sind meist in Form von Gleichungen und Ungleichungen gegeben. Sind für einen Wert x alle Nebenbedingungen eingehalten, so sagt man, dass x zulässig ist. Man spricht von einem konvexen Optimierungsproblem oder einem konvexen Programm, falls sowohl die Zielfunktion als auch die Menge der zulässigen Punkte konvex ist. Viele Probleme der Praxis sind konvexer Natur. Oft wird zum Beispiel auf Quadern optimiert, welche stets konvex sind, und als Zielfunktion finden oft quadratische Formen Verwendung, die unter bestimmten Voraussetzungen ebenfalls konvex sind. Ein anderer wichtiger Spezialfall ist die Lineare Optimierung, bei der eine lineare Zielfunktion über einem konvexen Polyeder optimiert wird.

Eine wichtige Eigenschaft der konvexen Optimierung im Unterschied zur nicht-konvexen Optimierung ist, dass jedes lokale Optimum auch ein globales Optimum ist. Anschaulich bedeutet dies, dass eine Lösung, die mindestens so gut ist wie alle anderen Lösungen in einer Umgebung, auch mindestens so gut ist wie alle zulässigen Lösungen. Dies erlaubt es, einfach nach lokalen Optima zu suchen.

Einleitung

Es gibt viele mögliche Formulierungen eines konvexen Programms. An dieser Stelle soll eine möglichst allgemeine Form gewählt werden. Der Eingabeparameter x sei aus dem , d.h. das Problem hängt von n Einflussparametern ab. Die Zielfunktion sei konvex. Weiterhin seien die konvexen Funktionen mit und die affinen Funktionen mit gegeben. Hierbei ist K eine konvexe Teilmenge des .

Konvexes Programm:

Minimiere f(x) mit unter den Nebenbedingungen

Eine Restriktion mit g_i (x) = 0 bezeichnet man als aktiv. Die Funktionen g_i stellen die sogenannten Ungleichungsnebenbedingungen und die Funktionen h_j stellen die sogenannten Gleichungsnebenbedingungen dar.

Beispiel

Konvexes Optimierungsproblem

Als Beispiel wird ein eindimensionales Problem ohne Gleichungsnebenbedingungen und mit nur einer Ungleichungsnebenbedingung betrachtet:

Minimiere f(x) = (x-1)² mit unter der Nebenbedingung:

Der zulässige Bereich ist gegeben durch die konvexe Menge

Der Zeichnung entnimmt man, dass für x = 1 der Optimalwert 0 angenommen wird.

Optimalitätsbedingungen

Zunächst werden notwendige Optimalitätsbedingungen vorgestellt. Dies sind Kriterien, die auf jeden Fall im Optimum erfüllt sein müssen. Danach werden hinreichende Optimalitätsbedingungen formuliert. Diese zeigen, dass eine Lösung wirklich optimal ist.

Fritz-John-Bedingungen

Sei optimal für das obige konvexe Programm. Dann gibt es Multiplikatoren , die nicht sämtlich den Wert 0 haben, mit den folgenden Eigenschaften:

(Complementary slackness condition)
für alle

Die Fritz-John-Bedingungen sind ein notwendiges Optimalitätskriterium. Für sind sie hinreichend. In diesem Fall darf man sogar setzen. Die complementary slackness condition wird im Deutschen auch Bedingung vom komplementären Schlupf genannt. Hierbei kann man beweisen, dass falls für alle gilt, dass dann alle Multiplikatoren für alle sein müssen. Diese Bedingung ist somit für den Aufbau und den Entwurf von Algorithmen von hoher Bedeutung.

Karush-Kuhn-Tucker-Bedingungen

Die Karush-Kuhn-Tucker-Bedingungen (auch bekannt als die KKT-Bedingungen) sind notwendig für die Optimalität einer Lösung in der nichtlinearen Optimierung. Sie stellen eine Verallgemeinerung der Lagrangen Multiplikatoren dar.

Notwendige Bedingungen

Sei die Zielfunktion und die konvexen Funktionen mit und die affinen Funktionen mit sind Nebenbedingungs-Funktionen. Es sei ein zulässiger Punkt, d.h. es gilt . Des Weiteren nimmt man an, dass die aktiven Funktionen g_i differenzierbar im Punkt sind, die Funktionen h_j sind stetig differenzierbar im Punkt . Falls ein lokales Minimum ist, dann existieren Konstanten mit und mit so dass

für alle

Außerdem gilt

für alle

und die Komplementaritätsbedingung ist erfüllt:

Regularitäts-Bedingungen

Für die obige notwendige Bedingung darf das duale Skalar gleich Null sein. In solchen Fällen spricht man von degeneriert oder abnormal. Dann spielt die notwendige Bedingung keine Rolle für die Eigenschaften der Funktion, nur die Geometrie der Nebenbedingungen ist relevant.

Es existieren mehrere Bedingungen, welche sicherstellen, dass die Lösung nicht-degeneriert ist, d.h. . Diese werden Constraint Qualifications genannt.

Hinreichende Bedingungen

Sei die Zielfunktion und die konvexen Funktionen mit und die affinen Funktionen mit sind Nebenbedingungs-Funktionen. Es sei ein zulässiger Punkt, d.h. es gilt . Des Weiteren nimmt man an, dass die aktiven Gradienten und die Gradienten linear unabhängig sind. Falls ein lokales Minimum ist, dann existieren Konstanten mit und mit so dass

für alle

dann ist der Punkt ein globales Minimum.

Constraint Qualifications

Ein Kriterium, welches sicherstellt, dass gilt, nennt man Constraint Qualification. Mit anderen Worten, eine Bedingung, die sicherstellt, dass die Fritz-John-Bedingungen auch die Karush-Kuhn-Tucker-Bedingungen erfüllen, nennt man Constraint Qualification.

Beispiele für Constraint Qualifications sind:

Slater: Es treten keine Gleichungsnebenbedingungen auf. Des weiteren gibt es einen Punkt , so dass für alle . An dieser Stelle sei erwähnt, dass die Constraint Qualification von Slater im Allgemeinen als die wichtigste angesehen wird.
Lineare Unabhängigkeit - Linear independence constraint qualification (LICQ): Die Gradienten der aktiven Ungleichungsbedingungen und die Gradienten der Gleichungsbedingungen sind linear unabhängig im Punkt .
Mangasarian-Fromowitz - Mangasarian-Fromowitz constraint qualification (MFCQ): Die Gradienten der aktiven Ungleichungsbedingungen und die Gradienten der Gleichungsbedingungen sind positiv-linear unabhängig im Punkt .
Konstanter Rang - Constant rank constraint qualification (CRCQ): Für jede Untermenge der Gradienten, der Ungleichungsbedingungen, welche aktiv sind, und der Gradienten der Gleichungsbedingungen ist der Rang in der Nähe von konstant.
Konstante positive-lineare Abhängigkeit - Constant positive-linear dependence constraint qualification (CPLD): Für jede Untermenge der Gradienten, der Ungleichungsbedingungen, welche aktiv sind, und der Gradienten der Gleichungsbedingungen, und falls eine positive-lineare Abhängigkeit im Punkt vorliegt, dann gibt es eine positiv-lineare Abhängigkeit in der Nähe von .

Man kann zeigen, dass die Folgerungen gelten

und

obwohl MFCQ nicht äquivalent zu CRCQ ist. In der Praxis werden schwächere Constraint Qualifications bevorzugt, da diese stärkere Optimalitäts-Bedingungen liefern.

Konkretes Vorgehen

Lagrange-Funktion

Zunächst wird die folgende abkürzende Schreibweise eingeführt:

wobei der Vektor aus allen Multiplikatoren ist.

Lagrangesche Multiplikatorenregel für das konvexe Problem

Vergleiche hierzu auch mit Lagrangesche Multiplikatorenregel. Konkretes Vorgehen:

Überprüfe, ob alle auftretenden Funktionen stetig partiell differenzierbar sind. Falls nein, ist diese Regel nicht anwendbar.
Gibt es einen zulässigen Punkt , für den gilt: ? Falls ja, dann ist optimal. Sonst fahre mit dem nächsten Schritt fort.
Bestimme den Gradienten der Lagrange-Funktion.
Löse das System , wobei kein Multiplikator negativ sein darf. Falls eine Restriktion aktiv ist, muss der zugehörige Multiplikator sogar gleich 0 sein. Findet man eine Lösung , so ist diese optimal.

Literatur

Avriel, Mordecai: Nonlinear Programming: Analysis and Methods. Dover Publishing, 2003, ISBN 0-486-43227-0.
R. Andreani, J. M. Martínez, M. L. Schuverdt: On the relation between constant positive linear dependence condition and quasinormality constraint qualification. Journal of optimization theory and applications, vol. 125, no2, 2005, pp. 473-485.
F. Jarre, J. Stoer: Optimierung. Springer, Berlin 2003, ISBN 3-540-43575-1.

Das ist ein Mittel, das Paradies nicht zu verfehlen: auf der einen Seite einen Mathematiker, auf der anderen einen Jesuiten; mit dieser Begleitung muß man seinen Weg machen, oder man macht ihn niemals.

Friedrich der Große

Druckansicht

Impressum: Wurzelzieher Mathepedia • Thomas Steinfeld • Dorfplatz 25 • 17237 Blankensee • Tel.: 01734332309 (Vodafone/D2) • Email: matһе@wυrzеlzιeher.de

Amazon.de empfiehlt: