www.wikidata.de-de.nina.az

Konvexe Optimierung Die konvexe Optimierung ist ein Teilgebiet der mathematischen Optimierung Es ist eine bestimmte Größ

Konvexe Optimierung

Die konvexe Optimierung ist ein Teilgebiet der mathematischen Optimierung.

Es ist eine bestimmte Größe zu minimieren, die sogenannte Zielfunktion, die von einem Parameter abhängt. Außerdem sind bestimmte Nebenbedingungen einzuhalten, das heißt, die Werte , 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 alle Nebenbedingungen eingehalten, so sagt man, dass 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 wie in der quadratischen Optimierung Verwendung, die unter bestimmten Voraussetzungen ebenfalls konvex sind (siehe Definitheit). 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.

Problemstellung Bearbeiten

Es gibt viele mögliche Formulierungen eines konvexen Programms. Eines der am häufigsten verwendeten und mathematisch am leichtesten handhabbaren ist

Der Eingabeparameter sei aus dem , das heißt, das Problem hängt von Einflussparametern ab. Die Zielfunktion sei konvex auf ihrem Definitionsbereich , genauso wie die Ungleichungsrestriktionen . Die sind auf ganz definierte affine Funktionen der Form . Die Menge

heißt dann die Definitionsmenge des konvexen Programms. Sie ist die größte Menge, auf der alle Funktionen definiert und konvex sind. Außerdem ist sie als Schnitt konvexer Mengen auch konvex. Die Funktionen stellen die sogenannten Ungleichungsnebenbedingungen und die Funktionen stellen die sogenannten Gleichungsnebenbedingungen dar. Die Funktion heißt die Zielfunktion und die Menge

die Restriktionsmenge des Problems. Sie ist eine konvexe Menge, da Subniveaumengen konvexer Funktionen wieder konvex sind.

Varianten Bearbeiten

Konkave Zielfunktion Bearbeiten

Meist werden auch Probleme der Form „Maximiere unter konvexen Nebenbedingungen“ als konvexe Probleme bezeichnet, wenn eine konkave Funktion ist. Dieses Problem ist äquivalent (nicht identisch) mit dem obigen Problem in dem Sinne, dass jeder Optimalpunkt des konkaven Problems auch ein Optimalpunkt des konvexen Problems ist, welches durch „minimiere unter konvexen Nebenbedingungen“ entsteht. Die Optimalwerte stimmen aber im Allgemeinen nicht überein.

Abstraktes konvexes Optimierungsproblem Bearbeiten

Manchmal werden Probleme der Form

als abstraktes konvexes Optimierungsproblem bezeichnet. Sie besitzen dieselben Lösbarkeitseigenschaften wie das obige Problem, sind aber mathematisch schwerer zu handhaben, da Kriterien wie algorithmisch schwer greifbar sind. Meist werden dann Funktionen gesucht, welche die abstrakte Nebenbedingung mittels Ungleichungen beschreiben, um das abstrakte Problem somit auf das obige Problem zurückzuführen. Umgekehrt kann aber auch jedes konvexe Problem als ein abstraktes konvexes Problem der Form „minimiere unter der Nebenbedingung “ formuliert werden. Hierbei ist die Restriktionsmenge.

Mischformen Bearbeiten

Die allgemeinste Form eines konvexen Problems besteht aus einer Mischform, die sowohl Ungleichungsrestriktionen, Gleichungsrestriktionen als auch abstrakte Nebenbedingungen verwendet. Aus den oben beschriebenen Gründen ist diese Form jedoch unpraktisch zu handhaben.

Lösbarkeit aus theoretischer Sicht Bearbeiten

Abstrakte konvexe Probleme zeichnen sich durch einige starke Eigenschaften aus, die das Auffinden von globalen Minima erleichtern:

  • Jedes lokale Minimum des Problems ist immer auch ein globales Minimum des Problems.
  • Die Menge der optimalen Punkte ist konvex. Sind nämlich optimal für das Problem, so ist aufgrund der Konvexität , da . Andererseits ist für alle Punkte der Restriktionsmenge , da und globale Minima sind. Somit ist für alle .
  • Ist die Zielfunktion strikt konvex, so ist der Optimalpunkt eindeutig.

Da jede Formulierung eines konvexen Problems in ein abstraktes Problem umgewandelt werden kann, übertragen sich alle diese Eigenschaften auf jede Formulierung des Problems.

Geschichte Bearbeiten

Carl Friedrich Gauß

