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.