Optimasi Cembung - Teorema Titik Terdekat

Misalkan S adalah cembung tertutup yang tidak kosong yang ditetapkan di $ \ mathbb {R} ^ n $ dan misalkan $ y \ notin S $, maka $ \ ada $ satu poin $ \ bar {x} \ dalam S $ dengan jarak minimum dari y, yaitu, $ \ kiri \ | y- \ bar {x} \ kanan \ | \ leq \ kiri \ | yx \ kanan \ | \ forall x \ in S. $

Selain itu, $ \ bar {x} $ adalah titik meminimalkan jika dan hanya jika $ \ left (y- \ hat {x} \ right) ^ {T} \ left (x- \ hat {x} \ right) \ leq 0 $ atau $ \ kiri (y- \ hat {x}, x- \ hat {x} \ right) \ leq 0 $

Bukti

Keberadaan titik terdekat

Karena $ S \ ne \ phi, \ ada $ satu poin $ \ hat {x} \ di S $ sedemikian rupa sehingga jarak minimum S dari y kurang dari atau sama dengan $ \ left \ | y- \ topi {x} \ kanan \ | $.

Tentukan $ \ hat {S} = S \ cap \ left \ {x: \ left \ | yx \ kanan \ | \ leq \ kiri \ | y- \ topi {x} \ kanan \ | \ kanan \} $

Karena $ \ hat {S} $ ditutup dan dibatasi, dan karena norma adalah fungsi kontinu, maka menurut teorema Weierstrass, terdapat titik minimum $ \ hat {x} \ dalam S $ sehingga $ \ left \ | y- \ topi {x} \ kanan \ | = Inf \ kiri \ {\ kiri \ | yx \ kanan \ |, x \ dalam S \ kanan \} $

Keunikan

Misalkan $ \ bar {x} \ dalam S $ sehingga $ \ kiri \ | y- \ topi {x} \ kanan \ | = \ kiri \ | y- \ topi {x} \ kanan \ | = \ alpha $

Karena S cembung, $ \ frac {\ hat {x} + \ bar {x}} {2} \ in S $

Tapi, $ \ kiri \ | y- \ frac {\ topi {x} - \ bar {x}} {2} \ kanan \ | \ leq \ frac {1} {2} \ kiri \ | y- \ topi {x} \ kanan \ | + \ frac {1} {2} \ kiri \ | y- \ bar {x} \ kanan \ | = \ alpha $

Ini tidak bisa menjadi ketimpangan yang tegas karena $ \ hat {x} $ paling dekat dengan y.

Oleh karena itu, $ \ kiri \ | y- \ topi {x} \ kanan \ | = \ mu \ kiri \ | y- \ hat {x} \ right \ | $, untuk beberapa $ \ mu $

Sekarang $ \ kiri \ | \ mu \ kanan \ | = 1. $ Jika $ \ mu = -1 $, maka $ \ kiri (y- \ topi {x} \ kanan) = - \ kiri (y- \ topi {x} \ kanan) \ Panah kanan y = \ frac {\ hat {x} + \ bar {x}} {2} \ dalam S $

Tapi $ y \ dalam S $. Oleh karena itu kontradiksi. Jadi $ \ mu = 1 \ Rightarrow \ hat {x} = \ bar {x} $

Jadi, meminimalkan poin itu unik.

Untuk bagian kedua dari pembuktian, asumsikan $ \ left (y- \ hat {x} \ right) ^ {\ tau} \ left (x- \ bar {x} \ right) \ leq 0 $ untuk semua $ x \ dalam S $

Sekarang,

$ \ kiri \ | yx \ right \ | ^ {2} = \ kiri \ | y- \ topi {x} + \ topi {x} -x \ kanan \ | ^ {2} = \ kiri \ | y- \ topi {x} \ kanan \ | ^ {2} + \ kiri \ | \ topi {x} -x \ kanan \ | ^ {2} +2 \ kiri (\ topi {x} -x \ kanan) ^ {\ tau} \ kiri (y- \ topi {x} \ kanan) $

$ \ Rightarrow \ kiri \ | yx \ kanan \ | ^ {2} \ geq \ kiri \ | y- \ hat {x} \ right \ | ^ {2} $ karena $ \ kiri \ | \ hat {x} -x \ right \ | ^ {2} \ geq 0 $ dan $ \ left (\ hat {x} - x \ right) ^ {T} \ left (y- \ hat {x} \ kanan ) \ geq 0 $

Jadi, $ \ hat {x} $ meminimalkan poin.

Sebaliknya, asumsikan $ \ hat {x} $ adalah poin minimizimg.

$ \ Rightarrow \ kiri \ | yx \ kanan \ | ^ {2} \ geq \ kiri \ | y- \ hat {x} \ right \ | ^ 2 \ forall x \ in S $

Karena S adalah himpunan cembung.

$ \ Rightarrow \ lambda x + \ left (1- \ lambda \ right) \ hat {x} = \ hat {x} + \ lambda \ left (x- \ hat {x} \ kanan) \ dalam S $ seharga $ x \ dalam S $ dan $ \ lambda \ dalam \ kiri (0,1 \ kanan) $

Sekarang, $ \ kiri \ | y- \ topi {x} - \ lambda \ kiri (x- \ topi {x} \ kanan) \ kanan \ | ^ {2} \ geq \ kiri \ | y- \ topi {x} \ kanan \ | ^ 2 $

Dan

$ \ kiri \ | y- \ topi {x} - \ lambda \ kiri (x- \ topi {x} \ kanan) \ kanan \ | ^ {2} = \ kiri \ | y- \ topi {x} \ kanan \ | ^ {2} + \ lambda ^ 2 \ kiri \ | x- \ topi {x} \ kanan \ | ^ {2} -2 \ lambda \ kiri (y- \ topi {x} \ kanan) ^ {T} \ kiri (x- \ hat {x} \ kanan) $

$ \ Rightarrow \ kiri \ | y- \ topi {x} \ kanan \ | ^ {2} + \ lambda ^ {2} \ kiri \ | x- \ topi {x} \ kanan \ | -2 \ lambda \ kiri (y- \ topi {x} \ kanan) ^ {T} \ kiri (x- \ topi {x} \ kanan) \ geq \ kiri \ | y- \ topi {x} \ kanan \ | ^ {2} $

$ \ Rightarrow 2 \ lambda \ left (y- \ hat {x} \ kanan) ^ {T} \ left (x- \ hat {x} \ kanan) \ leq \ lambda ^ 2 \ left \ | x- \ topi {x} \ kanan \ | ^ 2 $

$ \ Rightarrow \ left (y- \ hat {x} \ right) ^ {T} \ left (x- \ hat {x} \ kanan) \ leq 0 $

Karenanya Terbukti.