Relaks

Mam pytanie wykonalności, które można sformułować w następujący sposób. Ja dany punkt w -wymiarowej przestrzeni wektorowej i chcę, aby znaleźć najbliższy punkt do że spełnia zestaw „ ograniczeń” formularza $p$ $d$ $q$ $p$ $\ell_0$

Biorąc pod uwagę zestaw , co najwyżej jeden z może być niezerowy. $S \in [1\ldots d]$ $\{q_j, j \in S\}$

Pojęcie bliskości jest różne, ale na razie wystarczy przyjąć dogodną odległość, taką jak . $\ell_2^2$

Czy znane są rozluźnienia dla ograniczeń liniowych, które są „dobre” w sensie zapewnienia „wystarczająco bliskiego” polytopu do przybliżenia pierwotnych ograniczeń, gdzie jestem również dość elastyczny w kwestii definicji „wystarczająco blisko”

ds.algorithms approximation-algorithms linear-programming Suresh Venkat
źródło

Czy ograniczenia mogą zależeć nieliniowo od

p

$p$

Warren Schudy,

Czy możesz wyjaśnić, jakiego rodzaju politopu szukasz? Kadłub wypukły dopuszczalnych punktów

punktów z co najwyżej jeden niezerowy współrzędnych

, więc nie ma nadziei na dobrą poliedrycznego zbliżenia zestawu możliwych

punktów.

q

$q$

R^{d}

$\mathcal{R}^d$

q

$q$

Warren Schudy,

Jeśli

jest stałą znane z wyprzedzeniem, a następnie dla każdej stałej odległości

można łatwo obliczyć możliwych punktów, które są w zasięgu

(patrząc na jednym tylko ograniczeniem). W przypadku niektórych wskaźników wykonalnym punktem będzie połączenie polytopów; dla innych może być konieczne ich zbliżenie lub użycie wyroczni separacyjnej. Następnie napisz wiązania liniowe kodujące, że

znajduje się w ich wypukłym kadłubie.

p

$p$

δ

$\delta$

δ

$\delta$

p

$p$

q

$q$

Warren Schudy,

@ warren: ograniczenia zależą liniowo od p, ale samo p nie jest stałą (raczej jest wkładem do problemu). Ograniczenia są powyższego rodzaju lub są liniowe na q_i.

Suresh Venkat

Odpowiedzi:

Nie jestem pewien, czy dobrze rozumiem problem, ale jak napisano, wydaje się, że problem dopuszcza kilka uproszczeń, aw szczególności problem w przypadku ℓ ₂² jest równoważny z pokrywą wierzchołków o minimalnej wadze, jeśli się nie mylę.

Bez utraty ogólności możemy założyć, że | S | = 2 w każdym wiązaniu, ponieważ wiązanie z | S |> 2 jest odpowiednikiem zestawu ograniczeń, gdzie S pracuje nad całą parę elementów w oryginalny zestaw S . Dlatego wiązania ℓ ₀ mogą być wizualizowane jako wykres G z d wierzchołkami. Korzystając z wykresu G , te ograniczenia mogą być przekształcone w sposób następujący: zbiór wierzchołków odpowiadające współrzędne ı z q _i = 0 może być pokrywa wierzchołek G .
$q_{i}^{'} = {\begin{cases} p_{i}, & q_{i} \neq 0, \\ 0, & q_{i} = 0, \end{cases}$ $q'_i = \begin{cases} p_i, & q_i \ne 0, \\ 0, & q_i = 0, \end{cases}$ . W szczególności, jeśli odległość jest sumą odległości współrzędnych (jak w przypadku odległości ℓ ₂² ), problem jest dokładnie taki sam jak pokrycie wierzchołka o minimalnej masie.

Jeśli chodzi o relaksację LP problemu pokrycia wierzchołka, szybkie wyszukiwanie prowadzi np. Do notatek z wykładu (Wykład 9) Uriela Feige .

Tsuyoshi Ito
źródło

Dość interesujące. Podoba mi się obserwacja na temat | S | nie musi być więcej niż 2

Suresh Venkat

Jest jedna rzecz, która nie do końca działa. Zmienne na ogół mogą być dowolne (nie pomiędzy zero a jeden). Tak więc nie można tak naprawdę zakodować ograniczeń LP dla „zmiennych ustawionych na zero musi tworzyć osłonę wierzchołków”. Staje się to problemem (o czym powinienem wspomnieć), ponieważ istnieją inne (liniowe) ograniczenia na współrzędnych, które również muszą zostać uwzględnione.

Suresh Venkat

@Suresh: Jeśli naprawdę uważasz, że o tym wspomniałeś, zawsze możesz zmodyfikować pytanie.

Tsuyoshi Ito,

@Suresh: Chciałem powiedzieć „Jeśli naprawdę uważasz, że powinieneś o tym wspomnieć…”.

Tsuyoshi Ito