Fungsi Quasiconvex yang Dapat Dibedakan

Dalil

Misalkan S adalah cembung tidak kosong yang disetel dalam $ \ mathbb {R} ^ n $ dan $ f: S \ rightarrow \ mathbb {R} $ dapat terdiferensiasi pada S, maka f adalah quasiconvex jika dan hanya jika untuk $ x_1, x_2 \ dalam S $ dan $ f \ kiri (x_1 \ kanan) \ leq f \ kiri (x_2 \ kanan) $, kita memiliki $ \ bigtriangledown f \ kiri (x_2 \ kanan) ^ T \ kiri (x_2-x_1 \ kanan) \ leq 0 $

Bukti

Misalkan f menjadi fungsi quasiconvex.

Misalkan $ x_1, x_2 \ dalam S $ sehingga $ f \ kiri (x_1 \ kanan) \ leq f \ kiri (x_2 \ kanan) $

Dengan diferensiabilitas f pada $ x_2, \ lambda \ in \ left (0, 1 \ right) $

$ f \ kiri (\ lambda x_1 + \ kiri (1- \ lambda \ kanan) x_2 \ kanan) = f \ kiri (x_2 + \ lambda \ kiri (x_1-x_2 \ kanan) \ kanan) = f \ kiri (x_2 \ kanan ) + \ bigtriangledown f \ kiri (x_2 \ kanan) ^ T \ kiri (x_1-x_2 \ kanan) $

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

$ \ Kanan kanan f \ kiri (\ lambda x_1 + \ kiri (1- \ lambda \ kanan) x_2 \ kanan) -f \ kiri (x_2 \ kanan) -f \ kiri (x_2 \ kanan) = \ segitiga besar f \ kiri (x_2 \ kanan) ^ T \ kiri (x_1-x_2 \ kanan) $

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

Tetapi karena f adalah quasiconvex, $ f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ leq f \ left (x_2 \ right) $

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

Tapi $ \ alpha \ left (x_2, \ lambda \ left (x_1, x_2 \ right) \ right) \ rightarrow 0 $ sebagai $ \ lambda \ rightarrow 0 $

Oleh karena itu, $ \ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_1-x_2 \ right) \ leq 0 $

Berbicara

biarkan $ x_1, x_2 \ dalam S $ dan $ f \ kiri (x_1 \ kanan) \ leq f \ kiri (x_2 \ kanan) $, $ \ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_1, x_2 \ kanan) \ leq 0 $

Untuk menunjukkan bahwa f adalah quasiconvex, yaitu $ f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ leq f \ left (x_2 \ right) $

Proof by contradiction

Misalkan terdapat $ x_3 = \ lambda x_1 + \ left (1- \ lambda \ right) x_2 $ sehingga $ f \ left (x_2 \ right) <f \ left (x_3 \ right) $ untuk beberapa $ \ lambda \ in \ kiri (0, 1 \ kanan) $

Untuk $ x_2 $ dan $ x_3, \ bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_2-x_3 \ right) \ leq 0 $

$ \ Rightarrow - \ lambda \ bigtriangledown f \ kiri (x_3 \ kanan) ^ T \ kiri (x_2-x_3 \ kanan) \ leq 0 $

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

Untuk $ x_1 $ dan $ x_3, \ bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_1-x_3 \ right) \ leq 0 $

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

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

jadi, dari persamaan di atas, $ \ bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_1-x_2 \ right) = 0 $

Tentukan $ U = \ kiri \ {x: f \ kiri (x \ kanan) \ leq f \ kiri (x_2 \ kanan), x = \ mu x_2 + \ kiri (1- \ mu \ kanan) x_3, \ mu \ in \ kiri (0,1 \ kanan) \ kanan \} $

Jadi kita dapat menemukan $ x_0 \ dalam U $ sehingga $ x_0 = \ mu_0 x_2 = \ mu x_2 + \ kiri (1- \ mu \ kanan) x_3 $ untuk beberapa $ \ mu _0 \ in \ kiri (0,1 \ kanan ) $ yang terdekat dengan $ x_3 $ dan $ \ hat {x} \ in \ left (x_0, x_1 \ right) $ sedemikian rupa sehingga dengan teorema nilai mean,

$$ \ frac {f \ left (x_3 \ right) -f \ left (x_0 \ right)} {x_3-x_0} = \ bigtriangledown f \ left (\ hat {x} \ right) $$

$$ \ Rightarrow f \ left (x_3 \ right) = f \ left (x_0 \ right) + \ bigtriangledown f \ left (\ hat {x} \ kanan) ^ T \ kiri (x_3-x_0 \ kanan) $$

$$ \ Rightarrow f \ left (x_3 \ right) = f \ kiri (x_0 \ kanan) + \ mu_0 \ lambda f \ left (\ hat {x} \ kanan) ^ T \ kiri (x_1-x_2 \ kanan) $ $

Karena $ x_0 $ adalah kombinasi dari $ x_1 $ dan $ x_2 $ dan $ f \ left (x_2 \ right) <f \ left (\ hat {x} \ right) $

Dengan mengulangi prosedur awal, $ \ bigtriangledown f \ left (\ hat {x} \ right) ^ T \ left (x_1-x_2 \ right) = 0 $

Jadi, dengan menggabungkan persamaan di atas, kita mendapatkan:

$$ f \ kiri (x_3 \ kanan) = f \ kiri (x_0 \ kanan) \ leq f \ kiri (x_2 \ kanan) $$

$$ \ Panah kanan f \ kiri (x_3 \ kanan) \ leq f \ kiri (x_2 \ kanan) $$

Karenanya, ini adalah kontradiksi.

Contoh

Step 1 - $ f \ kiri (x \ kanan) = X ^ 3 $

$ Biarkan f \ kiri (x_1 \ kanan) \ leq f \ kiri (x_2 \ kanan) $

$ \ Panah Kanan x_ {1} ^ {3} \ leq x_ {2} ^ {3} \ Panah Kanan x_1 \ leq x_2 $

$ \ bigtriangledown f \ kiri (x_2 \ kanan) \ kiri (x_1-x_2 \ kanan) = 3x_ {2} ^ {2} \ kiri (x_1-x_2 \ kanan) \ leq 0 $

Jadi, $ f \ left (x \ right) $ adalah quasiconvex.

Step 2 - $ f \ kiri (x \ kanan) = x_ {1} ^ {3} + x_ {2} ^ {3} $

Misalkan $ \ topi {x_1} = \ kiri (2, -2 \ kanan) $ dan $ \ topi {x_2} = \ kiri (1, 0 \ kanan) $

jadi, $ f \ left (\ hat {x_1} \ right) = 0, f \ left (\ hat {x_2} \ right) = 1 \ Rightarrow f \ left (\ hat {x_1} \ right) \ setminus <f \ kiri (\ hat {x_2} \ kanan) $

Jadi, $ \ bigtriangledown f \ left (\ hat {x_2} \ right) ^ T \ left (\ hat {x_1} - \ hat {x_2} \ right) = \ left (3, 0 \ right) ^ T \ left (1, -2 \ kanan) = 3> 0 $

Karenanya $ f \ left (x \ right) $ bukan quasiconvex.