Otimização convexa - Teorema do Ponto Mais Próximo

Seja S um convexo fechado não vazio definido em $ \ mathbb {R} ^ n $ e seja $ y \ notin S $, então $ \ existe $ um ponto $ \ bar {x} \ em S $ com distância mínima de y, ou seja, $ \ left \ | y- \ bar {x} \ right \ | \ leq \ left \ | yx \ right \ | \ forall x \ in S. $

Além disso, $ \ bar {x} $ é um ponto de minimização se e somente se $ \ left (y- \ hat {x} \ right) ^ {T} \ left (x- \ hat {x} \ right) \ leq 0 $ ou $ \ left (y- \ hat {x}, x- \ hat {x} \ right) \ leq 0 $

Prova

Existência do ponto mais próximo

Já que $ S \ ne \ phi, \ existe $ a ponto $ \ hat {x} \ em S $ tal que a distância mínima de S de y é menor ou igual a $ \ left \ | y- \ hat {x} \ right \ | $.

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

Como $ \ hat {S} $ é fechado e limitado, e como norma é uma função contínua, então pelo teorema de Weierstrass, existe um ponto mínimo $ \ hat {x} \ em S $ tal que $ \ left \ | y- \ hat {x} \ right \ | = Inf \ left \ {\ left \ | yx \ right \ |, x \ in S \ right \} $

Singularidade

Suponha $ \ bar {x} \ em S $ tal que $ \ left \ | y- \ hat {x} \ right \ | = \ left \ | y- \ hat {x} \ right \ | = \ alpha $

Como S é convexo, $ \ frac {\ hat {x} + \ bar {x}} {2} \ in S $

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

Não pode ser desigualdade estrita porque $ \ hat {x} $ é o mais próximo de y.

Portanto, $ \ left \ | y- \ hat {x} \ right \ | = \ mu \ left \ | y- \ hat {x} \ right \ | $, por algum $ \ mu $

Agora $ \ left \ | \ mu \ right \ | = 1. $ Se $ \ mu = -1 $, então $ \ left (y- \ hat {x} \ right) = - \ left (y- \ hat {x} \ right) \ Rightarrow y = \ frac {\ hat {x} + \ bar {x}} {2} \ in S $

Mas $ y \ em S $. Daí a contradição. Assim, $ \ mu = 1 \ Rightarrow \ hat {x} = \ bar {x} $

Assim, minimizar o ponto é único.

Para a segunda parte da prova, assuma $ \ left (y- \ hat {x} \ right) ^ {\ tau} \ left (x- \ bar {x} \ right) \ leq 0 $ para todos $ x \ em S $

Agora,

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

Assim, $ \ hat {x} $ é o ponto de minimização.

Por outro lado, assuma que $ \ hat {x} $ é um ponto de minimização.

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

Uma vez que S é conjunto convexo.

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

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

E

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

Daí provado.