Rozwiązania punktu środkowego dla programów liniowych

Istnieje program liniowy, dla którego chcę nie tylko rozwiązania, ale rozwiązania, które jest tak centralne, jak to możliwe na powierzchni polytopa, który przyjmuje minimalną wartość.

Z góry oczekujemy, że minimalizująca powierzchnia powinna być wielowymiarowa z różnych powodów, w tym, że minimalizowana funkcja celu jest maksimum z wielu ograniczeń:

Zminimalizować $\epsilon$ z zastrzeżeniem $f_i(\bar x) \leq \epsilon < 0$ z $f_i$ liniowy i $x_i > 0$ dla wszystkich $i$ i $\sum_i x_i = 1$ .

Oczywiście nigdy nie uzyskalibyśmy żadnej właściwości centralnej z algorytmu simpleks. Czy którykolwiek ze zwykłych algorytmów punktu wewnętrznego wykazuje takie właściwości? Czy ktoś w ogóle gwarantuje, że w miarę możliwości uniknie wierzchołków lub ścian o niższych wymiarach?

W rzeczywistości jestem pewnie zadowolony z łatwego programu kwadratowego, który znajduje punkt środkowy całego polytopa, ponieważ centralność ma znaczenie większe niż minimalność, po prostu niejasne, czy inne algorytmy programowania liniowego oferują odpowiednie właściwości.

Aktualizacja: zredukowałem podstawowy problem do prostego problemu ograniczonej minimalizacji, który można rozwiązać za pomocą mnożników Lagrange'a, ale powyższe pytanie i tak pozostaje interesujące.

ds.algorithms linear-algebra linear-programming

— Jeff Burdges
źródło

nie do końca twoje pytanie, ale: obliczenie centroida jest trudne; nie jestem pewien, jakie jest najlepsze przybliżenie, ale dla niektórych zastosowań wystarczy ustawienie wielopłaszczyzny w pozycji izotropowej i pobranie średniej z wielomianu wielu jednorodnych próbek z (transformowanego) polytopa. patrz te uwagi, na przykład Lemma 15: cc.gatech.edu/~vempala/acg/notes.pdf

— Sasho Nikolov

czy to bardziej teoretyczne czy praktyczne pytanie? być może byłoby możliwe wygenerowanie wszystkich wierzchołków optymalnej powierzchni, a następnie użycie ich odpowiedniej wypukłej kombinacji.

— anonimowy

Odpowiedzi:

Mam kilka uwag, które są zbyt długie na komentarze. Oto podsumowanie.

Każdy algorytm, który dokładnie rozwiązuje twój problem, może być użyty do dokładnego rozwiązania programów liniowych (tj. „Silne programowanie liniowe”, które jest stosowane w rozwiązaniu Sariela i obecnie nie ma algorytmu wielomianowego czasu).
Naturalną kontynuacją jest, jeśli przybliżone rozwiązania (tj. „Słabe programowanie liniowe”) mogą zapewnić rozwiązanie. Chociaż odpowiedź brzmi „tak”, wydaje się, że warunek zatrzymania tej procedury wymaga wielkości, które według mojej najlepszej wiedzy nie mogą być obliczone w czasie wielomianowym. (tzn. algorytm znajduje coś dobrego, ale poświadczenie tego jest trudne.) Moją główną sugestią tutaj jest stworzenie sensownej definicji „ $\epsilon$ -optymalne rozwiązanie ”dla twojego problemu, w którym to przypadku takie podejście jest wykonalne. (Strategia ta skutecznie wyrzuca małe powierzchnie wielościanu).

Ogólnie rzecz biorąc, zastanawiając się nad twoim obecnym stwierdzeniem problemu, ciągle zastanawiałem się nad wydajnością. Ale jest w tym rozsądna intuicja: przedmioty, które rzucamy - wierzchołki, twarze itp. - są dyskretne i wykładniczo obfite.

