Convex Optimization - ทฤษฎีบทจุดที่ใกล้ที่สุด

ให้ S เป็นค่านูนปิดที่ไม่ว่างเปล่าที่กำหนดไว้ใน $ \ mathbb {R} ^ n $ และให้ $ y \ notin S $ แล้ว $ \ มีอยู่ $ a point $ \ bar {x} \ ใน S $ โดยมีระยะห่างต่ำสุดจาก y เช่น $ \ left \ | y- \ bar {x} \ right \ | \ leq \ left \ | yx \ right \ | \ forall x \ ใน S. $

นอกจากนี้ $ \ bar {x} $ ยังเป็นจุดที่ลดขนาดลงก็ต่อเมื่อ $ \ left (y- \ hat {x} \ right) ^ {T} \ left (x- \ hat {x} \ right) \ leq 0 $ หรือ $ \ left (y- \ hat {x}, x- \ hat {x} \ right) \ leq 0 $

หลักฐาน

การดำรงอยู่ของจุดที่ใกล้เคียงที่สุด

เนื่องจาก $ S \ ne \ phi มี $ a point $ \ hat {x} \ ใน S $ ดังนั้นระยะทางต่ำสุดของ S จาก y น้อยกว่าหรือเท่ากับ $ \ left \ | y- \ hat {x} \ right \ | $.

กำหนด $ \ hat {S} = S \ cap \ left \ {x: \ left \ | yx \ right \ | \ leq \ left \ | y- \ hat {x} \ right \ | \ right \} $

เนื่องจาก $ \ hat {S} $ ถูกปิดและมีขอบเขตและเนื่องจากบรรทัดฐานเป็นฟังก์ชันต่อเนื่องดังนั้นตามทฤษฎีบทของ Weierstrass จึงมีจุดต่ำสุด $ \ hat {x} \ ใน S $ ซึ่งเท่ากับ $ \ left \ | y- \ hat {x} \ right \ | = Inf \ left \ {\ left \ | yx \ right \ |, x \ ใน S \ right \} $

ความเป็นเอกลักษณ์

สมมติว่า $ \ bar {x} \ ใน S $ เช่นนั้น $ \ left \ | y- \ hat {x} \ right \ | = \ left \ | y- \ hat {x} \ right \ | = \ alpha $

เนื่องจาก S มีความนูน $ \ frac {\ hat {x} + \ bar {x}} {2} \ ใน S $

แต่ $ \ 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 $

ไม่สามารถเป็นอสมการที่เข้มงวดได้เนื่องจาก $ \ hat {x} $ อยู่ใกล้ y มากที่สุด

ดังนั้น $ \ left \ | y- \ hat {x} \ right \ | = \ mu \ left \ | y- \ hat {x} \ right \ | $ สำหรับบาง $ \ mu $

ตอนนี้ $ \ left \ | \ mu \ right \ | = 1. $ ถ้า $ \ mu = -1 $ แล้ว $ \ left (y- \ hat {x} \ right) = - \ left (y- \ hat {x} \ right) \ Rightarrow y = \ frac {\ hat {x} + \ bar {x}} {2} \ ใน S $

แต่ $ y \ ใน S $ ดังนั้นความขัดแย้ง ดังนั้น $ \ mu = 1 \ Rightarrow \ hat {x} = \ bar {x} $

ดังนั้นการย่อจุดจึงไม่เหมือนใคร

สำหรับส่วนที่สองของการพิสูจน์ให้สมมติว่า $ \ left (y- \ hat {x} \ right) ^ {\ tau} \ left (x- \ bar {x} \ right) \ leq 0 $ สำหรับ $ x ทั้งหมดทั้งหมด ใน S $

ตอนนี้

$ \ 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} $ เพราะ $ \ left \ | \ หมวก {x} -x \ right \ | ^ {2} \ geq 0 $ และ $ \ left (\ hat {x} - x \ right) ^ {T} \ left (y- \ hat {x} \ right ) \ geq 0 $

ดังนั้น $ \ hat {x} $ จึงเป็นจุดที่ลดลง

ในทางกลับกันสมมติว่า $ \ hat {x} $ คือ minimizimg point

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

เนื่องจาก S เป็นชุดนูน

$ \ Rightarrow \ lambda x + \ left (1- \ lambda \ right) \ hat {x} = \ hat {x} + \ lambda \ left (x- \ hat {x} \ right) \ ใน S $ สำหรับ $ x \ ใน S $ และ $ \ lambda \ in \ left (0,1 \ right) $

ตอนนี้ $ \ left \ | y- \ hat {x} - \ lambda \ left (x- \ hat {x} \ right) \ right \ | ^ {2} \ geq \ left \ | y- \ hat {x} \ right \ | ^ 2 $

และ

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

ดังนั้นพิสูจน์แล้ว