Ottimizzazione convessa - Teorema del punto più vicino

Sia S un insieme convesso chiuso non vuoto in $ \ mathbb {R} ^ n $ e $ y \ notin S $, allora $ \ esiste $ un punto $ \ bar {x} \ in S $ con una distanza minima da y, cioè $ \ left \ | y- \ bar {x} \ right \ | \ leq \ sinistra \ | yx \ right \ | \ forall x \ in S. $

Inoltre, $ \ bar {x} $ è un punto di minimizzazione se e solo se $ \ left (y- \ hat {x} \ right) ^ {T} \ left (x- \ hat {x} \ right) \ leq 0 $ o $ \ left (y- \ hat {x}, x- \ hat {x} \ right) \ leq 0 $

Prova

Esistenza del punto più vicino

Poiché $ S \ ne \ phi, \ esiste $ un punto $ \ hat {x} \ in S $ tale che la distanza minima di S da y sia minore o uguale a $ \ left \ | y- \ hat {x} \ right \ | $.

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

Poiché $ \ hat {S} $ è chiuso e limitato, e poiché la norma è una funzione continua, per il teorema di Weierstrass esiste un punto minimo $ \ hat {x} \ in S $ tale che $ \ left \ | y- \ hat {x} \ right \ | = Inf \ left \ {\ left \ | yx \ right \ |, x \ in S \ right \} $

Unicità

Supponiamo $ \ bar {x} \ in S $ tale che $ \ left \ | y- \ hat {x} \ right \ | = \ left \ | y- \ hat {x} \ right \ | = \ alpha $

Poiché S è convesso, $ \ frac {\ hat {x} + \ bar {x}} {2} \ in S $

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

Non può essere una disuguaglianza rigorosa perché $ \ hat {x} $ è il più vicino a y.

Pertanto, $ \ left \ | y- \ hat {x} \ right \ | = \ mu \ left \ | y- \ hat {x} \ right \ | $, per qualche $ \ mu $

Ora $ \ sinistra \ | \ mu \ right \ | = 1. $ Se $ \ mu = -1 $, allora $ \ left (y- \ hat {x} \ right) = - \ left (y- \ hat {x} \ right) \ Freccia a destra y = \ frac {\ hat {x} + \ bar {x}} {2} \ in S $

Ma $ y \ in S $. Da qui la contraddizione. Quindi $ \ mu = 1 \ Rightarrow \ hat {x} = \ bar {x} $

Pertanto, il punto di minimizzazione è unico.

Per la seconda parte della dimostrazione, supponiamo $ \ left (y- \ hat {x} \ right) ^ {\ tau} \ left (x- \ bar {x} \ right) \ leq 0 $ per tutti $ x \ in S $

Adesso,

$ \ sinistra \ | yx \ destra \ | ^ {2} = \ sinistra \ | 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) $

$ \ Freccia destra \ sinistra \ | yx \ destra \ | ^ {2} \ geq \ sinistra \ | y- \ hat {x} \ right \ | ^ {2} $ perché $ \ left \ | \ hat {x} -x \ right \ | ^ {2} \ geq 0 $ e $ \ left (\ hat {x} - x \ right) ^ {T} \ left (y- \ hat {x} \ right ) \ geq 0 $

Quindi, $ \ hat {x} $ sta minimizzando il punto.

Al contrario, supponiamo che $ \ hat {x} $ sia il punto minimizimg.

$ \ Freccia destra \ sinistra \ | yx \ destra \ | ^ {2} \ geq \ sinistra \ | y- \ hat {x} \ right \ | ^ 2 \ forall x \ in S $

Poiché S è un insieme convesso.

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

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

E

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

$ \ Freccia destra \ sinistra \ | 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 $

Quindi dimostrato.