(1.) Załóżmy, że mamy algorytm, który dokładnie rozwiązuje twój problem. Zauważ, że każdy odsłonięty punkt dowolnej powierzchni zawierającej podany punkt środkowy będzie dokładnym rozwiązaniem oryginalnego programu liniowego. Postępuj więc w następujący sposób. Dodaj nowe ograniczenie liniowe, mówiąc, że pierwotna wartość celu musi być równa wartości optymalnej (którą obecnie znamy), i ustaw nowy cel, mówiąc, aby zmaksymalizować pierwszą współrzędną rozwiązania. Powtórz tę procedurę jeden raz dla każdego wymiaru, za każdym razem dodając ograniczenie i wybierając nową współrzędną, aby zmaksymalizować. Ten proces za każdym razem zmniejszy wymiar rozwiązania; koniecznie, kiedy proces się zakończy, mamy 0-wymiarowy zestaw afiniczny, co oznacza pojedynczy punkt. Tak więc z $\mathcal O(d)$ iteracje algorytmu rozwiązywania punktu środkowego (i tylko zwiększając opis problemu o wielkość wielomianową w $d$ za każdym razem), silne programowanie liniowe jest rozwiązywane. To pokazuje, że chociaż rozwiązanie Sariela wymaga silnego programowania liniowego, dokładne rozwiązanie twojego pytania nie może tego uniknąć. ( Edycja : zwróć uwagę, że mój dowód zakłada na wejściu zwarty wielościan (polytop); w przeciwnym razie będzie musiał nieco ciężej pracować, aby znaleźć wierzchołki.)

(2.) Oto schemat iteracyjny, wykorzystujący w pełni wypukły solver wypukły w każdej iteracji, którego rozwiązania będą zbieżne do łagodnego pojęcia rozwiązania punktu środkowego. Wybierz pozytywną, ale malejącą sekwencję parametrów kary $\{\lambda_i\}_{i=1}^\infty\downarrow 0$ ; uzasadnione jest, aby spadały one geometrycznie, tj $\lambda_i = 2^{-i}$ . Teraz dla każdego $i$ , w przybliżeniu zminimalizuj funkcję wypukłą

⟨ c, x ⟩ - λ_{i} \sum_{j = 1}^{m} \ln (⟨ a_{j}, x ⟩ - b),

$\langle c,x\rangle - \lambda_i\sum_{j=1}^m \ln(\langle a_j,x\rangle - b),$

gdzie $\langle c,x\rangle$ jest twoim pierwotnym celem, oraz $j$ zakresy ponad $m$ oryginalne ograniczenia, teraz umieszczone w celu poprzez bariery logarytmiczne (uwaga, jest to standard). Teraz, jeśli myślimy o minimalizującej powierzchni (największego wymiaru) waszego wielościanu, zauważcie, że dla wystarczająco małej $\lambda_i$ i tolerancja $\tau$ do wypukłej czarnej skrzynki optycznej, twoje przybliżone optymalne będzie blisko tej twarzy, jednak bariery odepchną ją jak najdalej od innych ograniczeń. Powiedział inny sposób, jak $\lambda_i$ zmniejsza się, pierwotny cel liniowy ostatecznie zdominuje niektóre wybredne bariery, które utrzymywały cię przed właściwą twarzą, ale nie wpłyną na bariery, które utrzymują cię z innych granic, w szczególności granic twarzy docelowej.

W idealnym świecie usiądziemy i analitycznie ustalimy idealną wartość $\lambda$ lub przynajmniej czas zatrzymania, abyś nie musiał rozwiązywać, no cóż, nieskończenie wielu problemów. Niestety wydaje się to trudne. Jednym z pomysłów jest, powiedzmy, określenie najmniejszej szerokości dowolnej powierzchni mającej wymiar większy niż 0; jest to dobrze zdefiniowany problem minimalizacji z dodatnim optimum, ponieważ istnieje ostatecznie wiele powierzchni (i szerokość jest obliczana względem każdej z nich). Dzięki temu możemy ustawić $\lambda$ wystarczająco mały, aby wpływ barier był niewielki w środku każdej twarzy. Niestety może być wykładniczo wiele twarzy, więc obliczenie tej liczby jest nonsensem.

Wszystkie warunki zatrzymania, jakie mogłem wymyślić, miały tego rodzaju trudności obliczeniowe. (Co więcej, wielu można ponownie wykorzystać do przekształcenia tego w silny liniowy program do rozwiązywania problemów).

Z tego powodu zalecam zbudowanie pojęcia `` $\epsilon$ -zamknij optymalny punkt środkowy '' i rozwiąż go, wybierając $\lambda$ i tolerancję wypukłej czarnej skrzynki $\tau$ odpowiednio. Myślę, że jest to rozsądny wybór, ponieważ możesz naprawdę nie przejmować się twarzami o największej szerokości $\epsilon$ .

