Tối ưu hóa lồi - Vấn đề lập trình
Có bốn dạng bài toán lập trình lồi -
Step 1 - $ min \: f \ left (x \ right) $, trong đó $ x \ in S $ và S là một tập lồi không rỗng trong $ \ mathbb {R} ^ n $ và $ f \ left (x \ right ) $ là hàm lồi.
Step 2 - $ min \: f \ left (x \ right), x \ in \ mathbb {R} ^ n $ theo chủ đề
$ g_i \ left (x \ right) \ geq 0, 1 \ leq m_1 $ và $ g_i \ left (x \ right) $ là một hàm lồi.
$ g_i \ left (x \ right) \ leq 0, m_1 + 1 \ leq m_2 $ và $ g_i \ left (x \ right) $ là một hàm lõm.
$ g_i \ left (x \ right) = 0, m_2 + 1 \ leq m $ và $ g_i \ left (x \ right) $ là một hàm tuyến tính.
trong đó $ f \ left (x \ right) $ là một fucntion lồi.
Step 3 - $ max \: f \ left (x \ right) $ trong đó $ x \ in S $ và S là một tập lồi không rỗng trong $ \ mathbb {R} ^ n $ và $ f \ left (x \ right) $ là hàm lõm.
Step 4 - $ min \: f \ left (x \ right) $, trong đó $ x \ in \ mathbb {R} ^ n $ chủ đề
$ g_i \ left (x \ right) \ geq 0, 1 \ leq m_1 $ và $ g_i \ left (x \ right) $ là một hàm lồi.
$ g_i \ left (x \ right) \ leq 0, m_1 + 1 \ leq m_2 $ và $ g_i \ left (x \ right) $ là một hàm lõm.
$ g_i \ left (x \ right) = 0, m_2 + 1 \ leq m $ và $ g_i \ left (x \ right) $ là một hàm tuyến tính.
trong đó $ f \ left (x \ right) $ là một hàm lõm.
Hình nón của hướng khả thi
Gọi S là một tập khác rỗng trong $ \ mathbb {R} ^ n $ và đặt $ \ hat {x} \ in \: Closure \ left (S \ right) $, khi đó hình nón có hướng khả thi của S là $ \ hat {x} $, ký hiệu là D, được định nghĩa là $ D = \ left \ {d: d \ neq 0, \ hat {x} + \ lambda d \ in S, \ lambda \ in \ left (0, \ delta \ right), \ delta> 0 \ right \} $
Mỗi vectơ khác 0 $ d \ trong D $ được gọi là hướng khả thi.
Đối với một hàm đã cho $ f: \ mathbb {R} ^ n \ Rightarrow \ mathbb {R} $, hình nón có hướng cải thiện tại $ \ hat {x} $ được ký hiệu là F và được cho bởi
$$ 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 \} $$
Mỗi hướng $ d \ trong F $ được gọi là hướng đi lên hoặc hướng đi xuống của f tại $ \ hat {x} $
Định lý
Necessary Condition
Xét bài toán $ min f \ left (x \ right) $ sao cho $ x \ in S $ trong đó S là một tập khác rỗng trong $ \ mathbb {R} ^ n $. Giả sử f có thể phân biệt được tại một điểm $ \ hat {x} \ trong S $. Nếu $ \ hat {x} $ là một giải pháp tối ưu cục bộ thì $ F_0 \ cap D = \ phi $ trong đó $ F_0 = \ left \ {d: \ bigtriangledown f \ left (\ hat {x} \ right) ^ T d <0 \ right \} $ và D là một hình nón có hướng khả thi.
Sufficient Condition
Nếu $ F_0 \ cap D = \ phi $ f là một hàm giả lồi tại $ \ hat {x} $ và tồn tại một vùng lân cận của $ \ hat {x}, N_ \ varepsilon \ left (\ hat {x} \ right) , \ varepsilon> 0 $ sao cho $ d = x- \ hat {x} \ in D $ cho $ x \ in S \ cap N_ \ varepsilon \ left (\ hat {x} \ right) $ bất kỳ, sau đó $ \ hat {x} $ là giải pháp tối ưu cục bộ.
Bằng chứng
Necessary Condition
Cho $ F_0 \ cap D \ neq \ phi $, tức là tồn tại một $ d \ in F_0 \ cap D $ sao cho $ d \ in F_0 $ và $ d \ in D $
Vì $ d \ in D $, nên tồn tại $ \ delta_1> 0 $ sao cho $ \ hat {x} + \ lambda d \ in S, \ lambda \ in \ left (0, \ delta_1 \ right). $
Do $ d \ in F_0 $, do đó $ \ bigtriangledown f \ left (\ hat {x} \ right) ^ T d <0 $
Do đó, tồn tại $ \ delta_2> 0 $ sao cho $ f \ left (\ hat {x} + \ lambda d \ right) <f \ left (\ hat {x} \ right), \ forall \ lambda \ in f \ left (0, \ delta_2 \ right) $
Hãy để $ \ delta = min \ left \ {\ delta_1, \ delta_2 \ right \} $
Sau đó $ \ 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) $
Nhưng $ \ hat {x} $ là giải pháp tối ưu cục bộ.
Do đó nó là mâu thuẫn.
Do đó $ F_0 \ cap D = \ phi $
Sufficient Condition
Đặt $ F_0 \ cap D \ neq \ phi $ nd cho f là một hàm giả lồi.
Giả sử tồn tại một vùng lân cận của $ \ hat {x}, N _ {\ varepsilon} \ left (\ hat {x} \ right) $ sao cho $ d = x- \ hat {x}, \ forall x \ in S \ mũ N_ \ varepsilon \ left (\ hat {x} \ phải) $
Cho rằng $ \ hat {x} $ không phải là giải pháp tối ưu cục bộ.
Do đó, tồn tại $ \ bar {x} \ trong S \ cap N_ \ varepsilon \ left (\ hat {x} \ right) $ sao cho $ f \ left (\ bar {x} \ right) <f \ left ( \ hat {x} \ right) $
Theo giả định trên $ S \ cap N_ \ varepsilon \ left (\ hat {x} \ right), d = \ left (\ bar {x} - \ hat {x} \ right) \ trong D $
Bằng giả lồi của 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 $
do đó $ F_0 \ cap D \ neq \ phi $
đó là một mâu thuẫn.
Do đó, $ \ hat {x} $ là giải pháp tối ưu cục bộ.
Hãy xem xét vấn đề sau: $ min \: f \ left (x \ right) $ trong đó $ x \ in X $ sao cho $ g_x \ left (x \ right) \ leq 0, i = 1,2, ..., m $
$ f: X \ rightarrow \ mathbb {R}, g_i: X \ rightarrow \ mathbb {R} ^ n $ và X là một tập hợp mở trong $ \ mathbb {R} ^ n $
Cho $ S = \ left \ {x: g_i \ left (x \ right) \ leq 0, \ forall i \ right \} $
Đặt $ \ hat {x} \ trong X $, sau đó $ M = \ left \ {1,2, ..., m \ right \} $
Đặt $ I = \ left \ {i: g_i \ left (\ hat {x} \ right) = 0, i \ in M \ right \} $ nơi tôi được gọi là bộ chỉ mục cho tất cả các ràng buộc hoạt động tại $ \ hat {x } $
Đặt $ J = \ left \ {i: g_i \ left (\ hat {x} \ right) <0, i \ in M \ right \} $ trong đó J được gọi là bộ chỉ mục cho tất cả các ràng buộc hoạt động tại $ \ hat {x } $.
Cho $ F_0 = \ left \ {d \ in \ mathbb {R} ^ m: \ bigtriangledown f \ left (\ hat {x} \ right) ^ T d <0 \ right \} $
Cho $ G_0 = \ left \ {d \ in \ mathbb {R} ^ m: \ bigtriangledown gI \ left (\ hat {x} \ right) ^ T d <0 \ right \} $
hoặc $ G_0 = \ left \ {d \ in \ mathbb {R} ^ m: \ bigtriangledown gi \ left (\ hat {x} \ right) ^ T d <0, \ forall i \ in I \ right \} $
Bổ đề
Nếu $ S = \ left \ {x \ in X: g_i \ left (x \ right) \ leq 0, \ forall i \ in I \ right \} $ và X là tập mở không trống trong $ \ mathbb {R } ^ n $. Đặt $ \ hat {x} \ in S $ và $ g_i $ khác nhau ở $ \ hat {x}, i \ in I $ và để $ g_i $ trong đó $ i \ in J $ liên tục ở $ \ hat {x } $, rồi đến $ G_0 \ subseteq D $.
Bằng chứng
Cho $ d \ trong G_0 $
Vì $ \ hat {x} \ in X $ và X là một tập hợp mở, do đó, tồn tại $ \ delta_1> 0 $ sao cho $ \ hat {x} + \ lambda d \ in X $ cho $ \ lambda \ in \ trái (0, \ delta_1 \ phải) $
Ngoài ra, vì $ g_ \ hat {x} <0 $ và $ g_i $ liên tục ở $ \ hat {x}, \ forall i \ in J $, nên tồn tại $ \ delta_2> 0 $, $ g_i \ left (\ hat {x} + \ lambda d \ right) <0, \ lambda \ in \ left (0, \ delta_2 \ right) $
Vì $ d \ in G_0 $ nên $ \ bigtriangledown g_i \ left (\ hat {x} \ right) ^ T d <0, \ forall i \ in I $ nên tồn tại $ \ delta_3> 0, g_i \ left (\ hat {x} + \ lambda d \ right) <g_i \ left (\ hat {x} \ right) = 0 $, cho $ \ lambda \ in \ left (0, \ delta_3 \ right) i \ in J $
Để $ \ delta = min \ left \ {\ delta_1, \ delta_2, \ delta_3 \ right \} $
do đó, $ \ 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 $
Do đó đã được chứng minh.
Định lý
Necessary Condition
Giả sử $ f $ và $ g_i, i \ in I $, khác với $ \ hat {x} \ in S, $ và $ g_j $ liên tục với $ \ hat {x} \ trong S $. Nếu $ \ hat {x} $ là cực tiểu cục bộ của $ S $ thì $ F_0 \ cap G_0 = \ phi $.
Sufficient Condition
Nếu $ F_0 \ cap G_0 = \ phi $ và f là hàm giả lồi ở $ \ left (\ hat {x}, g_i 9x \ right), thì i \ in I $ là hàm giả lồi trên một số $ \ varepsilon $ - vùng lân cận của $ \ hat {x}, \ hat {x} $ là giải pháp tối ưu cục bộ.
Nhận xét
Đặt $ \ hat {x} $ là một điểm khả thi sao cho $ \ bigtriangledown f \ left (\ hat {x} \ right) = 0 $, thì $ F_0 = \ phi $. Do đó, $ F_0 \ cap G_0 = \ phi $ nhưng $ \ hat {x} $ không phải là giải pháp tối ưu
Nhưng nếu $ \ bigtriangledown g \ left (\ hat {x} \ right) = 0 $ thì $ G_0 = \ phi $, do đó $ F_0 \ cap G_0 = \ phi $
Xem xét vấn đề: min $ f \ left (x \ right) $ sao cho $ g \ left (x \ right) = 0 $.
Vì $ g \ left (x \ right) = 0 $ nên $ g_1 \ left (x \ right) = g \ left (x \ right) <0 $ và $ g_2 \ left (x \ right) = - g \ left (x \ right) \ leq 0 $.
Đặt $ \ hat {x} \ bằng S $, sau đó $ g_1 \ left (\ hat {x} \ right) = 0 $ và $ g_2 \ left (\ hat {x} \ right) = 0 $.
Nhưng $ \ bigtriangledown g_1 \ left (\ hat {x} \ right) = - \ bigtriangledown g_2 \ left (\ hat {x} \ right) $
Do đó, $ G_0 = \ phi $ và $ F_0 \ cap G_0 = \ phi $.