Konvexe Optimierung - Satz zum nächsten Punkt

Sei S eine nicht leere geschlossene konvexe Menge in $ \ mathbb {R} ^ n $ und sei $ y \ notin S $, dann existiert $ \ $ ein Punkt $ \ bar {x} \ in S $ mit minimalem Abstand von y, dh $ \ left \ | y- \ bar {x} \ right \ | \ leq \ left \ | yx \ right \ | \ forall x \ in S. $

Außerdem ist $ \ bar {x} $ genau dann ein Minimierungspunkt, wenn $ \ left (y- \ hat {x} \ right) ^ {T} \ left (x- \ hat {x} \ right) \ leq 0 $ oder $ \ left (y- \ hat {x}, x- \ hat {x} \ right) \ leq 0 $

Beweis

Existenz des nächsten Punktes

Da $ S \ ne \ phi, \ existiert $ ein Punkt $ \ hat {x} \ in S $, so dass der Mindestabstand von S von y kleiner oder gleich $ \ left \ | ist y- \ hat {x} \ right \ | $.

Definieren Sie $ \ hat {S} = S \ cap \ left \ {x: \ left \ | yx \ right \ | \ leq \ left \ | y- \ hat {x} \ right \ | \ right \} $

Da $ \ hat {S} $ geschlossen und begrenzt ist und Norm eine stetige Funktion ist, existiert nach dem Weierstrass-Theorem ein Mindestpunkt $ \ hat {x} \ in S $, so dass $ \ left \ | y- \ hat {x} \ right \ | = Inf \ left \ {\ left \ | yx \ right \ |, x \ in S \ right \} $

Einzigartigkeit

Angenommen, $ \ bar {x} \ in S $, so dass $ \ left \ | y- \ hat {x} \ right \ | = \ left \ | y- \ hat {x} \ right \ | = \ alpha $

Da S konvex ist, ist $ \ frac {\ hat {x} + \ bar {x}} {2} \ in S $

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

Es kann keine strikte Ungleichung sein, da $ \ hat {x} $ y am nächsten ist.

Daher $ \ left \ | y- \ hat {x} \ right \ | = \ mu \ left \ | y- \ hat {x} \ right \ | $, für einige $ \ mu $

Jetzt $ \ left \ | \ mu \ right \ | = 1. $ Wenn $ \ mu = -1 $, dann ist $ \ left (y- \ hat {x} \ right) = - \ left (y- \ hat {x} \ right) \ Rechter Pfeil y = \ frac {\ hat {x} + \ bar {x}} {2} \ in S $

Aber $ y \ in S $. Daher Widerspruch. Also $ \ mu = 1 \ Rightarrow \ hat {x} = \ bar {x} $

Somit ist der Minimierungspunkt einzigartig.

Nehmen Sie für den zweiten Teil des Beweises $ \ left (y- \ hat {x} \ right) ^ {\ tau} \ left (x- \ bar {x} \ right) \ leq 0 $ für alle $ x \ an in S $

Jetzt,

$ \ 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} $ weil $ \ left \ | \ hat {x} -x \ right \ | ^ {2} \ geq 0 $ und $ \ left (\ hat {x} - x \ right) ^ {T} \ left (y- \ hat {x} \ right ) \ geq 0 $

Somit minimiert $ \ hat {x} $ den Punkt.

Nehmen Sie umgekehrt an, dass $ \ hat {x} $ ein Minimierungspunkt ist.

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

Da S konvex gesetzt ist.

$ \ Rightarrow \ lambda x + \ left (1- \ lambda \ right) \ hat {x} = \ hat {x} + \ lambda \ left (x- \ hat {x} \ right) \ in S $ für $ x \ in S $ und $ \ lambda \ in \ left (0,1 \ right) $

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

Und

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

Daher bewiesen.