Выпуклая оптимизация — теорема о ближайшей точке

Пусть S — непустое замкнутое выпуклое множество в $\ mathbb {R} ^ n$, и пусть $y \ notin S$, тогда $\ существует$ точка $\ bar {x} \ in S$ с минимальным расстоянием от у, т. е. $ \ left \ | y- \ bar {x} \ right \ | \ leq \ left \ | yx \ right \ | \ forall x \ in 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, \ существует$ точка $\ hat {x} \ in 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}$ замкнуто и ограничено, а норма является непрерывной функцией, то по теореме Вейерштрасса существует минимальная точка $\ hat {x} \ в S$ такая, что $ \ left \ | y- \ hat {x} \ right \ | = Inf \ left \ {\ left \ | yx \ right \ |, x \ in S \ right \} $

уникальность

Предположим, что $\ bar {x} \ in S$ такой, что $ \ left \ | y- \ hat {x} \ right \ | = \ left \ | y- \ hat {x} \ right \ | = \ alpha $

Поскольку S выпуклая, $\ frac {\ hat {x} + \ bar {x}} {2} \ in 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) \ Правая стрелка y = \ frac {\ hat {x} + \ bar {x}} {2} \ in S $

Но $y \ in 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 \ | \ hat {x} -x \ right \ | ^ {2} \ geq 0 $и$ \ left (\ hat {x} — x \ right) ^ {T} \ left (y- \ hat {x} \ right ) \ geq 0 $

Таким образом, $\ hat {x}$ является минимизирующей точкой.

И наоборот, предположим, что $\ hat {x}$ является минимизируемой точкой.

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

Так как S выпуклое множество.

$\ Rightarrow \ lambda x + \ left (1- \ lambda \ right) \ hat {x} = \ hat {x} + \ lambda \ left (x- \ hat {x} \ right) \ in S$ для $x \ in 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$

Отсюда доказано.