Hàm lồi và lõm

Cho $ f: S \ rightarrow \ mathbb {R} $, trong đó S là tập lồi khác rỗng trong $ \ mathbb {R} ^ n $, sau đó $ f \ left (x \ right) $ được cho là lồi trên S if $ 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), \ forall \ lambda \ in \ left (0,1 \ right) $.

Mặt khác, Giả sử $ f: S \ rightarrow \ mathbb {R} $, trong đó S là tập lồi khác rỗng trong $ \ mathbb {R} ^ n $, thì $ f \ left (x \ right) $ được cho là bị lõm trên S nếu $ f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ geq \ lambda f \ left (x_1 \ right) + \ left (1- \ lambda \ right ) f \ left (x_2 \ right), \ forall \ lambda \ in \ left (0, 1 \ right) $.

Giả sử $ f: S \ rightarrow \ mathbb {R} $ trong đó S là tập lồi khác rỗng trong $ \ mathbb {R} ^ n $, thì $ f \ left (x \ right) $ được cho là tập lồi hoàn toàn trên S if $ f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) <\ lambda f \ left (x_1 \ right) + \ left (1- \ lambda \ right) f \ left (x_2 \ right), \ forall \ lambda \ in \ left (0, 1 \ right) $.

Giả sử $ f: S \ rightarrow \ mathbb {R} $ trong đó S là tập lồi khác rỗng trong $ \ mathbb {R} ^ n $, sau đó $ f \ left (x \ right) $ được cho là hoàn toàn lõm trên S if $ f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right)> \ lambda f \ left (x_1 \ right) + \ left (1- \ lambda \ right) f \ left (x_2 \ right), \ forall \ lambda \ in \ left (0, 1 \ right) $.

Ví dụ

  • Một hàm tuyến tính vừa lồi vừa lõm.

  • $ f \ left (x \ right) = \ left | x \ right | $ là một hàm lồi.

  • $ f \ left (x \ right) = \ frac {1} {x} $ là một hàm lồi.

Định lý

Cho $ f_1, f_2, ..., f_k: \ mathbb {R} ^ n \ rightarrow \ mathbb {R} $ là các hàm lồi. Hãy xem xét hàm $ f \ left (x \ right) = \ displaystyle \ sum \ limit_ {j = 1} ^ k \ alpha_jf_j \ left (x \ right) $ trong đó $ \ alpha_j> 0, j = 1, 2 ,. ..k, $ thì $ f \ left (x \ right) $ là một hàm lồi.

Bằng chứng

Vì $ f_1, f_2, ... f_k $ là các hàm lồi

Do đó, $ f_i \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ leq \ lambda f_i \ left (x_1 \ right) + \ left (1- \ lambda \ right) f_i \ left (x_2 \ right), \ forall \ lambda \ in \ left (0, 1 \ right) $ và $ i = 1, 2, ...., k $

Hãy xem xét hàm $ f \ left (x \ right) $.

Vì thế,

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

$ = \ displaystyle \ sum \ limit_ {j = 1} ^ k \ alpha_jf_j \ left (\ lambda x_1 + 1- \ lambda \ right) x_2 \ leq \ displaystyle \ sum \ limit_ {j = 1} ^ k \ alpha_j \ lambda f_j \ left (x_1 \ right) + \ left (1- \ lambda \ right) f_j \ left (x_2 \ right) $

$ \ Rightarrow f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ leq \ lambda \ left (\ displaystyle \ sum \ limit_ {j = 1} ^ k \ alpha _jf_j \ left ( x_1 \ right) \ right) + \ left (\ displaystyle \ sum \ limit_ {j = 1} ^ k \ alpha _jf_j \ left (x_2 \ right) \ right) $

$ \ Rightarrow f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ leq \ lambda f \ left (x_2 \ right) \ leq \ left (1- \ lambda \ right) f \ trái (x_2 \ phải) $

Do đó, $ f \ left (x \ right) $ là một hàm lồi.

Định lý

Đặt $ f \ left (x \ right) $ là một hàm lồi trên một tập lồi $ S \ subset \ mathbb {R} ^ n $ thì một cực tiểu cục bộ của $ f \ left (x \ right) $ trên S là một cực tiểu toàn cục.

Bằng chứng

Đặt $ \ hat {x} $ là cực tiểu cục bộ cho $ f \ left (x \ right) $ và $ \ hat {x} $ không phải là cực tiểu cục bộ.

do đó, $ \ tồn tại \ hat {x} \ trong S $ sao cho $ f \ left (\ bar {x} \ right) <f \ left (\ hat {x} \ right) $

