Pengoptimalan Cembung - Fungsi yang Dapat Dibedakan

Misalkan S adalah himpunan terbuka yang tidak kosong di $ \ mathbb {R} ^ n $, lalu $ f: S \ rightarrow \ mathbb {R} $ dikatakan dapat dibedakan pada $ \ hat {x} \ dalam S $ jika ada vektor $ \ bigtriangledown f \ left (\ hat {x} \ right) $ disebut vektor gradien dan fungsi $ \ alpha: \ mathbb {R} ^ n \ rightarrow \ mathbb {R} $ sedemikian rupa sehingga

$ f \ kiri (x \ kanan) = f \ kiri (\ topi {x} \ kanan) + \ bigtriangledown f \ kiri (\ topi {x} \ kanan) ^ T \ kiri (x- \ topi {x} \ kanan) + \ kiri \ | x = \ hat {x} \ right \ | \ alpha \ left (\ hat {x}, x- \ hat {x} \ right), \ forall x \ in S $ di mana

$ \ alpha \ left (\ hat {x}, x- \ hat {x} \ right) \ rightarrow 0 \ bigtriangledown f \ left (\ hat {x} \ right) = \ left [\ frac {\ partial f} {\ sebagian x_1} \ frac {\ sebagian f} {\ sebagian x_2} ... \ frac {\ sebagian f} {\ sebagian x_n} \ kanan] _ {x = \ hat {x}} ^ {T} $

Dalil

misalkan S tidak kosong, himpunan konveks terbuka di $ \ mathbb {R} ^ n $ dan misalkan $ f: S \ rightarrow \ mathbb {R} $ dapat terdiferensiasi pada S. Kemudian, f adalah konveks jika dan hanya jika untuk $ x_1, x_2 \ di S, \ bigtriangledown f \ kiri (x_2 \ kanan) ^ T \ kiri (x_1-x_2 \ kanan) \ leq f \ kiri (x_1 \ kanan) -f \ kiri (x_2 \ kanan) $

Bukti

Misalkan f adalah fungsi cembung. yaitu, untuk $ x_1, x_2 \ in S, \ lambda \ in \ left (0, 1 \ right) $

$ f \ kiri [\ lambda x_1 + \ kiri (1- \ lambda \ kanan) x_2 \ kanan] \ leq \ lambda f \ kiri (x_1 \ kanan) + \ kiri (1- \ lambda \ kanan) f \ kiri (x_2 \ benar) $

$ \ Kanan ke kanan f \ kiri [\ lambda x_1 + \ kiri (1- \ lambda \ kanan) x_2 \ kanan] \ leq \ lambda \ kiri (f \ kiri (x_1 \ kanan) -f \ kiri (x_2 \ kanan) \ kanan ) + f \ kiri (x_2 \ kanan) $

$ \ Kananarrow \ lambda \ kiri (f \ kiri (x_1 \ kanan) -f \ kiri (x_2 \ kanan) \ kanan) \ geq f \ kiri (x_2 + \ lambda \ kiri (x_1-x_2 \ kanan) \ kanan) - f \ kiri (x_2 \ kanan) $

$ \ Kananarrow \ lambda \ kiri (f \ kiri (x_1 \ kanan) -f \ kiri (x_2 \ kanan) \ kanan) \ geq f \ kiri (x_2 \ kanan) + \ bigtriangledown f \ kiri (x_2 \ kanan) ^ T \ kiri (x_1-x_2 \ kanan) \ lambda + $

$ \ kiri \ | \ lambda \ kiri (x_1-x_2 \ kanan) \ kanan \ | \ alpha \ kiri (x_2, \ lambda \ kiri (x_1 - x_2 \ kanan) -f \ kiri (x_2 \ kanan) \ kanan) $

di mana $ \ alpha \ left (x_2, \ lambda \ left (x_1 - x_2 \ right) \ right) \ rightarrow 0 $ sebagai $ \ lambda \ rightarrow 0 $

Membagi dengan $ \ lambda $ di kedua sisi, kita dapatkan -

$ f \ kiri (x_1 \ kanan) -f \ kiri (x_2 \ kanan) \ geq \ bigtriangledown f \ kiri (x_2 \ kanan) ^ T \ kiri (x_1-x_2 \ kanan) $

Berbicara

Misalkan untuk $ 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) $

Untuk menunjukkan bahwa f cembung.

Karena S cembung, $ x_3 = \ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ in S, \ lambda \ in \ left (0, 1 \ right) $

Karena itu, sejak $ x_1, x_3 \ dalam S $

$ f \ kiri (x_1 \ kanan) -f \ kiri (x_3 \ kanan) \ geq \ bigtriangledown f \ kiri (x_3 \ kanan) ^ T \ kiri (x_1 -x_3 \ kanan) $

