Relajante

Tengo una pregunta de viabilidad que se puede enmarcar de la siguiente manera. Me dan un punto en un d espacio vectorial dimensional, y yo quiero encontrar el punto más cercano q a p que satisface un conjunto de " l 0 limitaciones" de la forma$p$$d$$q$$p$$\ell_0$

Dado un conjunto , como máximo uno de { q j , j ∈ S } puede ser distinto de cero.$S \in [1\ldots d]$$\{q_j, j \in S\}$

La noción de cercanía varía, pero por ahora es suficiente asumir una distancia conveniente como .$\ell_2^2$

¿Hay alguna relajación conocida de las restricciones lineales que sean "buenas" en el sentido de proporcionar un politopo "lo suficientemente cerca" para aproximar las restricciones originales, donde también soy bastante flexible en la definición de "lo suficientemente cerca"

No estoy seguro si entiendo el problema correctamente, pero como está escrito, el problema parece admitir varias simplificaciones, y en particular el problema en el caso ℓ ₂ ² es equivalente a la cubierta de vértice de peso mínimo si no me equivoco.

1. Sin pérdida de generalidad podemos suponer que | S | = 2 en cada restricción, porque una restricción con | S |> 2 es equivalente al conjunto de restricciones, donde S se ejecuta sobre todo par de elementos en el conjunto original S . Por lo tanto, las restricciones ℓ ₀ se pueden visualizar como un gráfico G con d vértices. Usando el gráfico G , las restricciones pueden ser actualizados como sigue: el conjunto de los vértices correspondientes a las coordenadas i con q _i = 0 debe ser una cubierta vértice de G .
2. $$q'_i = \begin{cases} p_i, & q_i \ne 0, \\ 0, & q_i = 0, \end{cases}$$ . En particular, si la distancia es la suma de la distancia coordinada (como en el caso de la distancia ℓ ₂ ² ), el problema es exactamente el mismo que el de la cubierta de vértice de peso mínimo.

En cuanto a una relajación LP del problema de la cubierta del vértice, una búsqueda rápida conduce, por ejemplo, a las notas de clase (Clase 9) de Uriel Feige .