Vì $ \ hat {x} $ là cực tiểu cục bộ nên tồn tại vùng lân cận $ N_ \ varepsilon \ left (\ hat {x} \ right) $ sao cho $ f \ left (\ hat {x} \ right) \ leq f \ left (x \ right), \ forall x \ in N_ \ varepsilon \ left (\ hat {x} \ right) \ cap S $

Nhưng $ f \ left (x \ right) $ là một hàm lồi trên S, do đó đối với $ \ lambda \ in \ left (0, 1 \ right) $

chúng ta có $ \ lambda \ hat {x} + \ left (1- \ lambda \ right) \ bar {x} \ leq \ lambda f \ left (\ hat {x} \ right) + \ left (1- \ lambda \ right) f \ left (\ bar {x} \ right) $

$ \ Rightarrow \ lambda \ hat {x} + \ left (1- \ lambda \ right) \ bar {x} <\ lambda f \ left (\ hat {x} \ right) + \ left (1- \ lambda \ phải) f \ left (\ hat {x} \ right) $

$ \ Rightarrow \ lambda \ hat {x} + \ left (1- \ lambda \ right) \ bar {x} <f \ left (\ hat {x} \ right), \ forall \ lambda \ in \ left (0 , 1 \ phải) $

Nhưng đối với một số $ \ lambda <1 $ nhưng gần bằng 1, chúng ta có

$ \ lambda \ hat {x} + \ left (1- \ lambda \ right) \ bar {x} \ in N_ \ varepsilon \ left (\ hat {x} \ right) \ cap S $ và $ f \ left ( \ lambda \ hat {x} + \ left (1- \ lambda \ right) \ bar {x} \ right) <f \ left (\ bar {x} \ right) $

đó là một mâu thuẫn.

Do đó, $ \ bar {x} $ là cực tiểu toàn cục.

Epigraph

đặt S là tập con không rỗng trong $ \ mathbb {R} ^ n $ và đặt $ f: S \ rightarrow \ mathbb {R} $ thì epigraph của f được ký hiệu là epi (f) hoặc $ E_f $ là một tập con trong tổng số $ \ mathbb {R} ^ n + 1 $ được xác định bởi $ E_f = \ left \ {\ left (x, \ alpha \ right): x \ in \ mathbb {R} ^ n, \ alpha \ in \ mathbb { R}, f \ left (x \ right) \ leq \ alpha \ right \} $

Chữ viết

đặt S là một tập con không rỗng trong $ \ mathbb {R} ^ n $ và đặt $ f: S \ rightarrow \ mathbb {R} $, sau đó dấu gạch ngang của f được ký hiệu là hyp (f) hoặc $ H_f = \ left \ {\ left (x, \ alpha \ right): x \ in \ mathbb {R} ^ n, \ alpha \ in \ mathbb {R} ^ n, \ alpha \ in \ mathbb {R}, f \ left ( x \ right) \ geq \ alpha \ right \} $

Định lý

Gọi S là một tập lồi khác rỗng trong $ \ mathbb {R} ^ n $ và đặt $ f: S \ rightarrow \ mathbb {R} ^ n $, khi đó f là lồi nếu và chỉ khi biểu đồ $ E_f $ là một tập hợp lồi.

Bằng chứng

Cho f là một hàm lồi.

Để chỉ ra $ E_f $ là một tập hợp lồi.

Để $ \ left (x_1, \ alpha_1 \ right), \ left (x_2, \ alpha_2 \ right) \ trong E_f, \ lambda \ in \ left (0, 1 \ right) $

Để hiển thị $ \ lambda \ left (x_1, \ alpha_1 \ right) + \ left (1- \ lambda \ right) \ left (x_2, \ alpha_2 \ right) \ trong E_f $

$ \ Rightarrow \ left [\ lambda x_1 + \ left (1- \ lambda \ right) x_2, \ lambda \ alpha_1 + \ left (1- \ lambda \ right) \ alpha_2 \ right] \ trong E_f $

$ f \ left (x_1 \ right) \ leq \ alpha _1, f \ left (x_2 \ right) \ leq \ alpha _2 $

Do đó, $ 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 \ alpha_1 + \ left (1- \ lambda \ right) \ alpha_2 $

ngược

Cho $ E_f $ là một tập lồi.

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

tức là, để hiển thị nếu $ x_1, x_2 \ in S, \ lambda \ 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) $

Cho $ x_1, x_2 \ in S, \ lambda \ in \ left (0, 1 \ right), f \ left (x_1 \ right), f \ left (x_2 \ right) \ in \ mathbb {R} $

Vì $ E_f $ là một tập hợp lồi, $ \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2, \ lambda f \ left (x_1 \ right) + \ left (1- \ lambda \ right) \ phải) f \ left (x_2 \ right) \ trong E_f $

Do đó, $ 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) $