Для конкретности рассмотрим LP для решения игры с нулевой суммой для двух игроков, где у каждого игрока есть действий. Предположим, что каждая запись матрицы выплат имеет самое большее 1 в абсолютном значении. Для простоты давайте не будем делать предположений об ограниченности.
Предположим, что время выполнения доступно для приблизительного значения этой игры.
Одним из методов аппроксимации этого значения является метод мультипликативного обновления (известный в этом контексте как беспроигрышное обучение). Это дает ошибку , где скрывает логарифмические коэффициенты.
Я не знаю точно, как выглядит ландшафт ошибок для самого известного метода внутренней точки, но я предполагаю, что ошибка - что-то вроде .
Мультипликативные методы обновлений дают ошибку , что и обратный многочлен . Методы точечных Межкомнатные дают ошибку , которая экспоненциально мала по . Следовательно, ошибка лучшего из двух медленно снижается на некоторое время, пока внутренняя точка не догонит ее, после чего ошибка внезапно упадет с обрыва. Мои инстинкты против лучших компромиссов времени / ошибки, ведущих себя таким образом.
Мой вопрос :
Существует ли алгоритм приближенного линейного программирования, который сглаживает угол кривой компромисса времени / ошибки? То есть алгоритм, который выполняет как минимум лучшее из двух значений для любого доступного параметра времени и имеет относительно плавный компромисс между временем и ошибкой. Более разумный способ объединить внутренние и мультипликативные методы обновления, чем использовать лучшее из двух, является одним из вероятных способов получить такой алгоритм.
Рекомендации :
Мультипликативное обновление в целом:
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.