Điều kiện đủ & cần thiết cho Global Optima
Định lý
Cho f là hàm phân biệt hai lần. Nếu $ \ bar {x} $ là cực tiểu cục bộ thì $ \ bigtriangledown f \ left (\ bar {x} \ right) = 0 $ và ma trận Hessian $ H \ left (\ bar {x} \ right) $ là một bán kỳ dương.
Bằng chứng
Cho $ d \ in \ mathbb {R} ^ n $. Vì f phân biệt hai lần tại $ \ bar {x} $.
Vì thế,
$ f \ left (\ bar {x} + \ lambda d \ right) = f \ left (\ bar {x} \ right) + \ lambda \ bigtriangledown f \ left (\ bar {x} \ right) ^ T d + \ lambda ^ 2d ^ TH \ left (\ bar {x} \ right) d + \ lambda ^ 2d ^ TH \ left (\ bar {x} \ right) d + $
$ \ lambda ^ 2 \ left \ | d \ right \ | ^ 2 \ beta \ left (\ bar {x}, \ lambda d \ right) $
Nhưng $ \ bigtriangledown f \ left (\ bar {x} \ right) = 0 $ và $ \ beta \ left (\ bar {x}, \ lambda d \ right) \ rightarrow 0 $ as $ \ lambda \ rightarrow 0 $
$ \ Rightarrow f \ left (\ bar {x} + \ lambda d \ right) -f \ left (\ bar {x} \ right) = \ lambda ^ 2d ^ TH \ left (\ bar {x} \ right) d $
Vì $ \ bar {x} $ là cực tiểu cục bộ nên tồn tại $ \ delta> 0 $ sao cho $ f \ left (x \ right) \ leq f \ left (\ bar {x} + \ lambda d \ right ), \ forall \ lambda \ in \ left (0, \ delta \ right) $
Định lý
Giả sử $ f: S \ rightarrow \ mathbb {R} ^ n $ trong đó $ S \ subset \ mathbb {R} ^ n $ có thể phân biệt hai lần so với S. Nếu $ \ bigtriangledown f \ left (x \ right) = 0 $ và $ H \ left (\ bar {x} \ right) $ là bán xác định dương, đối với tất cả $ x \ tính bằng S $, thì $ \ bar {x} $ là giải pháp tối ưu toàn cầu.
Bằng chứng
Vì $ H \ left (\ bar {x} \ right) $ là bán xác định dương, f là hàm lồi trên S. Vì f là hàm phân biệt và lồi tại $ \ bar {x} $
$ \ bigtriangledown f \ left (\ bar {x} \ right) ^ T \ left (x- \ bar {x} \ right) \ leq f \ left (x \ right) -f \ left (\ bar {x} \ right), \ forall x \ in S $
Vì $ \ bigtriangledown f \ left (\ bar {x} \ right) = 0, f \ left (x \ right) \ geq f \ left (\ bar {x} \ right) $
Do đó, $ \ bar {x} $ là một tối ưu hóa toàn cầu.
Định lý
Giả sử $ \ bar {x} \ in S $ là một giải pháp tối ưu cục bộ cho bài toán $ f: S \ rightarrow \ mathbb {R} $ trong đó S là tập con không rỗng của $ \ mathbb {R} ^ n $ và S là tập lồi. $ min \: f \ left (x \ right) $ trong đó $ x \ tính bằng S $.
Sau đó:
$ \ bar {x} $ là một giải pháp tối ưu toàn cầu.
Nếu $ \ bar {x} $ là cực tiểu cục bộ hoàn toàn hoặc f là hàm lồi hoàn toàn, thì $ \ bar {x} $ là giải pháp tối ưu toàn cục duy nhất và cũng là cực tiểu cục bộ mạnh.
Bằng chứng
Hãy để $ \ bar {x} $ là một giải pháp tối ưu toàn cầu khác cho vấn đề sao cho $ x \ neq \ bar {x} $ và $ f \ left (\ bar {x} \ right) = f \ left (\ hat { x} \ right) $
Vì $ \ hat {x}, \ bar {x} \ in S $ và S là lồi nên $ \ frac {\ hat {x} + \ bar {x}} {2} \ in S $ và f là đúng lồi lõm.
$ \ Rightarrow f \ left (\ frac {\ hat {x} + \ bar {x}} {2} \ right) <\ frac {1} {2} f \ left (\ bar {x} \ right) + \ frac {1} {2} f \ left (\ hat {x} \ right) = f \ left (\ hat {x} \ right) $
Đây là sự mâu thuẫn.
Do đó, $ \ hat {x} $ là một giải pháp tối ưu toàn cầu duy nhất.
Hệ quả
Gọi $ f: S \ subset \ mathbb {R} ^ n \ rightarrow \ mathbb {R} $ là một hàm lồi phân biệt trong đó $ \ phi \ neq S \ subset \ mathbb {R} ^ n $ là một tập lồi. Hãy xem xét vấn đề $ min f \ left (x \ right), x \ in S $, thì $ \ bar {x} $ là một giải pháp tối ưu nếu $ \ bigtriangledown f \ left (\ bar {x} \ right) ^ T \ left (x- \ bar {x} \ right) \ geq 0, \ forall x \ in S. $
Bằng chứng
Hãy để $ \ bar {x} $ là một giải pháp tối ưu, tức là $ f \ left (\ bar {x} \ right) \ leq f \ left (x \ right), \ forall x \ in S $
$ \ Rightarrow f \ left (x \ right) = f \ left (\ bar {x} \ right) \ geq 0 $
$ f \ left (x \ right) = f \ left (\ bar {x} \ right) + \ bigtriangledown f \ left (\ bar {x} \ right) ^ T \ left (x- \ bar {x} \ phải) + \ left \ | x- \ bar {x} \ right \ | \ alpha \ left (\ bar {x}, x- \ bar {x} \ right) $
trong đó $ \ alpha \ left (\ bar {x}, x- \ bar {x} \ right) \ rightarrow 0 $ là $ x \ rightarrow \ bar {x} $
$ \ Rightarrow f \ left (x \ right) -f \ left (\ bar {x} \ right) = \ bigtriangledown f \ left (\ bar {x} \ right) ^ T \ left (x- \ bar {x } \ right) \ geq 0 $
Hệ quả
Đặt f là một hàm lồi có thể phân biệt tại $ \ bar {x} $, sau đó $ \ bar {x} $ là giá trị nhỏ nhất toàn cục $ \ bigtriangledown f \ left (\ bar {x} \ right) = 0 $
Ví dụ
$ f \ left (x \ right) = \ left (x ^ 2-1 \ right) ^ {3}, x \ in \ mathbb {R} $.
$ \ bigtriangledown f \ left (x \ right) = 0 \ Rightarrow x = -1,0,1 $.
$ \ bigtriangledown ^ 2f \ left (\ pm 1 \ right) = 0, \ bigtriangledown ^ 2 f \ left (0 \ right) = 6> 0 $.
$ f \ left (\ pm 1 \ right) = 0, f \ left (0 \ right) = - 1 $
Do đó, $ f \ left (x \ right) \ geq -1 = f \ left (0 \ right) \ Rightarrow f \ left (0 \ right) \ leq f \ left (x \ right) \ forall x \ in \ toánbb {R} $
$ f \ left (x \ right) = x \ log x $ được xác định trên $ S = \ left \ {x \ in \ mathbb {R}, x> 0 \ right \} $.
$ {f} 'x = 1 + \ log x $
$ {f} '' x = \ frac {1} {x}> 0 $
Do đó, hàm này là hàm lồi.
$ f \ left (x \ right) = e ^ {x}, x \ in \ mathbb {R} $ hoàn toàn lồi.