Die Disziplin der konvexen Optimierung entstand unter anderem aus der konvexen Analysis. Die erste Optimierungs-Technik, welche als Gradientenverfahren bekannt ist, geht auf Gauß zurück. Im Jahre 1947 wurde das Simplex-Verfahren durch George Dantzig eingeführt. Des Weiteren wurden im Jahr 1968 erstmals Innere-Punkte-Verfahren durch Fiacco und McCormick vorgestellt. In den Jahren 1976 und 1977 wurde die Ellipsoid-Methode von David Yudin und Arkadi Nemirovski und unabhängig davon von Naum Schor zur Lösung konvexer Optimierungsprobleme entwickelt. Narendra Karmarkar beschrieb im Jahr 1984 zum ersten Mal einen polynomialen potentiell praktisch einsetzbaren Algorithmus für lineare Probleme. Im Jahr 1994 entwickelten Arkadi Nemirovski und Yurii Nesterov Innere-Punkte-Verfahren für die konvexe Optimierung, welche große Klassen von konvexen Optimierungsproblemen in polynomialer Zeit lösen konnten.

Bei den Karush-Kuhn-Tucker-Bedingungen wurden die notwendigen Bedingungen für die Ungleichheits-Einschränkung zum ersten Mal 1939 in der Master-Arbeit (unveröffentlicht) von William Karush aufgeführt. Bekannter wurden diese jedoch erst 1951 nach einem Konferenz-Paper von Harold W. Kuhn und Albert W. Tucker.

Vor 1990 lag die Anwendung der konvexen Optimierung hauptsächlich im Operations Research und weniger im Bereich der Ingenieure. Seit 1990 boten sich jedoch immer mehr Anwendungsmöglichkeiten in der Ingenieurwissenschaft. Hier lässt sich unter anderem die Kontroll- und Signal-Steuerung, die Kommunikation und der Schaltungsentwurf nennen. Darüber hinaus ist das Konzept vor allem für die Strukturmechanik effizient. Außerdem entstanden neue Problemklassen wie semidefinite und Kegel-Optimierung 2. Ordnung und robuste Optimierung.

Beispiel Bearbeiten

Konvexes Optimierungsproblem

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

Minimiere

unter der Nebenbedingung:

Der zulässige Bereich ist gegeben durch die konvexe Menge

denn für Werte ist nicht erfüllt. Der Zeichnung kann entnommen werden, dass für den Optimalwert annimmt.

Klassifikation und Verallgemeinerungen Bearbeiten

Die konvexe Optimierung enthält weitere Klassen von Optimierungsproblemen, die sich alle durch eine spezielle Struktur auszeichnen:

Außerdem wird unterschieden, ob die verwendeten Funktionen stetig differenzierbar sind oder nicht.

Unter gewissen Voraussetzungen fallen noch folgende Problemklassen unter die konvexe Optimierung:

Verallgemeinerungen, die noch einige Eigenschaften einer konvexen Funktion erhalten, machen gewisse erweiterte Begriffe der konvexen Optimierung möglich.

  • Pseudokonvexe Funktionen sind eine Klasse von differenzierbaren Funktionen, bei denen ein globales Minimum vorliegt, wenn die Ableitung verschwindet.
  • Bei quasikonvexen Funktionen sind die Subniveaumengen alle konvex. Lässt man somit quasikonvexe Funktionen als Ungleichungsrestriktionen zu, so ist die Restriktionsmenge als Schnitt der Subniveaumengen immer noch eine konvexe Menge. Man erhält somit ein abstraktes konvexes Optimierungsproblem.
  • K-konvexe Funktion verwenden verallgemeinerte Ungleichungen, um Konvexität für Halbordnungen auf dem zu verallgemeinern. Dabei werden echte Kegel im definiert und dementsprechend Funktionen , die K-konvex bezüglich des Kegels und der verallgemeinerten Ungleichung sind. Das Problem lautet dann

Optimalitätsbedingungen Bearbeiten

Für konvexe Probleme gibt es einige wichtige Optimalitätskriterien. Zuerst werden die notwendigen Kriterien beschrieben, das heißt, wenn ein Optimum erreicht wird, dann sind diese Kriterien erfüllt. Danach die hinreichenden Kriterien, das heißt, wenn diese Kriterien in einem Punkt erfüllt sind, dann handelt es sich um einen Optimalpunkt.

Notwendige Kriterien Bearbeiten

