Каковы наилучшие возможные временные / ошибочные компромиссы для приближенного решения линейных программ?

19

Для конкретности рассмотрим LP для решения игры с нулевой суммой для двух игроков, где у каждого игрока есть действий. Предположим, что каждая запись матрицы выплат имеет самое большее 1 в абсолютном значении. Для простоты давайте не будем делать предположений об ограниченности.nA

Предположим, что время выполнения доступно для приблизительного значения этой игры.T

Одним из методов аппроксимации этого значения является метод мультипликативного обновления (известный в этом контексте как беспроигрышное обучение). Это дает ошибку , где скрывает логарифмические коэффициенты.O~(n/T)O~

Я не знаю точно, как выглядит ландшафт ошибок для самого известного метода внутренней точки, но я предполагаю, что ошибка - что-то вроде .O(exp(T/n3))

Мультипликативные методы обновлений дают ошибку , что и обратный многочлен . Методы точечных Межкомнатные дают ошибку , которая экспоненциально мала по . Следовательно, ошибка лучшего из двух медленно снижается на некоторое время, пока внутренняя точка не догонит ее, после чего ошибка внезапно упадет с обрыва. Мои инстинкты против лучших компромиссов времени / ошибки, ведущих себя таким образом.TT

Мой вопрос :

Существует ли алгоритм приближенного линейного программирования, который сглаживает угол кривой компромисса времени / ошибки? То есть алгоритм, который выполняет как минимум лучшее из двух значений для любого доступного параметра времени и имеет относительно плавный компромисс между временем и ошибкой. Более разумный способ объединить внутренние и мультипликативные методы обновления, чем использовать лучшее из двух, является одним из вероятных способов получить такой алгоритм.

Рекомендации :

Мультипликативное обновление в целом:

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

Мультипликативное обновление для игр с нулевой суммой:

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

Мультипликативное обновление для покрытия / упаковки пластинок:

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

Оригинальная бумага для интерьера:

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

Внутренняя точка с точки зрения прикладной математики:

Нелинейное программирование Берцекаса , раздел 4.1.1.

Уоррен Шуди
источник

Ответы:

2

Возможно, эта ссылка будет иметь отношение к вашему вопросу.

Григориадис М., Хачиян Л. Сублинейный алгоритм рандомизированного приближения к матричным играм // Опер. Местожительство Lett. 1995. Т. 18. № 2. С. 53-58.

Алгоритм в этом случае: 1) рандомизированный, 2) ошибка ДОБАВЛЯЮЩАЯ, но 3) является сублинейной (вам нужно проверить только небольшую часть входных данных, чтобы найти решение с высокой вероятностью).

Сергей

Сергей
источник
Действительно, эта статья весьма актуальна. Это вторая ссылка, приведенная в разделе ссылок моего вопроса.
Уоррен Шуди
Пардон. Я упустил из виду, что ссылка уже существует. Таким образом, мой комментарий должен быть удален или расценен как обзор одного из текстов в вашем списке. Некоторые дополнительные результаты того же характера, но с использованием более общей структуры, можно найти в Юдицком А., Лане, Г., Немировском, А., Шапиро, А. Подход стохастической аппроксимации к стохастическому программированию - SIAM Journal on Optimization 19: 4 (2009), 1574-1609. Сергей
Сергей