Konvexe Optimierung - Programmierproblem
Es gibt vier Arten von konvexen Programmierproblemen:
Step 1 - $ min \: f \ left (x \ right) $, wobei $ x \ in S $ und S eine nicht leere konvexe Menge in $ \ mathbb {R} ^ n $ und $ f \ left (x \ right) ist ) $ ist eine konvexe Funktion.
Step 2 - $ min \: f \ left (x \ right), x \ in \ mathbb {R} ^ n $ vorbehaltlich
$ g_i \ left (x \ right) \ geq 0, 1 \ leq m_1 $ und $ g_i \ left (x \ right) $ ist eine konvexe Funktion.
$ g_i \ left (x \ right) \ leq 0, m_1 + 1 \ leq m_2 $ und $ g_i \ left (x \ right) $ ist eine konkave Funktion.
$ g_i \ left (x \ right) = 0, m_2 + 1 \ leq m $ und $ g_i \ left (x \ right) $ ist eine lineare Funktion.
Dabei ist $ f \ left (x \ right) $ eine konvexe Funktion.
Step 3 - $ max \: f \ left (x \ right) $ wobei $ x \ in S $ und S eine nicht leere konvexe Menge in $ \ mathbb {R} ^ n $ und $ f \ left (x \ right) ist. $ ist eine konkave Funktion.
Step 4 - $ min \: f \ left (x \ right) $, wobei $ x \ in \ mathbb {R} ^ n $ vorbehaltlich
$ g_i \ left (x \ right) \ geq 0, 1 \ leq m_1 $ und $ g_i \ left (x \ right) $ ist eine konvexe Funktion.
$ g_i \ left (x \ right) \ leq 0, m_1 + 1 \ leq m_2 $ und $ g_i \ left (x \ right) $ ist eine konkave Funktion.
$ g_i \ left (x \ right) = 0, m_2 + 1 \ leq m $ und $ g_i \ left (x \ right) $ ist eine lineare Funktion.
Dabei ist $ f \ left (x \ right) $ eine konkave Funktion.
Kegel der machbaren Richtung
Sei S eine nicht leere Menge in $ \ mathbb {R} ^ n $ und sei $ \ hat {x} \ in \: Closure \ left (S \ right) $, dann der Kegel der möglichen Richtung von S bei $ \ hat {x} $, bezeichnet mit D, ist definiert als $ D = \ left \ {d: d \ neq 0, \ hat {x} + \ lambda d \ in S, \ lambda \ in \ left (0, \ delta \ right), \ delta> 0 \ right \} $
Jeder Nicht-Null-Vektor $ d \ in D $ wird als mögliche Richtung bezeichnet.
Für eine gegebene Funktion $ f: \ mathbb {R} ^ n \ Rightarrow \ mathbb {R} $ wird der Kegel der Richtungsverbesserung bei $ \ hat {x} $ mit F bezeichnet und ist gegeben durch
$$ F = \ left \ {d: f \ left (\ hat {x} + \ lambda d \ right) \ leq f \ left (\ hat {x} \ right), \ forall \ lambda \ in \ left ( 0, \ delta \ right), \ delta> 0 \ right \} $$
Jede Richtung $ d \ in F $ wird als Verbesserungs- oder Abstiegsrichtung von f bei $ \ hat {x} $ bezeichnet
Satz
Necessary Condition
Betrachten Sie das Problem $ min f \ left (x \ right) $ so, dass $ x \ in S $ eine nicht leere Menge in $ \ mathbb {R} ^ n $ ist. Angenommen, f ist an einem Punkt $ \ hat {x} \ in S $ differenzierbar. Wenn $ \ hat {x} $ eine lokale optimale Lösung ist, dann ist $ F_0 \ cap D = \ phi $ wobei $ F_0 = \ left \ {d: \ bigtriangledown f \ left (\ hat {x} \ right) ^ T. d <0 \ right \} $ und D ist ein Kegel der möglichen Richtung.
Sufficient Condition
Wenn $ F_0 \ cap D = \ phi $ f eine pseudokonvexe Funktion bei $ \ hat {x} $ ist und eine Nachbarschaft von $ \ hat {x} existiert, ist N_ \ varepsilon \ left (\ hat {x} \ right) , \ varepsilon> 0 $, so dass $ d = x- \ hat {x} \ in D $ für jedes $ x \ in S \ cap N_ \ varepsilon \ left (\ hat {x} \ right) $, dann $ \ hat {x} $ ist eine lokale optimale Lösung.
Beweis
Necessary Condition
Sei $ F_0 \ cap D \ neq \ phi $, dh es existiert ein $ d \ in F_0 \ cap D $, so dass $ d \ in F_0 $ und $ d \ in D $
Da $ d \ in D $ ist, existiert also $ \ delta_1> 0 $, so dass $ \ hat {x} + \ lambda d \ in S, \ lambda \ in \ left (0, \ delta_1 \ right). $
Da $ d \ in F_0 $, also $ \ bigtriangledown f \ left (\ hat {x} \ right) ^ T d <0 $
Somit existiert $ \ delta_2> 0 $, so dass $ f \ left (\ hat {x} + \ lambda d \ right) <f \ left (\ hat {x} \ right), \ forall \ lambda \ in f \ left (0, \ delta_2 \ right) $
Sei $ \ delta = min \ left \ {\ delta_1, \ delta_2 \ right \} $
Dann $ \ hat {x} + \ lambda d \ in S, f \ left (\ hat {x} + \ lambda d \ right) <f \ left (\ hat {x} \ right), \ forall \ lambda \ in f \ left (0, \ delta \ right) $
Aber $ \ hat {x} $ ist eine lokal optimale Lösung.
Daher ist es Widerspruch.
Also $ F_0 \ cap D = \ phi $
Sufficient Condition
Sei $ F_0 \ cap D \ neq \ phi $ nd sei f eine pseudokonvexe Funktion.
Es gebe eine Nachbarschaft von $ \ hat {x}, N _ {\ varepsilon} \ left (\ hat {x} \ right) $, so dass $ d = x- \ hat {x}, \ forall x \ in S \ cap N_ \ varepsilon \ left (\ hat {x} \ right) $
Sei $ \ hat {x} $ keine lokal optimale Lösung.
Somit existiert $ \ bar {x} \ in S \ cap N_ \ varepsilon \ left (\ hat {x} \ right) $, so dass $ f \ left (\ bar {x} \ right) <f \ left ( \ hat {x} \ right) $
Unter der Annahme von $ S \ cap N_ \ varepsilon \ left (\ hat {x} \ right) ist d = \ left (\ bar {x} - \ hat {x} \ right) \ in D $
Durch Pseudokonvex von f,
$$ f \ left (\ hat {x} \ right)> f \ left (\ bar {x} \ right) \ Rightarrow \ bigtriangledown f \ left (\ hat {x} \ right) ^ T \ left (\ bar {x} - \ hat {x} \ right) <0 $$
$ \ Rightarrow \ bigtriangledown f \ left (\ hat {x} \ right) ^ T d <0 $
$ \ Rightarrow d \ in F_0 $
daher $ F_0 \ cap D \ neq \ phi $
Das ist ein Widerspruch.
Daher ist $ \ hat {x} $ eine lokal optimale Lösung.
Betrachten Sie das folgende Problem: $ min \: f \ left (x \ right) $ wobei $ x \ in X $ so ist, dass $ g_x \ left (x \ right) \ leq 0, i = 1,2, ..., m $
$ f: X \ rightarrow \ mathbb {R}, g_i: X \ rightarrow \ mathbb {R} ^ n $ und X ist eine offene Menge in $ \ mathbb {R} ^ n $
Sei $ S = \ left \ {x: g_i \ left (x \ right) \ leq 0, \ forall i \ right \} $
Sei $ \ hat {x} \ in X $, dann $ M = \ left \ {1,2, ..., m \ right \} $
Sei $ I = \ left \ {i: g_i \ left (\ hat {x} \ right) = 0, i \ in M \ right \} $, wobei ich als Indexsatz für alle aktiven Einschränkungen bei $ \ hat {x bezeichnet werde } $
Sei $ J = \ left \ {i: g_i \ left (\ hat {x} \ right) <0, i \ in M \ right \} $, wobei J als Indexsatz für alle aktiven Einschränkungen bei $ \ hat {x bezeichnet wird } $.
Sei $ F_0 = \ left \ {d \ in \ mathbb {R} ^ m: \ bigtriangledown f \ left (\ hat {x} \ right) ^ T d <0 \ right \} $
Sei $ G_0 = \ left \ {d \ in \ mathbb {R} ^ m: \ bigtriangledown gI \ left (\ hat {x} \ right) ^ T d <0 \ right \} $
oder $ G_0 = \ left \ {d \ in \ mathbb {R} ^ m: \ bigtriangledown gi \ left (\ hat {x} \ right) ^ T d <0, \ forall i \ in I \ right \} $
Lemma
Wenn $ S = \ left \ {x \ in X: g_i \ left (x \ right) \ leq 0, \ forall i \ in I \ right \} $ und X nicht leer ist, wird in $ \ mathbb {R offen gesetzt } ^ n $. Sei $ \ hat {x} \ in S $ und $ g_i $ bei $ \ hat {x} unterschiedlich, i \ in I $ und sei $ g_i $, wobei $ i \ in J $ bei $ \ hat {x stetig sind } $, dann $ G_0 \ subseteq D $.
Beweis
Sei $ d \ in G_0 $
Da $ \ hat {x} \ in X $ und X eine offene Menge ist, existiert $ \ delta_1> 0 $, so dass $ \ hat {x} + \ lambda d \ in X $ für $ \ lambda \ in \ left (0, \ delta_1 \ right) $
Da $ g_ \ hat {x} <0 $ und $ g_i $ bei $ \ hat {x}, \ forall i \ in J $ stetig sind, existiert $ \ delta_2> 0 $, $ g_i \ left (\ hat {x} + \ lambda d \ right) <0, \ lambda \ in \ left (0, \ delta_2 \ right) $
Da $ d \ in G_0 $ also $ \ bigtriangledown g_i \ left (\ hat {x} \ right) ^ T d <0, \ forall i \ in I $, existiert also $ \ delta_3> 0, g_i \ left (\ hat {x} + \ lambda d \ right) <g_i \ left (\ hat {x} \ right) = 0 $, für $ \ lambda \ in \ left (0, \ delta_3 \ right) i \ in J. $
Sei $ \ delta = min \ left \ {\ delta_1, \ delta_2, \ delta_3 \ right \} $
daher ist $ \ hat {x} + \ lambda d \ in X, g_i \ left (\ hat {x} + \ lambda d \ right) <0, i \ in M $
$ \ Rightarrow \ hat {x} + \ lambda d \ in S $
$ \ Rightarrow d \ in D $
$ \ Rightarrow G_0 \ subseteq D $
Daher bewiesen.
Satz
Necessary Condition
$ F $ und $ g_i, i \ in I $, sind bei $ \ hat {x} \ in S unterschiedlich, $ und $ g_j $ sind bei $ \ hat {x} \ in S $ stetig. Wenn $ \ hat {x} $ ein lokales Minimum von $ S $ ist, dann ist $ F_0 \ cap G_0 = \ phi $.
Sufficient Condition
Wenn $ F_0 \ cap G_0 = \ phi $ und f eine pseudokonvexe Funktion bei $ \ left ist (\ hat {x}, g_i 9x \ right), sind i \ in I $ streng pseudokonvexe Funktionen über eine $ \ varepsilon $ - Nachbarschaft von $ \ hat {x} ist \ hat {x} $ eine lokale optimale Lösung.
Bemerkungen
Sei $ \ hat {x} $ ein machbarer Punkt, so dass $ \ bigtriangledown f \ left (\ hat {x} \ right) = 0 $, dann $ F_0 = \ phi $. Somit ist $ F_0 \ cap G_0 = \ phi $, aber $ \ hat {x} $ ist keine optimale Lösung
Aber wenn $ \ bigtriangledown g \ left (\ hat {x} \ right) = 0 $ ist, dann ist $ G_0 = \ phi $, also $ F_0 \ cap G_0 = \ phi $
Betrachten Sie das Problem: min $ f \ left (x \ right) $, so dass $ g \ left (x \ right) = 0 $.
Da $ g \ left (x \ right) = 0 $ ist, ist $ g_1 \ left (x \ right) = g \ left (x \ right) <0 $ und $ g_2 \ left (x \ right) = - g \ left (x \ right) \ leq 0 $.
Sei $ \ hat {x} \ in S $, dann $ g_1 \ left (\ hat {x} \ right) = 0 $ und $ g_2 \ left (\ hat {x} \ right) = 0 $.
Aber $ \ bigtriangledown g_1 \ left (\ hat {x} \ right) = - \ bigtriangledown g_2 \ left (\ hat {x} \ right) $
Somit ist $ G_0 = \ phi $ und $ F_0 \ cap G_0 = \ phi $.