(Kilka uwag końcowych.) Wydaje się, że kluczowe znaczenie ma pojęcie „punktu środkowego”; Komentarz Sasho wskazuje, że środek ciężkości (środek masy?) Jest niezwykle trudnym problemem, podczas gdy znalezienie, powiedzmy, największej wpisanej piłki jest łatwe. Bariery logarytmiczne, które zasugerowałem powyżej, na ogół nie będą spójne z żadnym z tych pojęć punktu środkowego. Z drugiej strony, dla barier i piłki, możesz wyznaczyć dolną granicę odległości od twojego środka ciężkości do względnej granicy twarzy; może to jest dla ciebie bardziej przydatne?

Wreszcie, na podstawie twojego opisu, uważam, że miałeś na myśli, że „twarz docelowa” ma mieć możliwie największy wymiar? Jest to dobrze zdefiniowane, jednak istnieją również powierzchnie rozwiązania dla wszystkich możliwych mniejszych wymiarów. W każdym razie zarówno podejście Sariela, jak i podejście barierowe powyżej będą działać z twarzą o największym wymiarze.

— matus
źródło

Tak, rozważałem takie sztuczki, ale ostatecznie zdecydowałem się na minimalizację

\sum_{i} f_{i} (x)^{2} + \sum_{j} x_{j}^{2}

$\sum_i f_i(x)^2 + \sum_j x_j^2$ z zastrzeżeniem

\sum_{j} x_{j} = 1

$\sum_j x_j = 1$ za pomocą mnożników Lagrange'a. Daje słabą właściwość centralności

x

$x$ na przekątnej, która może nie być powierzchnią minimalizującą, ale z pewnością jest jedną z powierzchni ograniczających, która nigdy się nie porusza. Po prostu uruchamiam osobny program liniowy, gdy przestaną ewoluować przeciwności i rzeczywiście potrzebuję prawdziwego minimum

ϵ

$\epsilon$ . Ostatecznie nie było takiej potrzeby

ϵ

$\epsilon$ zminimalizowane, aby ograniczenia ewoluowały szybciej. W każdym razie dzięki! :)

— Jeff Burdges

Ahh # 2 wygląda interesująco, a nie to, co początkowo myślałem. uroczy! Jak powiedziałem, wybaczam

x

$x$ za to, że nie ląduje na twarzy minimalizującej, o ile szybko trafi w rozsądne miejsce. Będę z tym kiedyś grał. W rzeczywistości i tak będę musiał przeczytać o optymalizacji wypukłej, ponieważ znalazłem powód, aby uczynić mój cel dwuliniowym zamiast liniowym.

— Jeff Burdges

Nie rozumiem sensu „silnego programowania liniowego” i nigdy wcześniej nie słyszałem tego wyrażenia. nie wiadomo, jak rozwiązać LP w silnym czasie wielomianowym. ale rozwiązywanie LP w czasie wielomianu w opisie wejściowym (tj. słaby czas wielomianu) jest oczywiście dobrze znane. jeśli OP chce, aby algorytm działał w słabym czasie wielomianowym, to rozwiązanie Sariela + algorytm wielopunktowego punktu wewnętrznego wykona zadanie, prawda?

— Sasho Nikolov,

@SashoNikolov, oto moje obecne zrozumienie. Wszelkie istniejące solwery (słabe czasy wieloczasowe) przyjmą tolerancję

τ

$\tau$ jako dane wejściowe i zwróć a

τ

$\tau$ -optymalne rozwiązanie. Tymczasem rozwiązanie Sariela zależy przede wszystkim od dokładnego rozwiązania: w szczególności metoda punktu wewnętrznego zwróci względnie wewnętrzne optymalne przybliżenie, co oznacza, że etap identyfikacji afinicznego kadłuba pożądanej optymalnej powierzchni faktycznie wybierze kadłub całego wykonalnego zestaw. Zgadzam się, że powinienem zrewidować to, co napisałem o silnym / słabym, gdzie kluczową kwestią jest naprawdę uzyskanie dokładnych rozwiązań w jakikolwiek sposób.

— matus

