Relaxando

Eu tenho uma pergunta de viabilidade que pode ser estruturada da seguinte maneira. Recebi um ponto em um espaço vetorial dimensional e quero encontrar o ponto mais próximo a que satisfaça um conjunto de " restrições" do formuláriod q p ℓ $p$$d$$q$$p$$\ell_0$

Dado um conjunto , no máximo um de pode ser diferente de zero.{ q j , j ∈ S $S \in [1\ldots d]$$\{q_j, j \in S\}$

A noção de proximidade varia, mas por enquanto é suficiente assumir uma distância conveniente como .$\ell_2^2$

Existe algum relaxamento conhecido das restrições lineares que é "bom" no sentido de fornecer um polítopo "perto o suficiente" para se aproximar das restrições originais, onde também sou bastante flexível na definição de "perto o suficiente"

Não sei se entendi o problema corretamente, mas, como está escrito, o problema parece admitir várias simplificações e, em particular, o problema no caso ℓ ₂ ² é equivalente à cobertura de vértices com peso mínimo, se não me engano.

1. Sem perda de generalidade, podemos assumir que | S | = 2 em cada restrição, porque uma restrição com | S |> 2 é equivalente ao conjunto de restrições, onde S é executado sobre todos os pares de elementos no conjunto original S . Portanto, as restrições ℓ ₀ podem ser visualizadas como um gráfico G com d vértices. Usando o gráfico G , os constrangimentos podem ser reescrita como se segue: o conjunto dos vértices correspondente às coordenadas i com Q _i = 0 deve ser uma cobertura de vértices de L .
2. Suponha que a distância seja definida por ℓ ₂ ² ou alguma norma. Nesse caso, qualquer ponto q pode ser transformado em um ponto q ′ que satisfaça a cada i , q ′ _i ∈ {0, p _i }, simplesmente configurando e essa transformação nunca aumenta a distância do ponto p $$q'_i = \begin{cases} p_i, & q_i \ne 0, \\ 0, & q_i = 0, \end{cases}$$ . Em particular, se a distância é a soma da distância em coordenadas (como no caso da distância ℓ ₂ ² ), o problema é exatamente o mesmo que a cobertura de vértice com peso mínimo.

Quanto ao relaxamento do LP do problema de cobertura de vértices, uma pesquisa rápida leva, por exemplo, às notas da aula (aula 9) de Uriel Feige .