Tối ưu hóa lồi - Chức năng khác biệt

Đặt S là một tập mở không trống trong $ \ mathbb {R} ^ n $, thì $ f: S \ rightarrow \ mathbb {R} $ được cho là có thể phân biệt được với $ \ hat {x} \ trong S $ nếu tồn tại một vectơ $ \ bigtriangledown f \ left (\ hat {x} \ right) $ được gọi là vectơ gradient và một hàm $ \ alpha: \ mathbb {R} ^ n \ rightarrow \ mathbb {R} $ sao cho

$ f \ left (x \ right) = f \ left (\ hat {x} \ right) + \ bigtriangledown f \ left (\ hat {x} \ right) ^ T \ left (x- \ hat {x} \ phải) + \ left \ | x = \ hat {x} \ right \ | \ alpha \ left (\ hat {x}, x- \ hat {x} \ right), \ forall x \ in S $ ở đâu

$ \ alpha \ left (\ hat {x}, x- \ hat {x} \ right) \ rightarrow 0 \ bigtriangledown f \ left (\ hat {x} \ right) = \ left [\ frac {\ part f} {\ một phần x_1} \ frac {\ một phần f} {\ một phần x_2} ... \ frac {\ một phần f} {\ một phần x_n} \ right] _ {x = \ hat {x}} ^ {T} $

Định lý

đặt S là một tập lồi mở, không rỗng trong $ \ mathbb {R} ^ n $ và để $ f: S \ rightarrow \ mathbb {R} $ có thể phân biệt được trên S. Khi đó, f là lồi nếu và chỉ khi với $ x_1, x_2 \ in S, \ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_1-x_2 \ right) \ leq f \ left (x_1 \ right) -f \ left (x_2 \ right) $

Bằng chứng

Cho f là một hàm lồi. tức là với $ x_1, x_2 \ in S, \ lambda \ in \ left (0, 1 \ right) $

$ f \ left [\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right] \ leq \ lambda f \ left (x_1 \ right) + \ left (1- \ lambda \ right) f \ left (x_2 \ right) $

$ \ Rightarrow f \ left [\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right] \ leq \ lambda \ left (f \ left (x_1 \ right) -f \ left (x_2 \ right) \ right ) + f \ left (x_2 \ right) $

$ \ Rightarrow \ lambda \ left (f \ left (x_1 \ right) -f \ left (x_2 \ right) \ right) \ geq f \ left (x_2 + \ lambda \ left (x_1-x_2 \ right) \ right) - f \ left (x_2 \ right) $

$ \ Rightarrow \ lambda \ left (f \ left (x_1 \ right) -f \ left (x_2 \ right) \ right) \ geq f \ left (x_2 \ right) + \ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_1-x_2 \ right) \ lambda + $

$ \ left \ | \ lambda \ left (x_1-x_2 \ right) \ right \ | \ alpha \ left (x_2, \ lambda \ left (x_1 - x_2 \ right) -f \ left (x_2 \ right) \ right) $

trong đó $ \ alpha \ left (x_2, \ lambda \ left (x_1 - x_2 \ right) \ right) \ rightarrow 0 $ dưới dạng $ \ lambda \ rightarrow 0 $

Chia cho $ \ lambda $ ở cả hai phía, ta được -

$ f \ left (x_1 \ right) -f \ left (x_2 \ right) \ geq \ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_1-x_2 \ right) $

ngược

Cho $ x_1, x_2 \ in S, \ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_1-x_2 \ right) \ leq f \ left (x_1 \ right) -f \ left (x_2 \ right) $

Để chứng tỏ rằng f là lồi.

Vì S là lồi nên $ x_3 = \ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ in S, \ lambda \ in \ left (0, 1 \ right) $

Vì $ x_1, x_3 \ tính bằng S $, do đó

$ f \ left (x_1 \ right) -f \ left (x_3 \ right) \ geq \ bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_1 -x_3 \ right) $

$ \ Rightarrow f \ left (x_1 \ right) -f \ left (x_3 \ right) \ geq \ bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_1 - \ lambda x_1- \ left (1- \ lambda \ right) x_2 \ right) $

$ \ Rightarrow f \ left (x_1 \ right) -f \ left (x_3 \ right) \ geq \ left (1- \ lambda \ right) \ bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_1 - x_2 \ right) $

Do đó, $ x_2, x_3 \ in S $

$ f \ left (x_2 \ right) -f \ left (x_3 \ right) \ geq \ bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_2-x_3 \ right) $

$ \ Rightarrow f \ left (x_2 \ right) -f \ left (x_3 \ right) \ geq \ bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_2- \ lambda x_1- \ left (1- \ lambda \ right) x_2 \ right) $

$ \ Rightarrow f \ left (x_2 \ right) -f \ left (x_3 \ right) \ geq \ left (- \ lambda \ right) \ bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_1-x_2 \ đúng) $

Do đó, kết hợp các phương trình trên, chúng ta nhận được -

$ \ lambda \ left (f \ left (x_1 \ right) -f \ left (x_3 \ right) \ right) + \ left (1- \ lambda \ right) \ left (f \ left (x_2 \ right) -f \ left (x_3 \ right) \ right) \ geq 0 $

