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 $.