$ \ Panah kanan f \ kiri (x_1 \ kanan) -f \ kiri (x_3 \ kanan) \ geq \ bigtriangledown f \ kiri (x_3 \ kanan) ^ T \ kiri (x_1 - \ lambda x_1- \ kiri (1- \ lambda \ kanan) x_2 \ kanan) $

$ \ 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 \ benar) $

Karena, $ x_2, x_3 \ dalam S $ karenanya

$ f \ kiri (x_2 \ kanan) -f \ kiri (x_3 \ kanan) \ geq \ bigtriangledown f \ kiri (x_3 \ kanan) ^ T \ kiri (x_2-x_3 \ kanan) $

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

$ \ 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 \ benar) $

Jadi, dengan menggabungkan persamaan di atas, kita mendapatkan -

$ \ lambda \ kiri (f \ kiri (x_1 \ kanan) -f \ kiri (x_3 \ kanan) \ kanan) + \ kiri (1- \ lambda \ kanan) \ kiri (f \ kiri (x_2 \ kanan) -f \ kiri (x_3 \ kanan) \ kanan) \ geq 0 $

$ \ Panah kanan f \ kiri (x_3 \ kanan) \ leq \ lambda f \ kiri (x_1 \ kanan) + \ kiri (1- \ lambda \ kanan) f \ kiri (x_2 \ kanan) $

Dalil

misalkan S adalah cembung terbuka yang tidak kosong yang disetel dalam $ \ mathbb {R} ^ n $ dan misalkan $ f: S \ rightarrow \ mathbb {R} $ dapat terdiferensiasi pada S, maka f adalah konveks pada S jika dan hanya jika untuk $ 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 $

Bukti

biarkan f menjadi fungsi cembung, lalu gunakan teorema sebelumnya -

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

$ \ bigtriangledown f \ kiri (x_1 \ kanan) ^ T \ kiri (x_2-x_1 \ kanan) \ leq f \ kiri (x_2 \ kanan) -f \ kiri (x_1 \ kanan) $

Menambahkan dua persamaan di atas, kita mendapatkan -

$ \ bigtriangledown f \ kiri (x_2 \ kanan) ^ T \ kiri (x_1-x_2 \ kanan) + \ bigtriangledown f \ kiri (x_1 \ kanan) ^ T \ kiri (x_2-x_1 \ kanan) \ leq 0 $

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

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

Berbicara

Biarkan untuk $ 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 $

Untuk menunjukkan bahwa f cembung.

Misalkan $ x_1, x_2 \ dalam S $, jadi dengan teorema nilai rata-rata, $ \ frac {f \ left (x_1 \ right) -f \ left (x_2 \ right)} {x_1-x_2} = \ bigtriangledown f \ left ( x \ kanan), x \ in \ left (x_1-x_2 \ right) \ Rightarrow x = \ lambda x_1 + \ left (1- \ lambda \ right) x_2 $ karena S adalah himpunan cembung.

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

untuk $ x, x_1 $, kami tahu -

$ \ kiri (\ bigtriangledown f \ kiri (x \ kanan) - \ bigtriangledown f \ kiri (x_1 \ kanan) \ kanan) ^ T \ kiri (x-x_1 \ kanan) \ geq 0 $

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

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

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

Menggabungkan persamaan di atas, kita mendapatkan -

$ \ Kananarrow \ bigtriangledown f \ kiri (x_1 \ kanan) ^ T \ kiri (x_2-x_1 \ kanan) \ leq f \ kiri (x_2 \ kanan) -f \ kiri (x_1 \ kanan) $

Karenanya, menggunakan teorema terakhir, f adalah fungsi cembung.

Fungsi yang Dapat Dibedakan Dua Kali

Misalkan S adalah subset yang tidak kosong dari $ \ mathbb {R} ^ n $ dan misalkan $ f: S \ rightarrow \ mathbb {R} $ maka f dikatakan dapat terdiferensiasi dua kali pada $ \ bar {x} \ in S $ jika ada vektor $ \ bigtriangledown f \ left (\ bar {x} \ right), a \: nXn $ matrix $ H \ left (x \ right) $ (disebut matriks Hessian) dan fungsi $ \ alpha: \ mathbb {R} ^ n \ rightarrow \ mathbb {R} $ sedemikian sehingga $ f \ left (x \ right) = f \ left (\ bar {x} + x- \ bar {x} \ right) = f \ kiri (\ bar {x} \ kanan) + \ bigtriangledown f \ left (\ bar {x} \ right) ^ T \ left (x- \ bar {x} \ kanan) + \ frac {1} {2} \ kiri (x- \ bar {x} \ kanan) H \ kiri (\ bar {x} \ kanan) \ kiri (x- \ bar {x} \ kanan) $

di mana $ \ alpha \ left (\ bar {x}, x- \ bar {x} \ right) \ rightarrow Oasx \ rightarrow \ bar {x} $