Problème d'optimisation avec des matrices

Bonjour je bloque sur un problème et j'aurais besoin d'aide (je ne sais pas vraiment si ce problème s'inscrit dans le domaine de l'analyse).

Imaginons un ensemble de points du plan assez grand $X \in \mathbb{R}^{n \times 2}$ (avec $n=10 000$ par exemple) et un autre ensemble plus petit $Y \in \mathbb{R}^{p \times 2}$ (avec $p=100$ plus petit). On voudrait trouver les $p$ points de $X$ qui sont les plus proches des points de $Y$. On cherche donc à minimiser $\sum_{i \leq p} || (\Pi X)_i - Y_i ||_2^2,\ $ où $\Pi \in \mathbb{R}^{p \times n}$ est une matrice de sélection. Imaginons que $n=5$ , $p=3$ et que la solution est donnée par le 1er, le 4ème et le 5ème point de $X$. Par exemple : $X= \begin{pmatrix}
0.5 & 0.4 \\
1 & 2 \\
1 & 2 \\
-1 & 4 \\
3 & 0.7 \\
\end{pmatrix}\ $ et $\ Y= \begin{pmatrix}
0.49 & 0.39 \\
-1.1 & 3.9 \\
2.9 & 0.71\\
\end{pmatrix},\ $ alors $\ \Pi = \begin{pmatrix}
1 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 1
\end{pmatrix}$

Réponses

  • Bonjour
    Je ne connais pas ce genre de problème et je me demande s'il n'aurait pas sa place dans la rubrique combinatoire et graphe.
    Une solution serait de programmer le calcul pour chaque $\Pi$ possible. Malheureusement le nombre de possibilités est Binomial(n,p) (ou A(n,p)? ) mais de toute façon c'est trop grand.
     
  • Bonjour,

    Donc si je comprends bien, on a $n=10^4$ points marqués $P_i$ dans le plan.

    On cherche à calculer l'application qui à tout point $M$ associe le $i$ tel que $d(M,P_i)$ est minimal. (Diagramme de Voronoi : https://en.wikipedia.org/wiki/Voronoi_diagram )

    Et puis on cherche à le faire efficacement, parce qu'on va répéter $p=100$ fois.

    C'est ça ?
  • Bonjour Marsup merci de ta réponse. Je ne suis pas sûr d'avoir bien compris. On a $n=10e4$ points marqués dans le plan $P_i$ ainsi que $p=100$ autres points $M_j$ marqués dans le plan également. Pour un index $j$ donné on cherche l'index $i$ qui minimise $d(M_i,P_j)$.
Connectez-vous ou Inscrivez-vous pour répondre.