Relâcher les contraintes

J'ai une question de faisabilité qui peut être formulée comme suit. On me donne un point dans un espace vectoriel dimensionnel, et je veux trouver le point le plus proche de qui satisfait un ensemble de " contraintes" de la formed q p ℓ $p$$d$$q$$p$$\ell_0$

Étant donné un ensemble , au plus l'un des peut être différent de zéro.{ q j , j ∈ S $S \in [1\ldots d]$$\{q_j, j \in S\}$

La notion de proximité varie, mais pour l'instant, il suffit de supposer une distance convenable comme .$\ell_2^2$

Existe-t-il des assouplissements connus des contraintes linéaires qui sont "bons" dans le sens de fournir un polytope "assez proche" pour approximer les contraintes d'origine, où je suis également assez flexible sur la définition de "assez proche"

Je ne sais pas si je comprends bien le problème, mais comme il est écrit, le problème semble admettre plusieurs simplifications, et en particulier le problème dans le cas ℓ ₂ ² est équivalent à la couverture de sommet de poids minimum si je ne me trompe pas.

1. Sans perte de généralité, nous pouvons supposer que | S | = 2 dans chaque contrainte, car une contrainte avec | S |> 2 est équivalente à l'ensemble des contraintes où S passe sur toutes les paires d'éléments dans l'ensemble d' origine S . Par conséquent, les contraintes ℓ ₀ peuvent être visualisées comme un graphe G avec d sommets. Utilisation du graphe G , les contraintes peuvent être retraitées de la manière suivante: l'ensemble des sommets correspondant aux coordonnées i avec q _i = 0 doit être un couvercle de sommet de G .
2. Supposons que la distance soit définie par ℓ ₂ ² ou une norme. Dans ce cas, tout point q peut être transformé en un point q ′ satisfaisant pour tout i , q ′ _i ∈ {0, p _i }, simplement en définissant et cette transformation n'augmente jamais la distance du point p . En particulier, si la distance est la somme de la distance en coordonnées (comme dans le cas de la distance ℓ ₂ ² ), le problème est exactement le même que la couverture de sommet de poids minimum. $$q'_i = \begin{cases} p_i, & q_i \ne 0, \\ 0, & q_i = 0, \end{cases}$$

Quant à la relaxation LP du problème de la couverture des sommets, une recherche rapide conduit par exemple aux notes de cours (leçon 9) d'Uriel Feige .