Optimisation convexe - Théorème du point le plus proche

Soit S un ensemble convexe fermé non vide dans $ \ mathbb {R} ^ n $ et soit $ y \ notin S $, alors $ \ existe $ un point $ \ bar {x} \ dans S $ avec une distance minimale de y, c'est-à-dire $ \ gauche \ | y- \ bar {x} \ droit \ | \ leq \ gauche \ | yx \ droite \ | \ forall x \ dans S. $

De plus, $ \ bar {x} $ est un point de minimisation si et seulement si $ \ left (y- \ hat {x} \ right) ^ {T} \ left (x- \ hat {x} \ right) \ leq 0 $ ou $ \ left (y- \ hat {x}, x- \ hat {x} \ right) \ leq 0 $

Preuve

Existence du point le plus proche

Puisque $ S \ ne \ phi, \ existe $ un point $ \ hat {x} \ dans S $ tel que la distance minimale de S à partir de y soit inférieure ou égale à $ \ left \ | y- \ hat {x} \ right \ | $.

Définissez $ \ hat {S} = S \ cap \ left \ {x: \ left \ | yx \ droite \ | \ leq \ gauche \ | y- \ hat {x} \ right \ | \ droite \} $

Puisque $ \ hat {S} $ est fermé et borné, et que la norme est une fonction continue, alors par le théorème de Weierstrass, il existe un point minimum $ \ hat {x} \ dans S $ tel que $ \ left \ | y- \ hat {x} \ right \ | = Inf \ left \ {\ left \ | yx \ right \ |, x \ in S \ right \} $

Unicité

Supposons $ \ bar {x} \ in S $ tel que $ \ left \ | y- \ hat {x} \ right \ | = \ left \ | y- \ hat {x} \ right \ | = \ alpha $

Puisque S est convexe, $ \ frac {\ hat {x} + \ bar {x}} {2} \ in S $

Mais, $ \ gauche \ | 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 $

Cela ne peut pas être une inégalité stricte car $ \ hat {x} $ est le plus proche de y.

Par conséquent, $ \ left \ | y- \ hat {x} \ right \ | = \ mu \ left \ | y- \ hat {x} \ right \ | $, pour quelques $ \ mu $

Maintenant $ \ left \ | \ mu \ right \ | = 1. $ Si $ \ mu = -1 $, alors $ \ left (y- \ hat {x} \ right) = - \ left (y- \ hat {x} \ right) \ Flèche droite y = \ frac {\ hat {x} + \ bar {x}} {2} \ en S $

Mais $ y \ dans S $. D'où la contradiction. Ainsi $ \ mu = 1 \ Rightarrow \ hat {x} = \ bar {x} $

Ainsi, minimiser le point est unique.

Pour la deuxième partie de la preuve, supposons $ \ left (y- \ hat {x} \ right) ^ {\ tau} \ left (x- \ bar {x} \ right) \ leq 0 $ pour tout $ x \ en S $

Maintenant,

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

$ \ Flèche droite \ gauche \ | yx \ droite \ | ^ {2} \ geq \ gauche \ | y- \ hat {x} \ right \ | ^ {2} $ car $ \ left \ | \ hat {x} -x \ right \ | ^ {2} \ geq 0 $ et $ \ left (\ hat {x} - x \ right) ^ {T} \ left (y- \ hat {x} \ right ) \ geq 0 $

Ainsi, $ \ hat {x} $ minimise le point.

Inversement, supposons que $ \ hat {x} $ est un point de minimisation.

$ \ Flèche droite \ gauche \ | yx \ droite \ | ^ {2} \ geq \ gauche \ | y- \ hat {x} \ right \ | ^ 2 \ forall x \ in S $

Puisque S est un ensemble convexe.

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

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

Et

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

$ \ Flèche droite \ gauche \ | 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 $

D'où prouvé.