$ \ Rightarrow f \ left (x_3 \ right) \ leq \ lambda f \ left (x_1 \ right) + \ left (1- \ lambda \ right) f \ left (x_2 \ right) $

Định lý

cho S là một tập lồi mở khác rỗng trong $ \ mathbb {R} ^ n $ và để cho $ f: S \ rightarrow \ mathbb {R} $ có thể phân biệt được trên S, khi đó f lồi trên S nếu và chỉ khi cho bất kỳ $ x_1, x_2 \ in S, \ left (\ bigtriangledown f \ left (x_2 \ right) - \ bigtriangledown f \ left (x_1 \ right) \ right) ^ T \ left (x_2-x_1 \ right) \ geq 0 $

Bằng chứng

cho f là một hàm lồi, sau đó sử dụng định lý trước -

$ \ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_1-x_2 \ right) \ leq f \ left (x_1 \ right) -f \ left (x_2 \ right) $ và

$ \ bigtriangledown f \ left (x_1 \ right) ^ T \ left (x_2-x_1 \ right) \ leq f \ left (x_2 \ right) -f \ left (x_1 \ right) $

Cộng hai phương trình trên, ta được -

$ \ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_1-x_2 \ right) + \ bigtriangledown f \ left (x_1 \ right) ^ T \ left (x_2-x_1 \ right) \ leq 0 $

$ \ Rightarrow \ left (\ bigtriangledown f \ left (x_2 \ right) - \ bigtriangledown f \ left (x_1 \ right) \ right) ^ T \ left (x_1-x_2 \ right) \ leq 0 $

$ \ Rightarrow \ left (\ bigtriangledown f \ left (x_2 \ right) - \ bigtriangledown f \ left (x_1 \ right) \ right) ^ T \ left (x_2-x_1 \ right) \ geq 0 $

ngược

Cho bất kỳ $ x_1, x_2 \ in S, \ left (\ bigtriangledown f \ left (x_2 \ right) - \ bigtriangledown f \ left (x_1 \ right) \ right) ^ T \ left (x_2-x_1 \ right) \ geq 0 $

Để chứng tỏ rằng f là lồi.

Giả sử $ x_1, x_2 \ trong S $, do đó theo định lý giá trị trung bình, $ \ frac {f \ left (x_1 \ right) -f \ left (x_2 \ right)} {x_1-x_2} = \ bigtriangledown f \ left ( x \ right), x \ in \ left (x_1-x_2 \ right) \ Rightarrow x = \ lambda x_1 + \ left (1- \ lambda \ right) x_2 $ vì S là tập lồi.

$ \ Rightarrow f \ left (x_1 \ right) - f \ left (x_2 \ right) = \ left (\ bigtriangledown f \ left (x \ right) ^ T \ right) \ left (x_1-x_2 \ right) $

với $ x, x_1 $, chúng tôi biết -

$ \ left (\ bigtriangledown f \ left (x \ right) - \ bigtriangledown f \ left (x_1 \ right) \ right) ^ T \ left (x-x_1 \ right) \ geq 0 $

$ \ Rightarrow \ left (\ bigtriangledown f \ left (x \ right) - \ bigtriangledown f \ left (x_1 \ right) \ right) ^ T \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2- x_1 \ right) \ geq 0 $

$ \ Rightarrow \ left (\ bigtriangledown f \ left (x \ right) - \ bigtriangledown f \ left (x_1 \ right) \ right) ^ T \ left (1- \ lambda \ right) \ left (x_2-x_1 \ right ) \ geq 0 $

$ \ Rightarrow \ bigtriangledown f \ left (x \ right) ^ T \ left (x_2-x_1 \ right) \ geq \ bigtriangledown f \ left (x_1 \ right) ^ T \ left (x_2-x_1 \ right) $

Kết hợp các phương trình trên, ta được -

$ \ Rightarrow \ bigtriangledown f \ left (x_1 \ right) ^ T \ left (x_2-x_1 \ right) \ leq f \ left (x_2 \ right) -f \ left (x_1 \ right) $

Do đó, sử dụng định lý cuối cùng, f là một hàm lồi.

Hai lần chức năng khác biệt

Gọi S là tập con khác rỗng của $ \ mathbb {R} ^ n $ và đặt $ f: S \ rightarrow \ mathbb {R} $ thì f được cho là có thể phân biệt hai lần tại $ \ bar {x} \ trong S $ nếu tồn tại vectơ $ \ bigtriangledown f \ left (\ bar {x} \ right), a \: nXn $ ma trận $ H \ left (x \ right) $ (được gọi là ma trận Hessian) và một hàm $ \ alpha: \ mathbb {R} ^ n \ rightarrow \ mathbb {R} $ sao cho $ f \ left (x \ right) = f \ left (\ bar {x} + x- \ bar {x} \ right) = f \ left (\ bar {x} \ right) + \ bigtriangledown f \ left (\ bar {x} \ right) ^ T \ left (x- \ bar {x} \ right) + \ frac {1} {2} \ left (x- \ bar {x} \ right) H \ left (\ bar {x} \ right) \ left (x- \ bar {x} \ right) $

trong đó $ \ alpha \ left (\ bar {x}, x- \ bar {x} \ right) \ rightarrow Oasx \ rightarrow \ bar {x} $