Jakie są najlepsze możliwe kompromisy czas / błąd dla przybliżonego rozwiązania programów liniowych?

Dla konkretności rozważ LP za rozwiązanie gry dla dwóch graczy o sumie zerowej, w której każdy gracz ma akcji. Załóżmy, że każdy zapis macierzy wypłat ma najwyżej 1 wartość bezwzględną. Dla uproszczenia nie róbmy żadnych założeń sparity.$n$$A$

Załóżmy, że środowisko wykonawcze jest dostępne w celu przybliżenia wartości tej gry.$T$

Jedną z technik przybliżania tej wartości jest metoda aktualizacji multiplikatywnej (w tym kontekście znana jako uczenie się bez żalu). Daje to błąd , gdzie ukrywa współczynniki dziennika.$\tilde O(\sqrt{n/T})$$\tilde O$

Nie wiem dokładnie, jak wygląda krajobraz błędów dla najbardziej znanej metody punktu wewnętrznego, ale domyślam się, że błąd jest podobny do $O(\exp(-T/n^3))$ .

Multyplikatywnej metody aktualizacji dać błąd, który jest odwrotna wielomian w $T$ . Metody punktowe wewnętrzne dają błąd, który znajduje się w postępie geometrycznym małe $T$ . Błąd najlepszego z nich z tego powodu powoli maleje, dopóki wewnętrzny punkt nie nadejdzie, po czym błąd nagle spadnie z klifu. Moje instynkty sprzeciwiają się najlepszym możliwym kompromisom czas / błąd, zachowując się w ten sposób.

Moje pytanie :

Czy istnieje algorytm przybliżonego programowania liniowego, który wygładza narożnik krzywej kompromisu czas / błąd? To znaczy, algorytm, który działa co najmniej tak dobrze, jak oba najlepsze dla dowolnej wartości dostępnego parametru czasu i ma względnie płynny kompromis czas / błąd. Bardziej inteligentnym sposobem na połączenie technik aktualizacji wewnętrznej i multiplikatywnej aktualizacji niż wykorzystanie tych dwóch metod jest jednym z prawdopodobnych sposobów uzyskania takiego algorytmu.

Referencje :

Aktualizacja multiplikatywna ogólnie:

http://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf

Aktualizacja multiplikatywna dla gier o sumie zerowej:

http://dx.doi.org/10.1016/0167-6377(95)00032-0

Aktualizacja wielokrotna obejmująca / pakująca płyty LP:

http://arxiv.org/PS_cache/arxiv/pdf/0801/0801.1987v1.pdf

Oryginalny papier punktu wewnętrznego:

http://math.stanford.edu/~lekheng/courses/302/classics/karmarkar.pdf

Punkt wewnętrzny z zastosowanej perspektywy matematycznej:

Programowanie nieliniowe Bertsekasa , sekcja 4.1.1.

Być może to odniesienie będzie odpowiednie dla twojego pytania.

Grigoriadis M., Khachiyan L. Podliniowy algorytm losowego przybliżenia do gier matrycowych // Oper. Res. Łotysz. 1995. V. 18. nr 2. str. 53-58.

Algorytm w nim jest 1) losowy 2) błąd jest DODATKOWY, ale 3) jest sublinearny (musisz sprawdzić tylko niewielką część danych wejściowych, aby znaleźć solutiom z dużym prawdopodobieństwem).

Siergiej