Minimisation de fonction - polyèdres

[razorbladeetc62]

Bonjour,

Un polyèdre convexe de Rn est défini par un ensemble fini d'inéquations linéaires représentant les arêtes du polyèdre, ou par un ensemble fini de points de Rn représentant les sommets du polyèdre.

Je définis la distance (dite locale) d'un point de Rn à un polyèdre P comme étant la distance minimale entre ce point et n'importe quel point de P (limitons nous à la distance euclidienne...)

Je définis la distance (dite globale) d'un point de Rn à un ensemble fini de polyèdres comme étant la somme des distances entre ce point et chacun des polyèdres.

L'ensemble des points minimisant cette distance globale forme un ensemble convexe. Mais je voudrais montrer qu'il forme en fait un polyèdre!!

Auriez-vous une intuition?

[miikou]

salut,

connaissant les sommet tu peux en deduire les equations des plan formant ton polyedre, ensuite tu recherche la distance dun point a un plan ( ici il ya plusieurs cas a traiter) ca doit surement donner qq chose d'interessant

[Ben314]

Salut,
J'ai peu être un début d'idée de preuve....
Je pense qu'étant donné un polyêdre P de R^n, il existe une partition finie de R^n en polyèdres convexes (éventuellements non bornés) tel que, sur chacun d'eux, la fonction d(M,P) (distance de M à P) est de la forme où A est un point de P et q une forme quadratique positive (en général dégénérée).
Lorsque l'on a plusieurs polyèdres au départ, la fonction somme des distances s'exprime donc, sur chaque élément d'une partition de R^n en polyèdres convexes, comme une somme de .
Si on considère une des parties X de la partition et si cette partie contient deux point M1 et M2 qui minimisent, tu as déja montré que tout le segment minimise (et je te fait confiance, je n'ais pas vérifié).
Je pense que, vu la tête de la formule, on peut en déduire que la fonction reste constante sur la droite (M1M2) (ou plutôt sur l'intersection de (M1M2) avec X, vu que la formule n'est valable que sur X).
Si c'est vrai, l'intersection de l'ensemble des points qui minimise avec X serait bien un polyédre (en fait se serait l'intersection de X avec un sous espace affine) et je pense qu'on en déduit bien que l'ensemble des points qui minimisent est un polyèdre.

Tout cela demande bien sûr à être mis en forme et VERIFIE...