Karush-Kuhn-Tucker-Bedingungen Bearbeiten

Die Karush-Kuhn-Tucker-Bedingungen (auch bekannt als die KKT-Bedingungen) sind eine Verallgemeinerung der Lagrange-Multiplikatoren von Optimierungsproblemen unter Nebenbedingungen und finden in der fortgeschrittenen neoklassischen Theorie Anwendung. Ein zulässiger Punkt des konvexen Problems erfüllt die KKT-Bedingungen, wenn gilt

Diese Bedingungen werden die Karush-Kuhn-Tucker-Bedingungen oder kurz KKT-Bedingungen genannt.

Ein Punkt heißt dann Karush-Kuhn-Tucker-Punkt oder kurz KKT-Punkt des obigen Optimierungsproblems, wenn er die obigen Bedingungen erfüllt.

Das eigentliche notwendige Optimalitätskriterium lautet nun: Ist ein Punkt ein lokales (und aufgrund der Konvexität auch globales) Minimum des konvexen Problems, und erfüllt er gewisse Regularitätsvoraussetzungen, so gibt es , so dass ein KKT-Punkt ist. Gängige Regularitätsbedingungen (auch constraint qualifications genannt) sind die LICQ, die MFCQ, die Abadie CQ oder speziell für konvexe Probleme die Slater-Bedingung. Mehr Regularitätsvoraussetzungen finden sich im Hauptartikel zu den KKT-Bedingungen.

Fritz-John-Bedingungen Bearbeiten

Die Fritz-John-Bedingungen oder FJ-Bedingungen sind eine Verallgemeinerung der KKT-Bedingungen und kommen im Gegensatz zu diesen ohne Regularitätsvoraussetzungen aus. Unter gewissen Umständen sind beide Bedingungen äquivalent. Ein Punkt heißt Fritz-John-Punkt oder kurz FJ-Punkt des konvexen Problems, wenn er die folgenden Bedingungen erfüllt:

Diese Bedingungen werden die Fritz-John-Bedingungen oder kurz FJ-Bedingungen genannt.

Ist der Punkt lokales (und aufgrund der Konvexität auch globales) Minimum des Optimierungsproblems, so gibt es , so dass ein FJ-Punkt ist und ungleich dem Nullvektor ist.

Hinreichende Kriterien Bearbeiten

Ist ein KKT-Punkt, so ist ein globales Minimum des konvexen Problems. Somit sind die KKT-Bedingungen im konvexen Fall schon hinreichend für die Optimalität des Punktes. Insbesondere werden dazu keine weiteren Regularitätsvoraussetzungen benötigt. Da sich zeigen lässt, dass man aus jedem FJ-Punkt einen KKT-Punkt konstruieren kann, wenn ist, sind auch schon die FJ-Bedingungen hinreichend für die Optimalität, wenn gilt.

Kriterien für nicht differenzierbare Funktionen Bearbeiten

Sind einige der verwendeten Funktionen des konvexen Optimierungsproblems nicht differenzierbar, so kann man noch auf die Sattelpunktcharakterisierung von Optimalpunkten zurückgreifen. Mittels der Lagrange-Funktion lässt sich dann zeigen, dass jeder Sattelpunkt der Lagrange-Funktion eine Optimallösung ist. Umgekehrt ist eine Optimallösung und die Slater-Bedingung erfüllt, so kann man die Optimallösung zu einem Sattelpunkt der Lagrange-Funktion erweitern.

Konkretes Vorgehen Bearbeiten

Lagrange-Funktion Bearbeiten

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

wobei der Vektor aus allen Multiplikatoren ist.

Lagrangesche Multiplikatorenregel für das konvexe Problem Bearbeiten

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 nicht aktiv ist, muss der zugehörige Multiplikator sogar gleich sein. Findet man eine Lösung , so ist diese optimal.

Literatur Bearbeiten

  • 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, no. 2, 2005, pp. 473–485.
  • Florian Jarre, Josef Stoer: Optimierung. Springer, Berlin 2003, ISBN 3-540-43575-1.
  • Schmit, L.A.; Fleury, C. 1980: Structural synthesis by combining approximation concepts and dual methods. J. Amer. Inst. Aeronaut. Astronaut 18, 1252–1260

