Optimización convexa: teorema del punto más cercano

Sea S un conjunto convexo cerrado no vacío en $ \ mathbb {R} ^ n $ y sea $ y \ notin S $, entonces $ \ existe $ un punto $ \ bar {x} \ en S $ con una distancia mínima desde y, es decir, $ \ left \ | y- \ bar {x} \ right \ | \ leq \ left \ | yx \ right \ | \ forall x \ en S. $

Además, $ \ bar {x} $ es un punto de minimización si y solo si $ \ left (y- \ hat {x} \ right) ^ {T} \ left (x- \ hat {x} \ right) \ leq 0 $ o $ \ left (y- \ hat {x}, x- \ hat {x} \ right) \ leq 0 $

Prueba

Existencia del punto más cercano

Desde $ S \ ne \ phi, \ existe $ un punto $ \ hat {x} \ en S $ tal que la distancia mínima de S desde y es menor o igual que $ \ left \ | y- \ hat {x} \ right \ | $.

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

Como $ \ hat {S} $ es cerrado y acotado, y dado que la norma es una función continua, entonces, según el teorema de Weierstrass, existe un punto mínimo $ \ hat {x} \ en S $ tal que $ \ left \ | y- \ hat {x} \ right \ | = Inf \ left \ {\ left \ | yx \ right \ |, x \ in S \ right \} $

Unicidad

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

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

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

No puede ser una desigualdad estricta porque $ \ hat {x} $ está más cerca de y.

Por lo tanto, $ \ left \ | y- \ hat {x} \ right \ | = \ mu \ left \ | y- \ hat {x} \ right \ | $, por unos $ \ mu $

Ahora $ \ left \ | \ mu \ right \ | = 1. $ Si $ \ mu = -1 $, entonces $ \ left (y- \ hat {x} \ right) = - \ left (y- \ hat {x} \ right) \ Flecha derecha y = \ frac {\ hat {x} + \ bar {x}} {2} \ in S $

Pero $ y \ en S $. De ahí la contradicción. Entonces $ \ mu = 1 \ Rightarrow \ hat {x} = \ bar {x} $

Por lo tanto, minimizar el punto es único.

Para la segunda parte de la prueba, suponga $ \ left (y- \ hat {x} \ right) ^ {\ tau} \ left (x- \ bar {x} \ right) \ leq 0 $ para todos $ x \ en S $

Ahora,

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

$ \ Flecha derecha \ izquierda \ | yx \ right \ | ^ {2} \ geq \ left \ | y- \ hat {x} \ right \ | ^ {2} $ porque $ \ left \ | \ hat {x} -x \ right \ | ^ {2} \ geq 0 $ y $ \ left (\ hat {x} - x \ right) ^ {T} \ left (y- \ hat {x} \ right ) \ geq 0 $

Por tanto, $ \ hat {x} $ minimiza el punto.

A la inversa, suponga que $ \ hat {x} $ es el punto de minimización.

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

Dado que S es un conjunto convexo.

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

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

Y

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

$ \ Flecha derecha \ izquierda \ | 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 $

Por lo tanto probado.