Optymalizacja wypukła - twierdzenie o punkcie najbliższym

Niech S będzie niepustym zamkniętym wypukłym zbiorem w $ \ mathbb {R} ^ n $ i niech $ y \ notin S $, a następnie $ \ istnieje $ punkt $ \ bar {x} \ w S $ z minimalną odległością od y, czyli $ \ left \ | y- \ bar {x} \ right \ | \ leq \ left \ | yx \ right \ | \ forall x \ in S. $

Co więcej, $ \ bar {x} $ jest punktem minimalizacji wtedy i tylko wtedy, gdy $ \ left (y- \ hat {x} \ right) ^ {T} \ left (x- \ hat {x} \ right) \ leq 0 $ lub $ \ left (y- \ hat {x}, x- \ hat {x} \ right) \ leq 0 $

Dowód

Istnienie najbliższego punktu

Ponieważ $ S \ ne \ phi, \ istnieje $ punkt $ \ hat {x} \ w S $ taki, że minimalna odległość S od y jest mniejsza lub równa $ \ left \ | y- \ hat {x} \ right \ | $.

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

Ponieważ $ \ hat {S} $ jest zamknięte i ograniczone, a ponieważ norma jest funkcją ciągłą, to zgodnie z twierdzeniem Weierstrassa istnieje minimalny punkt $ \ hat {x} \ w S $ taki, że $ \ left \ | y- \ hat {x} \ right \ | = Inf \ left \ {\ left \ | yx \ right \ |, x \ in S \ right \} $

Wyjątkowość

Załóżmy, że $ \ bar {x} \ in S $ taki, że $ \ left \ | y- \ hat {x} \ right \ | = \ left \ | y- \ hat {x} \ right \ | = \ alpha $

Ponieważ S jest wypukłe, $ \ frac {\ hat {x} + \ bar {x}} {2} \ w S $

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

Nie może to być ścisła nierówność, ponieważ $ \ hat {x} $ jest najbliżej y.

Dlatego $ \ left \ | y- \ hat {x} \ right \ | = \ mu \ left \ | y- \ hat {x} \ right \ | $, dla jakiegoś $ \ mu $

Teraz $ \ left \ | \ mu \ right \ | = 1. $ Jeśli $ \ mu = -1 $, to $ \ left (y- \ hat {x} \ right) = - \ left (y- \ hat {x} \ right) \ Rightarrow y = \ frac {\ hat {x} + \ bar {x}} {2} \ in S $

Ale $ y \ w S $. Stąd sprzeczność. Zatem $ \ mu = 1 \ Rightarrow \ hat {x} = \ bar {x} $

Dlatego punkt minimalizacji jest wyjątkowy.

W drugiej części dowodu załóżmy, że $ \ left (y- \ hat {x} \ right) ^ {\ tau} \ left (x- \ bar {x} \ right) \ leq 0 $ dla wszystkich $ x \ w S $

Teraz,

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

Zatem $ \ hat {x} $ jest punktem minimalizującym.

I odwrotnie, załóżmy, że $ \ hat {x} $ jest minimalnym punktem.

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

Ponieważ S jest zbiorem wypukłym.

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

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

I

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

Stąd udowodnione.