Учебники

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

Пусть S – непустое замкнутое выпуклое множество в  mathbbRn, и пусть y notinS, тогда  существует точка  barx inS с минимальным расстоянием от у, т. е. $ \ left \ | y- \ bar {x} \ right \ | \ leq \ left \ | yx \ right \ | \ forall x \ in S. $

Кроме того,  barx является минимизирующей точкой тогда и только тогда, когда  left(y hatx right)T left(x hatx right) leq0 или  left(y hatx,x hatx right) leq0

доказательство

Наличие ближайшей точки

Поскольку S ne phi, существует точка  hatx inS, такая, что минимальное расстояние S от y меньше или равно $ \ left \ | y- \ hat {x} \ right \ | $.

Определите $ \ hat {S} = S \ cap \ left \ {x: \ left \ | yx \ right \ | \ leq \ left \ | y- \ hat {x} \ right \ | \ right \} $

Поскольку  hatS замкнуто и ограничено, а норма является непрерывной функцией, то по теореме Вейерштрасса существует минимальная точка  hatx вS такая, что $ \ left \ | y- \ hat {x} \ right \ | = Inf \ left \ {\ left \ | yx \ right \ |, x \ in S \ right \} $

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

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

Поскольку S выпуклая,  frac hatx+ barx2 inS

Но, $ \ 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 $

Это не может быть строгим неравенством, потому что  hatx ближе всего к 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 inS. Отсюда и противоречие. Таким образом,  mu=1 Rightarrow hatx= barx

Таким образом, точка минимизации уникальна.

Во второй части доказательства предположим, что  left(y hatx right) tau left(x barx right) leq0 для всех 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 $

Таким образом,  hatx является минимизирующей точкой.

И наоборот, предположим, что  hatx является минимизируемой точкой.

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

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

 Rightarrow lambdax+ left(1 lambda right) hatx= hatx+ lambda left(x hatx right) inS для x inS и  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 hatx right)T left(x hatx right) leq0

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