@SashoNikolov, teraz, gdy o tym myślę, to samo pojęcie optymalizacyjne (z tymi samymi problemami) może zostać zastosowane w rozwiązaniu Sariela, na przykład przez traktowanie ograniczeń, które mieszczą się w niewielkiej tolerancji, aby być ścisłym, i odpowiednie dostosowanie tej wartości. Zaktualizuję dziś moje rozwiązanie.

— matus

Najpierw znajdź optymalne rozwiązanie, a następnie dodaj ograniczenie liniowe, że rozwiązanie musi mieć wartość równą optymalnemu, czego chcesz, i ponownie sformatuj swój LP jako ten, który szuka największej piłki w wykonalnym obszarze. Rozwiąż ten zmodernizowany LP i masz to, czego chcesz.

Dlaczego drugi problem można rozwiązać za pomocą LP jest niezmiernie uroczym problemem w geometrii obliczeniowej ...

==============

Bardziej formalnie znajdziesz afiniczną podprzestrzeń obejmującą wykonalne punkty zawierające optymalne rozwiązanie. Załóżmy, że optymalne rozwiązanie leży na hiperpłaszczyźnie $h \equiv cx = \alpha$ (to znaczy, $\min c x$ była oryginalną funkcją docelową LP). Gdyby $P$ jest wykonalnym regionem oryginalnego LP, szukamy największej piłki $P \cap h$ . W tym celu musimy obliczyć najmniejszą wymiarową podprzestrzeń afiniczną zawierającą ten zestaw. Po znalezieniu tej podprzestrzeni zmień zmienne, aby uwzględnić tylko ten podzbiór afiniczny. Teraz twój polytop jest w pełni dimenisonalny i możesz użyć drugiego LP, jak opisano powyżej.

Więc pozwól $v$ być wierzchołkiem obliczonym przez pierwszy LP. Biorąc pod uwagę wszystkie sąsiednie wierzchołki do $v$ . Rozważ afiniczną podprzestrzeń $v$ wraz ze wszystkimi sąsiadami, którzy mają tę samą wartość docelową (tj. $\alpha$ ). Nietrudno zauważyć, że ta afiniczna podprzestrzeń jest pożądaną podprzestrzenią.

Tak więc, aby przejść na lato: (A) rozwiąż LP, aby odkryć optymalną wartość. (B) Oblicz najmniejszą podprzestrzeń wymiarową zawierającą wykonalne rozwiązanie o optymalnej wartości. (C) Przepisz oryginalny LP w tej afinicznej podprzestrzeni (tzn. Upuszczając wszystkie nieistotne wymiary), dodaj zmienną i zmień go w LP, aby znaleźć największą kulkę w tym polytopie.

— Sariel Har-Peled
źródło

Co oznacza „największa kula” w wielościanie nie w pełnym wymiarze?

— Kristoffer Arnsfelt Hansen

@KristofferArnsfeltHansen wielościan z pewnością jest wypukłym zestawem leżącym w afinicznej podprzestrzeni o pewnym wymiarze.

— Sasho Nikolov

aby to zadziałało, musisz określić ograniczenie ograniczające cię do twarzy, które znalazłeś w pierwszym kroku. Trzeba też wiedzieć, że rozwiązanie było stałe na całej twarzy (prawdopodobnie ujawniłoby to uzupełniające luźność)

— Suresh Venkat,

Czy jest jakiś sposób na wykonanie czynności po wstępnej optymalizacji w czasie wielomianowym? Jak napisano, wydaje się, że wymaga uwzględnienia wszystkich wierzchołków na powierzchni docelowej, których może być wykładniczo wiele.

— Matus

Jest to łatwiejsze - musisz wziąć pod uwagę tylko wierzchołki sąsiadujące z optymalnym wierzchołkiem - są co najwyżej

d

$d$ przylega do niego i można je obliczyć w czasie wielomianowym .... Aby zobaczyć, dlaczego tak jest, rozważ polytop w podprzestrzeni afinicznej - jest on rozproszony przez sąsiadów

v

$v$ które leżą na tej afinicznej podprzestrzeni, ale są one podzbiorem wierzchołków sąsiadujących z v w oryginalnym polytopie. I tak - zajęło mi to trochę czasu, aby to zobaczyć.

— Sariel Har-Peled