Tối ưu hóa lồi - Định lý điểm gần nhất

Gọi S là một tập lồi đóng không rỗng trong $ \ mathbb {R} ^ n $ và đặt $ y \ notin S $, thì $ \ tồn tại $ a point $ \ bar {x} \ in S $ với khoảng cách nhỏ nhất từ y, tức là, $ \ left \ | y- \ bar {x} \ right \ | \ leq \ left \ | yx \ right \ | \ forall x \ in S. $

Hơn nữa, $ \ bar {x} $ là điểm thu nhỏ nếu và chỉ khi $ \ left (y- \ hat {x} \ right) ^ {T} \ left (x- \ hat {x} \ right) \ leq 0 $ hoặc $ \ left (y- \ hat {x}, x- \ hat {x} \ right) \ leq 0 $

Bằng chứng

Sự tồn tại của điểm gần nhất

Vì $ S \ ne \ phi, \ tồn tại $ a point $ \ hat {x} \ trong S $ sao cho khoảng cách tối thiểu của S từ y nhỏ hơn hoặc bằng $ \ left \ | y- \ hat {x} \ right \ | $.

Xác định $ \ hat {S} = S \ cap \ left \ {x: \ left \ | yx \ right \ | \ leq \ left \ | y- \ hat {x} \ right \ | \ right \} $

Vì $ \ hat {S} $ là đóng và có giới hạn, và vì chuẩn là một hàm liên tục, nên theo định lý Weierstrass, tồn tại một điểm nhỏ nhất $ \ hat {x} \ trong S $ sao cho $ \ left \ | y- \ hat {x} \ right \ | = Inf \ left \ {\ left \ | yx \ right \ |, x \ trong S \ right \} $

Tính độc đáo

Giả sử $ \ bar {x} \ trong S $ sao cho $ \ left \ | y- \ hat {x} \ right \ | = \ left \ | y- \ hat {x} \ right \ | = \ alpha $

Vì S là lồi nên $ \ frac {\ hat {x} + \ bar {x}} {2} \ in S $

Nhưng, $ \ left \ | y- \ frac {\ hat {x} - \ bar {x}} {2} \ right \ | \ leq \ frac {1} {2} \ left \ | y- \ hat {x} \ right \ | + \ frac {1} {2} \ left \ | y- \ bar {x} \ right \ | = \ alpha $

Nó không thể là bất đẳng thức nghiêm ngặt vì $ \ hat {x} $ gần nhất với y.

Do đó, $ \ left \ | y- \ hat {x} \ right \ | = \ mu \ left \ | y- \ hat {x} \ right \ | $, với một số $ \ mu $

Bây giờ $ \ left \ | \ mu \ right \ | = 1. $ Nếu $ \ mu = -1 $ thì $ \ left (y- \ hat {x} \ right) = - \ left (y- \ hat {x} \ right) \ Rightarrow y = \ frac {\ hat {x} + \ bar {x}} {2} \ in S $

Nhưng $ y \ bằng S $. Do đó mâu thuẫn. Do đó $ \ mu = 1 \ Rightarrow \ hat {x} = \ bar {x} $

Do đó, điểm tối thiểu là duy nhất.

Đối với phần thứ hai của bằng chứng, giả sử $ \ left (y- \ hat {x} \ right) ^ {\ tau} \ left (x- \ bar {x} \ right) \ leq 0 $ cho tất cả $ x \ bằng S $

Hiện nay,

$ \ left \ | yx \ right \ | ^ {2} = \ left \ | y- \ hat {x} + \ hat {x} -x \ right \ | ^ {2} = \ left \ | y- \ hat {x} \ right \ | ^ {2} + \ left \ | \ hat {x} -x \ right \ | ^ {2} +2 \ left (\ hat {x} -x \ right) ^ {\ tau} \ left (y- \ hat {x} \ right) $

$ \ Rightarrow \ left \ | yx \ right \ | ^ {2} \ geq \ left \ | y- \ hat {x} \ right \ | ^ {2} $ vì $ \ left \ | \ hat {x} -x \ right \ | ^ {2} \ geq 0 $ và $ \ left (\ hat {x} - x \ right) ^ {T} \ left (y- \ hat {x} \ right ) \ geq 0 $

Do đó, $ \ hat {x} $ là điểm cực tiểu.

Ngược lại, giả sử $ \ hat {x} $ là điểm cực tiểu.

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

Vì S là tập lồi.

$ \ Rightarrow \ lambda x + \ left (1- \ lambda \ right) \ hat {x} = \ hat {x} + \ lambda \ left (x- \ hat {x} \ right) \ in S $ với $ x \ in S $ và $ \ lambda \ in \ left (0,1 \ right) $

Bây giờ, $ \ left \ | y- \ hat {x} - \ lambda \ left (x- \ hat {x} \ right) \ right \ | ^ {2} \ geq \ left \ | y- \ hat {x} \ right \ | ^ 2 $

Và

$ \ left \ | y- \ hat {x} - \ lambda \ left (x- \ hat {x} \ right) \ right \ | ^ {2} = \ left \ | y- \ hat {x} \ right \ | ^ {2} + \ lambda ^ 2 \ left \ | x- \ hat {x} \ right \ | ^ {2} -2 \ lambda \ left (y- \ hat {x} \ right) ^ {T} \ left (x- \ hat {x} \ right) $

$ \ Rightarrow \ left \ | y- \ hat {x} \ right \ | ^ {2} + \ lambda ^ {2} \ left \ | x- \ hat {x} \ right \ | -2 \ lambda \ left (y- \ hat {x} \ right) ^ {T} \ left (x- \ hat {x} \ right) \ geq \ left \ | y- \ hat {x} \ right \ | ^ {2} $

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

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

Do đó đã được chứng minh.