Optymalizacja wypukła - problem programistyczny
Istnieją cztery typy wypukłych problemów programistycznych -
Step 1 - $ min \: f \ left (x \ right) $, gdzie $ x \ in S $ i S są niepustym zbiorem wypukłym w $ \ mathbb {R} ^ n $ i $ f \ left (x \ right ) $ jest funkcją wypukłą.
Step 2 - $ min \: f \ left (x \ right), x \ in \ mathbb {R} ^ n $ podlega
$ g_i \ left (x \ right) \ geq 0, 1 \ leq m_1 $ i $ g_i \ left (x \ right) $ to funkcja wypukła.
$ g_i \ left (x \ right) \ leq 0, m_1 + 1 \ leq m_2 $ i $ g_i \ left (x \ right) $ jest funkcją wklęsłą.
$ g_i \ left (x \ right) = 0, m_2 + 1 \ leq m $ i $ g_i \ left (x \ right) $ jest funkcją liniową.
gdzie $ f \ left (x \ right) $ jest funkcją wypukłą.
Step 3 - $ max \: f \ left (x \ right) $ gdzie $ x \ in S $ i S są niepustym zbiorem wypukłym w $ \ mathbb {R} ^ n $ i $ f \ left (x \ right) $ jest funkcją wklęsłą.
Step 4 - $ min \: f \ left (x \ right) $, gdzie $ x \ in \ mathbb {R} ^ n $ podlega
$ g_i \ left (x \ right) \ geq 0, 1 \ leq m_1 $ i $ g_i \ left (x \ right) $ to funkcja wypukła.
$ g_i \ left (x \ right) \ leq 0, m_1 + 1 \ leq m_2 $ i $ g_i \ left (x \ right) $ jest funkcją wklęsłą.
$ g_i \ left (x \ right) = 0, m_2 + 1 \ leq m $ i $ g_i \ left (x \ right) $ jest funkcją liniową.
gdzie $ f \ left (x \ right) $ jest funkcją wklęsłą.
Stożek wykonalnego kierunku
Niech S będzie niepustym zbiorem w $ \ mathbb {R} ^ n $ i niech $ \ hat {x} \ in \: Closure \ left (S \ right) $, a następnie stożek możliwego kierunku S w $ \ hat {x} $, oznaczony przez D, jest zdefiniowany jako $ D = \ left \ {d: d \ neq 0, \ hat {x} + \ lambda d \ in S, \ lambda \ in \ left (0, \ delta \ right), \ delta> 0 \ right \} $
Każdy niezerowy wektor $ d \ w D $ nazywany jest wykonalnym kierunkiem.
Dla danej funkcji $ f: \ mathbb {R} ^ n \ Rightarrow \ mathbb {R} $ stożek poprawiającego się kierunku w $ \ hat {x} $ jest oznaczony przez F i jest określony przez
$$ 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 \} $$
Każdy kierunek $ d \ w F $ nazywany jest poprawiającym się kierunkiem lub kierunkiem opadania f w $ \ hat {x} $
Twierdzenie
Necessary Condition
Rozważmy problem $ min f \ left (x \ right) $ w taki sposób, że $ x \ in S $, gdzie S będzie niepustym zbiorem w $ \ mathbb {R} ^ n $. Załóżmy, że f jest różniczkowalne w punkcie $ \ hat {x} \ w S $. Jeśli $ \ hat {x} $ jest lokalnym optymalnym rozwiązaniem, to $ F_0 \ cap D = \ phi $ gdzie $ F_0 = \ left \ {d: \ bigtriangledown f \ left (\ hat {x} \ right) ^ T d <0 \ right \} $ i D to stożek wykonalnego kierunku.
Sufficient Condition
Jeśli $ F_0 \ cap D = \ phi $ f jest funkcją pseudo wypukłą w $ \ hat {x} $ i istnieje sąsiedztwo $ \ hat {x}, N_ \ varepsilon \ left (\ hat {x} \ right) , \ varepsilon> 0 $ takie, że $ d = x- \ hat {x} \ in D $ dla każdego $ x \ in S \ cap N_ \ varepsilon \ left (\ hat {x} \ right) $, a następnie $ \ hat {x} $ to optymalne rozwiązanie lokalne.
Dowód
Necessary Condition
Niech $ F_0 \ cap D \ neq \ phi $, czyli istnieje $ d \ in F_0 \ cap D $ takie, że $ d \ in F_0 $ i $ d \ in D $
Ponieważ $ d \ in D $, więc istnieje $ \ delta_1> 0 $ takie, że $ \ hat {x} + \ lambda d \ in S, \ lambda \ in \ left (0, \ delta_1 \ right). $
Ponieważ $ d \ in F_0 $, więc $ \ bigtriangledown f \ left (\ hat {x} \ right) ^ T d <0 $
Tak więc istnieje $ \ delta_2> 0 $ takie, że $ f \ left (\ hat {x} + \ lambda d \ right) <f \ left (\ hat {x} \ right), \ forall \ lambda \ in f \ left (0, \ delta_2 \ right) $
Niech $ \ delta = min \ left \ {\ delta_1, \ delta_2 \ right \} $
Następnie $ \ hat {x} + \ lambda d \ in S, f \ left (\ hat {x} + \ lambda d \ right) <f \ left (\ hat {x} \ right), \ forall \ lambda \ w f \ left (0, \ delta \ right) $
Ale $ \ hat {x} $ jest lokalnie optymalnym rozwiązaniem.
Stąd jest to sprzeczność.
Zatem $ F_0 \ cap D = \ phi $
Sufficient Condition
Niech $ F_0 \ cap D \ neq \ phi $ nd niech f będzie funkcją pseudo wypukłą.
Niech istnieje sąsiedztwo $ \ hat {x}, N _ {\ varepsilon} \ left (\ hat {x} \ right) $ takie, że $ d = x- \ hat {x}, \ forall x \ in S \ czapka N_ \ varepsilon \ left (\ hat {x} \ right) $
Niech $ \ hat {x} $ nie jest lokalnym optymalnym rozwiązaniem.
Tak więc istnieje $ \ bar {x} \ in S \ cap N_ \ varepsilon \ left (\ hat {x} \ right) $ takie, że $ f \ left (\ bar {x} \ right) <f \ left ( \ hat {x} \ right) $
Zakładając, że $ S \ cap N_ \ varepsilon \ left (\ hat {x} \ right), d = \ left (\ bar {x} - \ hat {x} \ right) \ in D $
Przez pseudo wypukłe 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 $
stąd $ F_0 \ cap D \ neq \ phi $
co jest sprzecznością.
Stąd $ \ hat {x} $ jest lokalnie optymalnym rozwiązaniem.
Rozważmy następujący problem: $ min \: f \ left (x \ right) $ gdzie $ x \ in X $ takie, że $ g_x \ left (x \ right) \ leq 0, i = 1,2, ..., m $
$ f: X \ rightarrow \ mathbb {R}, g_i: X \ rightarrow \ mathbb {R} ^ n $ i X to zbiór otwarty w $ \ mathbb {R} ^ n $
Niech $ S = \ left \ {x: g_i \ left (x \ right) \ leq 0, \ forall i \ right \} $
Niech $ \ hat {x} \ in X $, a następnie $ M = \ left \ {1,2, ..., m \ right \} $
Niech $ I = \ left \ {i: g_i \ left (\ hat {x} \ right) = 0, i \ in M \ right \} $, gdzie nazywam się zbiorem indeksu dla wszystkich aktywnych ograniczeń w $ \ hat {x } $
Niech $ J = \ left \ {i: g_i \ left (\ hat {x} \ right) <0, i \ in M \ right \} $, gdzie J to zbiór indeksów dla wszystkich aktywnych ograniczeń w $ \ hat {x } $.
Niech $ F_0 = \ left \ {d \ in \ mathbb {R} ^ m: \ bigtriangledown f \ left (\ hat {x} \ right) ^ T d <0 \ right \} $
Niech $ G_0 = \ left \ {d \ in \ mathbb {R} ^ m: \ bigtriangledown gI \ left (\ hat {x} \ right) ^ T d <0 \ right \} $
lub $ G_0 = \ left \ {d \ in \ mathbb {R} ^ m: \ bigtriangledown gi \ left (\ hat {x} \ right) ^ T d <0, \ forall i \ in I \ right \} $
Lemat
Jeśli $ S = \ left \ {x \ in X: g_i \ left (x \ right) \ leq 0, \ forall i \ in I \ right \} $ i X jest niepuste otwórz zbiór w $ \ mathbb {R } ^ n $. Niech $ \ hat {x} \ in S $ i $ g_i $ są różne w $ \ hat {x}, i \ in I $ i niech $ g_i $ gdzie $ i \ in J $ są ciągłe przy $ \ hat {x } $, a następnie $ G_0 \ subseteq D $.
Dowód
Niech $ d \ in G_0 $
Ponieważ $ \ hat {x} \ in X $ i X jest zbiorem otwartym, więc istnieje $ \ delta_1> 0 $ takie, że $ \ hat {x} + \ lambda d \ in X $ dla $ \ lambda \ in \ left (0, \ delta_1 \ right) $
Również ponieważ $ g_ \ hat {x} <0 $ i $ g_i $ są ciągłe w $ \ hat {x}, \ forall i \ in J $, istnieje $ \ delta_2> 0 $, $ g_i \ left (\ hat {x} + \ lambda d \ right) <0, \ lambda \ in \ left (0, \ delta_2 \ right) $
Ponieważ $ d \ in G_0 $, więc $ \ bigtriangledown g_i \ left (\ hat {x} \ right) ^ T d <0, \ forall i \ in I $, więc istnieje $ \ delta_3> 0, g_i \ left (\ hat {x} + \ lambda d \ right) <g_i \ left (\ hat {x} \ right) = 0 $, for $ \ lambda \ in \ left (0, \ delta_3 \ right) i \ in J $
Niech $ \ delta = min \ left \ {\ delta_1, \ delta_2, \ delta_3 \ right \} $
zatem $ \ 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 $
Stąd udowodnione.
Twierdzenie
Necessary Condition
Niech $ f $ i $ g_i, i \ in I $, są różne w $ \ hat {x} \ in S, $ i $ g_j $ są ciągłe w $ \ hat {x} \ in S $. Jeśli $ \ hat {x} $ to lokalne minima $ S $, to $ F_0 \ cap G_0 = \ phi $.
Sufficient Condition
Jeśli $ F_0 \ cap G_0 = \ phi $ if jest funkcją pseudowypukłą w $ \ left (\ hat {x}, g_i 9x \ right), i \ in I $ są funkcjami ściśle pseudowypukłymi na jakimś $ \ varepsilon $ - sąsiedztwie $ \ hat {x}, \ hat {x} $ to optymalne rozwiązanie lokalne.
Uwagi
Niech $ \ hat {x} $ będzie możliwym punktem takim, że $ \ bigtriangledown f \ left (\ hat {x} \ right) = 0 $, a następnie $ F_0 = \ phi $. Zatem $ F_0 \ cap G_0 = \ phi $ ale $ \ hat {x} $ nie jest optymalnym rozwiązaniem
Ale jeśli $ \ bigtriangledown g \ left (\ hat {x} \ right) = 0 $, to $ G_0 = \ phi $, więc $ F_0 \ cap G_0 = \ phi $
Rozważmy problem: min $ f \ left (x \ right) $ takie, że $ g \ left (x \ right) = 0 $.
Ponieważ $ g \ left (x \ right) = 0 $, więc $ g_1 \ left (x \ right) = g \ left (x \ right) <0 $ i $ g_2 \ left (x \ right) = - g \ left (x \ right) \ leq 0 $.
Niech $ \ hat {x} \ in S $, a następnie $ g_1 \ left (\ hat {x} \ right) = 0 $ i $ g_2 \ left (\ hat {x} \ right) = 0 $.
Ale $ \ bigtriangledown g_1 \ left (\ hat {x} \ right) = - \ bigtriangledown g_2 \ left (\ hat {x} \ right) $
Zatem $ G_0 = \ phi $ i $ F_0 \ cap G_0 = \ phi $.