Weblinks Bearbeiten

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Die konvexe Optimierung ist ein Teilgebiet der mathematischen Optimierung Es ist eine bestimmte Grosse zu minimieren die sogenannte Zielfunktion die von einem Parameter x displaystyle x abhangt Ausserdem sind bestimmte Nebenbedingungen einzuhalten das heisst die Werte x displaystyle x die man wahlen darf sind gewissen Einschrankungen unterworfen Diese sind meist in Form von Gleichungen und Ungleichungen gegeben Sind fur einen Wert x displaystyle x alle Nebenbedingungen eingehalten so sagt man dass x displaystyle x zulassig ist Man spricht von einem konvexen Optimierungsproblem oder einem konvexen Programm falls sowohl die Zielfunktion als auch die Menge der zulassigen 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 wie in der quadratischen Optimierung Verwendung die unter bestimmten Voraussetzungen ebenfalls konvex sind siehe Definitheit Ein anderer wichtiger Spezialfall ist die Lineare Optimierung bei der eine lineare Zielfunktion uber 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 Losung die mindestens so gut ist wie alle anderen Losungen in einer Umgebung auch mindestens so gut ist wie alle zulassigen Losungen Dies erlaubt es einfach nach lokalen Optima zu suchen Inhaltsverzeichnis 1 Problemstellung 1 1 Varianten 1 1 1 Konkave Zielfunktion 1 1 2 Abstraktes konvexes Optimierungsproblem 1 1 3 Mischformen 2 Losbarkeit aus theoretischer Sicht 3 Geschichte 4 Beispiel 5 Klassifikation und Verallgemeinerungen 6 Optimalitatsbedingungen 6 1 Notwendige Kriterien 6 1 1 Karush Kuhn Tucker Bedingungen 6 1 2 Fritz John Bedingungen 6 2 Hinreichende Kriterien 6 3 Kriterien fur nicht differenzierbare Funktionen 7 Konkretes Vorgehen 7 1 Lagrange Funktion 7 2 Lagrangesche Multiplikatorenregel fur das konvexe Problem 8 Literatur 9 WeblinksProblemstellung BearbeitenEs gibt viele mogliche Formulierungen eines konvexen Programms Eines der am haufigsten verwendeten und mathematisch am leichtesten handhabbaren ist Minimiere f x unter den Nebenbedingungen g i x 0 i 1 k h j x 0 j 1 l displaystyle begin aligned text Minimiere amp f x amp text unter den Nebenbedingungen amp g i x leq 0 amp i 1 dots k amp h j x 0 amp j 1 dots l end aligned nbsp Der Eingabeparameter x displaystyle x nbsp sei aus dem R n displaystyle mathbb R n nbsp das heisst das Problem hangt von n displaystyle n nbsp Einflussparametern ab Die Zielfunktion f D 0 R displaystyle f colon D 0 rightarrow mathbb R nbsp sei konvex auf ihrem Definitionsbereich D 0 displaystyle D 0 nbsp genauso wie die Ungleichungsrestriktionen g i D i R displaystyle g i colon D i rightarrow mathbb R nbsp Die h j x displaystyle h j x nbsp sind auf ganz R n displaystyle mathbb R n nbsp definierte affine Funktionen der Form h j x a j T x b j displaystyle h j x a j T x b j nbsp Die Menge D m 0 k D m displaystyle mathcal D bigcap m 0 k D m nbsp heisst dann die Definitionsmenge des konvexen Programms Sie ist die grosste Menge auf der alle Funktionen definiert und konvex sind Ausserdem ist sie als Schnitt konvexer Mengen auch konvex Die Funktionen g i displaystyle g i nbsp stellen die sogenannten Ungleichungsnebenbedingungen und die Funktionen h j displaystyle h j nbsp stellen die sogenannten Gleichungsnebenbedingungen dar Die Funktion f displaystyle f nbsp heisst die Zielfunktion und die Menge R x D R n g i x 0 h j x 0 fur alle i j displaystyle mathcal R x in mathcal D subset mathbb R n g i x leq 0 h j x 0 text fur alle i j nbsp die Restriktionsmenge des Problems Sie ist eine konvexe Menge da Subniveaumengen konvexer Funktionen wieder konvex sind Varianten Bearbeiten Konkave Zielfunktion Bearbeiten Meist werden auch Probleme der Form Maximiere f x displaystyle f x nbsp unter konvexen Nebenbedingungen als konvexe Probleme bezeichnet wenn f x displaystyle f x nbsp eine konkave Funktion ist Dieses Problem ist aquivalent nicht identisch mit dem obigen Problem in dem Sinne dass jeder Optimalpunkt des konkaven Problems auch ein Optimalpunkt des konvexen Problems ist welches durch minimiere f x displaystyle f x nbsp unter konvexen Nebenbedingungen entsteht Die Optimalwerte stimmen aber im Allgemeinen nicht uberein Abstraktes konvexes Optimierungsproblem Bearbeiten Manchmal werden Probleme der Form Minimiere f x unter den Nebenbedingungen x K K ist konvexe Menge displaystyle begin aligned text Minimiere amp f x amp text unter den Nebenbedingungen amp x in K amp K text ist konvexe Menge end aligned nbsp als abstraktes konvexes Optimierungsproblem bezeichnet Sie besitzen dieselben Losbarkeitseigenschaften wie das obige Problem sind aber mathematisch schwerer zu handhaben da Kriterien wie x K displaystyle x in K nbsp algorithmisch schwer greifbar sind Meist werden dann Funktionen gesucht welche die abstrakte Nebenbedingung x K displaystyle x in K nbsp mittels Ungleichungen beschreiben um das abstrakte Problem somit auf das obige Problem zuruckzufuhren Umgekehrt kann aber auch jedes konvexe Problem als ein abstraktes konvexes Problem der Form minimiere f x displaystyle f x nbsp unter der Nebenbedingung x R displaystyle x in mathcal R nbsp formuliert werden Hierbei ist R displaystyle mathcal R nbsp die Restriktionsmenge Mischformen Bearbeiten Die allgemeinste Form eines konvexen Problems besteht aus einer Mischform die sowohl Ungleichungsrestriktionen Gleichungsrestriktionen als auch abstrakte Nebenbedingungen verwendet Aus den oben beschriebenen Grunden ist diese Form jedoch unpraktisch zu handhaben Losbarkeit aus theoretischer Sicht BearbeitenAbstrakte konvexe Probleme zeichnen sich durch einige starke Eigenschaften aus die das Auffinden von globalen Minima erleichtern Jedes lokale Minimum des Problems ist immer auch ein globales Minimum des Problems Die Menge der optimalen Punkte ist konvex Sind namlich x y displaystyle x y nbsp optimal fur das Problem so ist aufgrund der Konvexitat f l x 1 l y l f x 1 l f y f x displaystyle f lambda x 1 lambda y leq lambda f x 1 lambda f y f x nbsp da f x f y displaystyle f x f y nbsp Andererseits ist f x f y f z displaystyle f x f y leq f z nbsp fur alle Punkte z displaystyle z nbsp der Restriktionsmenge R displaystyle mathcal R nbsp da f x displaystyle f x nbsp und f y displaystyle f y nbsp globale Minima sind Somit ist f l x 1 l y f x displaystyle f lambda x 1 lambda y f x nbsp fur alle l 0 1 displaystyle lambda in 0 1 nbsp Ist die Zielfunktion strikt konvex so ist der Optimalpunkt eindeutig Da jede Formulierung eines konvexen Problems in ein abstraktes Problem umgewandelt werden kann ubertragen sich alle diese Eigenschaften auf jede Formulierung des Problems Geschichte Bearbeiten nbsp Carl Friedrich GaussDie Disziplin der konvexen Optimierung entstand unter anderem aus der konvexen Analysis Die erste Optimierungs Technik welche als Gradientenverfahren bekannt ist geht auf Gauss zuruck Im Jahre 1947 wurde das Simplex Verfahren durch George Dantzig eingefuhrt Des Weiteren wurden im Jahr 1968 erstmals Innere Punkte Verfahren durch Fiacco und McCormick vorgestellt In den Jahren 1976 und 1977 wurde die Ellipsoid Methode von David Yudin und Arkadi Nemirovski und unabhangig davon von Naum Schor zur Losung konvexer Optimierungsprobleme entwickelt Narendra Karmarkar beschrieb im Jahr 1984 zum ersten Mal einen polynomialen potentiell praktisch einsetzbaren Algorithmus fur lineare Probleme Im Jahr 1994 entwickelten Arkadi Nemirovski und Yurii Nesterov Innere Punkte Verfahren fur die konvexe Optimierung welche grosse Klassen von konvexen Optimierungsproblemen in polynomialer Zeit losen konnten Bei den Karush Kuhn Tucker Bedingungen wurden die notwendigen Bedingungen fur die Ungleichheits Einschrankung zum ersten Mal 1939 in der Master Arbeit unveroffentlicht von William Karush aufgefuhrt Bekannter wurden diese jedoch erst 1951 nach einem Konferenz Paper von Harold W Kuhn und Albert W Tucker Vor 1990 lag die Anwendung der konvexen Optimierung hauptsachlich im Operations Research und weniger im Bereich der Ingenieure Seit 1990 boten sich jedoch immer mehr Anwendungsmoglichkeiten in der Ingenieurwissenschaft Hier lasst sich unter anderem die Kontroll und Signal Steuerung die Kommunikation und der Schaltungsentwurf nennen Daruber hinaus ist das Konzept vor allem fur die Strukturmechanik effizient Ausserdem entstanden neue Problemklassen wie semidefinite und Kegel Optimierung 2 Ordnung und robuste Optimierung Beispiel Bearbeiten nbsp Konvexes OptimierungsproblemAls Beispiel wird ein eindimensionales Problem ohne Gleichungsnebenbedingungen und mit nur einer Ungleichungsnebenbedingung betrachtet Minimiere f x x 2 2 displaystyle f x x 2 2 nbsp mit x K 0 displaystyle x in K 0 infty nbsp unter der Nebenbedingung g x x 2 1 0 displaystyle g x x 2 1 leq 0 nbsp Der zulassige Bereich ist gegeben durch die konvexe Menge x K g x 0 0 1 displaystyle x in K g x leq 0 0 1 nbsp denn fur Werte x gt 1 displaystyle x gt 1 nbsp ist g x 0 displaystyle g x leq 0 nbsp nicht erfullt Der Zeichnung kann entnommen werden dass f x displaystyle f x nbsp fur x 1 displaystyle x 1 nbsp den Optimalwert 1 displaystyle 1 nbsp annimmt Klassifikation und Verallgemeinerungen BearbeitenDie konvexe Optimierung enthalt weitere Klassen von Optimierungsproblemen die sich alle durch eine spezielle Struktur auszeichnen Konische Programme Es werden verallgemeinerte Ungleichungen verwendet ansonsten sind alle Funktionen affin Konische Programme haben wiederum drei Teilgebiete Semidefinite Programme verwenden den Kegel der positiv semidefiniten Matrizen haben also als Variable eine Matrix Die verwendete verallgemeinerte Ungleichung ist dann die Loewner Halbordnung Die SOCPs Second Order Cone Program verwenden den second order cone der auch Lorentz Kegel genannt wird Auch lineare Optimierungsprobleme lassen sich als konische Programme formulieren Ausserdem wird unterschieden ob die verwendeten Funktionen stetig differenzierbar sind oder nicht Unter gewissen Voraussetzungen fallen noch folgende Problemklassen unter die konvexe Optimierung Quadratische Programme und Quadratische Programme mit quadratischen Nebenbedingungen sind konvexe Probleme wenn alle auftretenden Matrizen positiv semidefinit sind Geometrische Programme sind per se keine konvexen Probleme lassen sich aber durch elementare Substitutionen in eine konvexe Form uberfuhren Verallgemeinerungen die noch einige Eigenschaften einer konvexen Funktion erhalten machen gewisse erweiterte Begriffe der konvexen Optimierung moglich Pseudokonvexe Funktionen sind eine Klasse von differenzierbaren Funktionen bei denen ein globales Minimum vorliegt wenn die Ableitung verschwindet Bei quasikonvexen Funktionen sind die Subniveaumengen alle konvex Lasst man somit quasikonvexe Funktionen als Ungleichungsrestriktionen zu so ist die Restriktionsmenge als Schnitt der Subniveaumengen immer noch eine konvexe Menge Man erhalt somit ein abstraktes konvexes Optimierungsproblem K konvexe Funktion verwenden verallgemeinerte Ungleichungen um Konvexitat fur Halbordnungen auf dem R n displaystyle mathbb R n nbsp zu verallgemeinern Dabei werden l displaystyle l nbsp echte Kegel im R k i displaystyle mathbb R k i nbsp definiert und dementsprechend l displaystyle l nbsp Funktionen g i R n R k i displaystyle g i colon mathbb R n mapsto mathbb R k i nbsp die K konvex bezuglich des Kegels K i displaystyle K i nbsp und der verallgemeinerten Ungleichung K i displaystyle preccurlyeq K i nbsp sind Das Problem lautet dannMinimiere f x unter den Nebenbedingungen g i x K i 0 i 1 l H x b 0 displaystyle begin aligned text Minimiere amp f x amp text unter den Nebenbedingungen amp g i x preccurlyeq K i 0 amp i 1 dots l amp Hx b 0 amp end aligned nbsp dd fur eine konvexe Funktion f displaystyle f nbsp und eine passend dimensionierte Matrix H displaystyle H nbsp und einen Vektor b displaystyle b nbsp Da auch die Subniveaumengen einer K konvexen Funktion konvex sind liefert dies auch wieder ein abstraktes konvexes Optimierungsproblem Eine weitere Verallgemeinerung sind die fast konvexen Funktionen Sie bilden im Allgemeinen kein abstraktes konvexes Optimierungsproblem mehr dafur gilt bei ihnen wie bei konvexen Problemen die starke Dualitat wenn sie die Slater Bedingung erfullen Allgemeiner lassen sich konvexe Abbildungen fur jeden reellen Vektorraum mit Ordnungskegel definieren Optimalitatsbedingungen BearbeitenFur konvexe Probleme gibt es einige wichtige Optimalitatskriterien Zuerst werden die notwendigen Kriterien beschrieben das heisst wenn ein Optimum erreicht wird dann sind diese Kriterien erfullt Danach die hinreichenden Kriterien das heisst wenn diese Kriterien in einem Punkt erfullt sind dann handelt es sich um einen Optimalpunkt Notwendige Kriterien Bearbeiten Karush Kuhn Tucker Bedingungen Bearbeiten Hauptartikel Karush Kuhn Tucker Bedingungen Die Karush Kuhn Tucker Bedingungen auch bekannt als die KKT Bedingungen sind eine Verallgemeinerung der Lagrange Multiplikatoren von Optimierungsproblemen unter Nebenbedingungen und finden in der fortgeschrittenen neoklassischen Theorie Anwendung Ein zulassiger Punkt x displaystyle x nbsp des konvexen Problems erfullt die KKT Bedingungen wenn gilt f x i 1 m m i g i x j 1 l l j h j x 0 displaystyle nabla f x sum i 1 m mu i nabla g i x sum j 1 l lambda j nabla h j x 0 nbsp g i x 0 fur i 1 m displaystyle g i x leq 0 text fur i 1 ldots m nbsp h j x 0 fur j 1 l displaystyle h j x 0 text fur j 1 ldots l nbsp m i 0 fur i 1 m displaystyle mu i geq 0 text fur i 1 ldots m nbsp m i g i x 0 fur i 1 m displaystyle mu i g i x 0 text fur i 1 ldots m nbsp Diese Bedingungen werden die Karush Kuhn Tucker Bedingungen oder kurz KKT Bedingungen genannt Ein Punkt x m l R n m l displaystyle x mu lambda in mathbb R n m l nbsp heisst dann Karush Kuhn Tucker Punkt oder kurz KKT Punkt des obigen Optimierungsproblems wenn er die obigen Bedingungen erfullt Das eigentliche notwendige Optimalitatskriterium lautet nun Ist ein Punkt x displaystyle x nbsp ein lokales und aufgrund der Konvexitat auch globales Minimum des konvexen Problems und erfullt er gewisse Regularitatsvoraussetzungen so gibt es m l displaystyle mu lambda nbsp so dass x m l displaystyle x mu lambda nbsp ein KKT Punkt ist Gangige Regularitatsbedingungen auch constraint qualifications genannt sind die LICQ die MFCQ die Abadie CQ oder speziell fur konvexe Probleme die Slater Bedingung Mehr Regularitatsvoraussetzungen finden sich im Hauptartikel zu den KKT Bedingungen Fritz John Bedingungen Bearbeiten Hauptartikel Fritz John Bedingungen Die Fritz John Bedingungen oder FJ Bedingungen sind eine Verallgemeinerung der KKT Bedingungen und kommen im Gegensatz zu diesen ohne Regularitatsvoraussetzungen aus Unter gewissen Umstanden sind beide Bedingungen aquivalent Ein Punkt z x m l R 1 n m l displaystyle z x mu lambda in mathbb R 1 n m l nbsp heisst Fritz John Punkt oder kurz FJ Punkt des konvexen Problems wenn er die folgenden Bedingungen erfullt z f x i 1 m m i g i x j 1 l l j h j x 0 displaystyle z nabla f x sum i 1 m mu i nabla g i x sum j 1 l lambda j nabla h j x 0 nbsp g i x 0 fur i 1 m displaystyle g i x leq 0 text fur i 1 ldots m nbsp h j x 0 fur j 1 l displaystyle h j x 0 text fur j 1 ldots l nbsp m i 0 fur i 1 m displaystyle mu i geq 0 text fur i 1 ldots m nbsp m i g i x 0 fur i 1 m displaystyle mu i g i x 0 text fur i 1 ldots m nbsp z 0 displaystyle z geq 0 nbsp Diese Bedingungen werden die Fritz John Bedingungen oder kurz FJ Bedingungen genannt Ist der Punkt x displaystyle x nbsp lokales und aufgrund der Konvexitat auch globales Minimum des Optimierungsproblems so gibt es m l z displaystyle mu lambda z nbsp so dass z x m l displaystyle z x mu lambda nbsp ein FJ Punkt ist und z m l displaystyle z mu lambda nbsp ungleich dem Nullvektor ist Hinreichende Kriterien Bearbeiten Ist x m l displaystyle x mu lambda nbsp ein KKT Punkt so ist x displaystyle x nbsp ein globales Minimum des konvexen Problems Somit sind die KKT Bedingungen im konvexen Fall schon hinreichend fur die Optimalitat des Punktes Insbesondere werden dazu keine weiteren Regularitatsvoraussetzungen benotigt Da sich zeigen lasst dass man aus jedem FJ Punkt einen KKT Punkt konstruieren kann wenn z gt 0 displaystyle z gt 0 nbsp ist sind auch schon die FJ Bedingungen hinreichend fur die Optimalitat wenn z gt 0 displaystyle z gt 0 nbsp gilt Kriterien fur nicht differenzierbare Funktionen Bearbeiten Hauptartikel Lagrange Dualitat Sind einige der verwendeten Funktionen des konvexen Optimierungsproblems nicht differenzierbar so kann man noch auf die Sattelpunktcharakterisierung von Optimalpunkten zuruckgreifen Mittels der Lagrange Funktion lasst sich dann zeigen dass jeder Sattelpunkt der Lagrange Funktion eine Optimallosung ist Umgekehrt ist x displaystyle x nbsp eine Optimallosung und die Slater Bedingung erfullt so kann man die Optimallosung zu einem Sattelpunkt der Lagrange Funktion erweitern Konkretes Vorgehen BearbeitenLagrange Funktion Bearbeiten Zunachst wird die folgende abkurzende Schreibweise eingefuhrt L x l f x i 1 m m i g i x j 1 l n j h j x displaystyle L x lambda f x sum i 1 m mu i g i x sum j 1 l nu j h j x nbsp wobei l displaystyle lambda nbsp der Vektor aus allen Multiplikatoren ist Lagrangesche Multiplikatorenregel fur das konvexe Problem Bearbeiten Vergleiche hierzu auch mit Lagrangesche Multiplikatorenregel Konkretes Vorgehen Uberprufe ob alle auftretenden Funktionen stetig partiell differenzierbar sind Falls nein ist diese Regel nicht anwendbar Gibt es einen zulassigen Punkt x displaystyle hat x nbsp fur den gilt f x 0 displaystyle nabla f hat x 0 nbsp Falls ja dann ist x displaystyle hat x nbsp optimal Sonst fahre mit dem nachsten Schritt fort Bestimme den Gradienten x L x l displaystyle nabla x L x lambda nbsp der Lagrange Funktion Lose das System x L x l x x 0 x K displaystyle nabla x L x lambda x hat x geq 0 x in K nbsp wobei kein Multiplikator negativ sein darf Falls eine Restriktion nicht aktiv ist muss der zugehorige Multiplikator sogar gleich 0 displaystyle 0 nbsp sein Findet man eine Losung x displaystyle hat x nbsp so ist diese optimal Literatur BearbeitenAvriel Mordecai Nonlinear Programming Analysis and Methods Dover Publishing 2003 ISBN 0 486 43227 0 R Andreani J M Martinez M L Schuverdt On the relation between constant positive linear dependence condition and quasinormality constraint qualification Journal of optimization theory and applications vol 125 no 2 2005 pp 473 485 Florian Jarre Josef Stoer Optimierung Springer Berlin 2003 ISBN 3 540 43575 1 Schmit L A Fleury C 1980 Structural synthesis by combining approximation concepts and dual methods J Amer Inst Aeronaut Astronaut 18 1252 1260Weblinks BearbeitenBuch Convex Optimization von Stephen Boyd und Lieven Vandenberghe PDF engl Abgerufen von https de wikipedia org w index php title Konvexe Optimierung amp oldid 236083412