Konveks Optimizasyon - Programlama Problemi
Dört tür dışbükey programlama problemi vardır -
Step 1 - $ min \: f \ left (x \ right) $, burada S $ ve S içindeki $ x \, $ \ mathbb {R} ^ n $ ve $ f \ left (x \ right ) $ dışbükey işlevdir.
Step 2 - $ min \: f \ left (x \ sağ), x \ in \ mathbb {R} ^ n $ konu
$ g_i \ left (x \ right) \ geq 0, 1 \ leq m_1 $ ve $ g_i \ left (x \ right) $ bir dışbükey fonksiyondur.
$ g_i \ left (x \ right) \ leq 0, m_1 + 1 \ leq m_2 $ ve $ g_i \ left (x \ right) $ içbükey bir fonksiyondur.
$ g_i \ left (x \ right) = 0, m_2 + 1 \ leq m $ ve $ g_i \ left (x \ right) $ doğrusal bir fonksiyondur.
burada $ f \ left (x \ right) $ dışbükey bir işlevdir.
Step 3 - $ max \: f \ left (x \ right) $ burada $ x \ $ \ mathbb {R} ^ n $ ve $ f \ left (x \ right) içinde boş olmayan bir dışbükey kümedir $, içbükey işlevdir.
Step 4 - $ min \: f \ left (x \ right) $, burada $ x \ in \ mathbb {R} ^ n $ konu
$ g_i \ left (x \ right) \ geq 0, 1 \ leq m_1 $ ve $ g_i \ left (x \ right) $ bir dışbükey fonksiyondur.
$ g_i \ left (x \ right) \ leq 0, m_1 + 1 \ leq m_2 $ ve $ g_i \ left (x \ right) $ içbükey bir fonksiyondur.
$ g_i \ left (x \ right) = 0, m_2 + 1 \ leq m $ ve $ g_i \ left (x \ right) $ doğrusal bir fonksiyondur.
$ f \ left (x \ right) $ içbükey bir fonksiyondur.
Uygulanabilir yön konisi
S $ \ mathbb {R} ^ n $ içinde boş olmayan bir küme olsun ve $ \ hat {x} \ in \: Closure \ left (S \ right) $, sonra da $ 'da S'nin uygun yönünün konisi olsun D ile gösterilen \ hat {x} $, $ D = \ left \ {d: d \ neq 0, \ hat {x} + \ lambda d \ in S, \ lambda \ in \ left (0, \ delta \ sağ), \ delta> 0 \ sağ \} $
D $ 'da sıfır olmayan her bir $ d \ vektörüne uygun yön denir.
Verilen bir $ f: \ mathbb {R} ^ n \ Rightarrow \ mathbb {R} $ fonksiyonu için $ \ hat {x} $ 'da yön geliştirme konisi F ile gösterilir ve şu şekilde verilir:
$$ F = \ left \ {d: f \ left (\ hat {x} + \ lambda d \ right) \ leq f \ left (\ hat {x} \ sağ), \ forall \ lambda \ in \ left ( 0, \ delta \ sağ), \ delta> 0 \ sağ \} $$
F $ 'da her $ d \ yön, f'nin $ \ hat {x} $ konumunda iyileştirme yönü veya alçalma yönü olarak adlandırılır.
Teoremi
Necessary Condition
$ Min f \ left (x \ right) $ problemini, öyle ki S $ 'da $ x \, burada S $ \ mathbb {R} ^ n $' da boş olmayan bir küme olsun. F'nin S $ 'da $ \ hat {x} \ noktasında türevlenebilir olduğunu varsayalım. $ \ Hat {x} $ yerel bir optimal çözümse, $ F_0 \ cap D = \ phi $ burada $ F_0 = \ left \ {d: \ bigtriangledown f \ left (\ hat {x} \ right) ^ T d <0 \ sağ \} $ ve D, uygun yönde bir konidir.
Sufficient Condition
$ F_0 \ cap D = \ phi $ f, $ \ hat {x} $ konumunda bir sözde konveks işleviyse ve $ \ hat {x}, N_ \ varepsilon \ left (\ hat {x} \ right) mahallesi varsa , \ varepsilon> 0 $ öyle ki $ d = x- \ hat {x} \ S \ cap N_ \ varepsilon \ left (\ hat {x} \ right) $ için $ d = x- \ hat {x} \, sonra $ \ şapka {x} $ yerel olarak en uygun çözümdür.
Kanıt
Necessary Condition
$ F_0 \ cap D \ neq \ phi $ olsun, yani, F_0 \ cap D $ içinde bir $ d \ vardır öyle ki F_0 $ içinde $ d \ ve D $ içinde $ d \
D $ 'da $ d \ olduğundan, $ \ delta_1> 0 $ vardır öyle ki $ \ hat {x} + \ lambda d \ in S, \ lambda \ in \ left (0, \ delta_1 \ right) $.
F_0 $ içinde $ d \ olduğundan, bu nedenle $ \ bigtriangledown f \ left (\ hat {x} \ right) ^ T d <0 $
Böylece, f'de $ f \ left (\ hat {x} + \ lambda d \ right) <f \ left (\ hat {x} \ right), \ forall \ lambda \ olacak şekilde $ \ delta_2> 0 $ vardır \ left (0, \ delta_2 \ sağ) $
$ \ Delta = min \ left \ {\ delta_1, \ delta_2 \ right \} $ olsun
Sonra $ \ hat {x} + \ lambda d \ in S, f \ left (\ hat {x} + \ lambda d \ right) <f \ left (\ hat {x} \ right), \ forall \ lambda \ f \ left (0, \ delta \ right) $
Ancak $ \ hat {x} $ yerel olarak en uygun çözümdür.
Dolayısıyla çelişkidir.
Böylece $ F_0 \ cap D = \ phi $
Sufficient Condition
$ F_0 \ cap D \ neq \ phi $ nd, f bir sözde konveks işlevi olsun.
S \ içinde $ d = x- \ hat {x}, \ forall x \ olacak şekilde $ \ hat {x}, N _ {\ varepsilon} \ left (\ hat {x} \ right) $ mahallesi olsun cap N_ \ varepsilon \ left (\ hat {x} \ right) $
$ \ Hat {x} $ yerel bir optimal çözüm olmasın.
Böylece, S \ cap N_ \ varepsilon \ left (\ hat {x} \ right) $ içinde $ \ bar {x} \ vardır öyle ki $ f \ left (\ bar {x} \ right) <f \ left ( \ hat {x} \ sağ) $
D $ içinde $ S \ cap N_ \ varepsilon \ left (\ hat {x} \ right), d = \ left (\ bar {x} - \ hat {x} \ right) \ varsayımına göre
F'nin sözde konveksine göre,
$$ f \ left (\ hat {x} \ right)> f \ left (\ bar {x} \ right) \ Rightarrow \ bigtriangledown f \ left (\ hat {x} \ right) ^ T \ left (\ bar {x} - \ hat {x} \ sağ) <0 $$
$ \ Rightarrow \ bigtriangledown f \ left (\ hat {x} \ right) ^ T d <0 $
F_0 $ içinde $ \ Rightarrow d \
dolayısıyla $ F_0 \ cap D \ neq \ phi $
bu bir çelişkidir.
Dolayısıyla, $ \ hat {x} $ yerel olarak en uygun çözümdür.
Şu problemi düşünün: $ min \: f \ left (x \ right) $ burada $ x \ X $ içinde, $ g_x \ left (x \ right) \ leq 0, i = 1,2, ..., m $
$ f: X \ rightarrow \ mathbb {R}, g_i: X \ rightarrow \ mathbb {R} ^ n $ ve X, $ \ mathbb {R} ^ n $ içinde açık bir kümedir
$ S = \ left \ {x: g_i \ left (x \ right) \ leq 0, \ forall i \ right \} $ olsun
X $ içinde $ \ hat {x} \, sonra $ M = \ left \ {1,2, ..., m \ right \} $ olsun
$ I = \ left \ {i: g_i \ left (\ hat {x} \ right) = 0, i \ in M \ right \} $ burada I $ \ hat {x'teki tüm etkin kısıtlamalar için dizin kümesi olarak adlandırılır } $
$ J = \ left \ {i: g_i \ left (\ hat {x} \ right) <0, i \ in M \ right \} $ burada J $ \ hat {x'teki tüm etkin kısıtlamalar için dizin kümesi olarak adlandırılır } $.
$ F_0 = \ left \ {d \ in \ mathbb {R} ^ m: \ bigtriangledown f \ left (\ hat {x} \ right) ^ T d <0 \ right \} $
$ G_0 = \ left \ {d \ in \ mathbb {R} ^ m: \ bigtriangledown gI \ left (\ hat {x} \ right) ^ T d <0 \ right \} $
veya $ G_0 = \ left \ {d \ in \ mathbb {R} ^ m: \ bigtriangledown gi \ left (\ hat {x} \ right) ^ T d <0, \ forall i \ in I \ right \} $
Lemma
$ S = \ left \ {x \ in X: g_i \ left (x \ right) \ leq 0, \ forall i \ in I \ right \} $ ve X $ \ mathbb {R içinde boş olmayan açık küme ise } ^ n $. $ \ Hat {x} \ in S $ ve $ g_i $, $ \ hat {x}, i \ in I $ konumunda ve $ g_i $ burada $ i \ in J $ $ \ hat {x konumunda sürekli olsun } $, ardından $ G_0 \ subseteq D $.
Kanıt
G_0 $ içinde $ d \ olsun
X $ ve X içindeki $ \ hat {x} \ bir açık küme olduğundan, $ \ delta_1> 0 $ öyle ki $ \ lambda \ in \ için $ \ hat {x} + \ lambda d \ in X $ sol (0, \ delta_1 \ sağ) $
Ayrıca $ g_ \ hat {x} <0 $ ve $ g_i $, $ \ hat {x} konumunda sürekli olduğundan, \ forall i \ J $ içinde, $ \ delta_2> 0 $, $ g_i \ left (\ hat {x} + \ lambda d \ right) <0, \ lambda \ in \ left (0, \ delta_2 \ right) $
G_0 $ içinde $ d \ olduğundan, bu nedenle, $ \ bigtriangledown g_i \ left (\ hat {x} \ right) ^ T d <0, \ forall i \ I $ içinde böylece $ \ delta_3> 0, g_i \ left var (\ hat {x} + \ lambda d \ right) <g_i \ left (\ hat {x} \ right) = 0 $, $ \ lambda \ in \ left (0, \ delta_3 \ right) için J içinde i \ $
$ \ Delta = min \ left \ {\ delta_1, \ delta_2, \ delta_3 \ right \} $ olsun
bu nedenle, $ \ hat {x} + \ lambda d \ in X, g_i \ left (\ hat {x} + \ lambda d \ right) <0, i \ M $ içinde
S $ içinde $ \ Rightarrow \ hat {x} + \ lambda d \
D $ içinde $ \ Rightarrow d \
$ \ Rightarrow G_0 \ subseteq D $
Dolayısıyla Kanıtlandı.
Teoremi
Necessary Condition
$ F $ ve $ g_i, i \ I $ içinde, $ \ hat {x} \ S'de farklı olsun, $ ve $ g_j $ S $ içinde $ \ hat {x} \ konumunda sürekli olsun. $ \ Hat {x} $, $ S $ 'ın yerel minimum değeri ise, $ F_0 \ cap G_0 = \ phi $ olur.
Sufficient Condition
$ F_0 \ cap G_0 = \ phi $ ve f, $ \ left (\ hat {x}, g_i 9x \ right) konumunda bir sözde konveks işleviyse, I $ içindeki i \, bazı $ \ varepsilon $ - mahallesi üzerinde kesinlikle sözde konveks işlevleridir $ \ hat {x}, \ hat {x} $ yerel bir en uygun çözümdür.
Uyarılar
$ \ Hat {x} $, $ \ bigtriangledown f \ left (\ hat {x} \ right) = 0 $, ardından $ F_0 = \ phi $ olacak şekilde uygulanabilir bir nokta olsun. Bu nedenle, $ F_0 \ cap G_0 = \ phi $ ancak $ \ hat {x} $ en uygun çözüm değildir
Ancak $ \ bigtriangledown g \ left (\ hat {x} \ right) = 0 $ ise, $ G_0 = \ phi $, dolayısıyla $ F_0 \ cap G_0 = \ phi $
Sorunu bir düşünün: min $ f \ left (x \ right) $ öyle ki $ g \ left (x \ right) = 0 $.
$ G \ left (x \ right) = 0 $ olduğundan, $ g_1 \ left (x \ right) = g \ left (x \ right) <0 $ ve $ g_2 \ left (x \ right) = - g \ sol (x \ sağ) \ leq 0 $.
S $ içinde $ \ hat {x} \, ardından $ g_1 \ left (\ hat {x} \ right) = 0 $ ve $ g_2 \ left (\ hat {x} \ right) = 0 $ olsun.
Ancak $ \ bigtriangledown g_1 \ left (\ hat {x} \ right) = - \ bigtriangledown g_2 \ left (\ hat {x} \ right) $
Böylece, $ G_0 = \ phi $ ve $ F_0 \ cap G_0 = \ phi $.