Какова верхняя граница симплексного алгоритма для поиска решения линейной программы?
Как мне найти доказательства для такого случая? Кажется, что наихудший случай - посещение каждой вершины, то есть . Однако на практике симплексный алгоритм будет работать значительно быстрее, чем этот, для более стандартных задач.
Как я могу рассуждать о средней сложности проблемы, решаемой с помощью этого метода?
Любая информация или ссылки с благодарностью!
Ответы:
Симплексный алгоритм действительно посещает все2N вершин в худшем случае ( Klee & Minty 1972 ), и это оказывается верным для любого детерминистического правила поворота. Тем не менее, в историческом документе, использующем сглаженный анализ, Spielman и Teng (2001) доказали, что, когда входные данные алгоритма слегка случайным образом возмущены, ожидаемое время работы симплексного алгоритма является полиномиальным для любых входных данных - это в основном говорит, что для любая проблема есть «рядом», которую симплекс-метод будет эффективно решать, и она в значительной степени охватывает все реальные линейные программы, которые вы хотели бы решить. Впоследствии Келнер и Спилман (2006) представили рандомизированный симплекс-алгоритм за полиномиальное время, который работает на любых входах, даже на плохих для исходного симплекс-алгоритма
источник
Как сказал Лев, в худшем случае алгоритм посещает все2d вершины, где d - количество переменных. Однако производительность симплексного алгоритма также может сильно зависеть от конкретного используемого правила поворота. Насколько мне известно, остается открытым вопрос, существует ли конкретное детерминированное правило поворота с субэкспоненциальным временем наихудшего случая. Многие кандидаты были исключены из нижних оценок результатов. Недавно Фридман, Хансен и Цвик также показали первые неполиномиальные нижние оценки для некоторых естественных рандомизированных правил разворота с некоторыми исправлениями, представленными позже .
Тем не менее, добавив к сглаженному результату анализа, упомянутому Левом: После того, как в оригинальной работе Спилмана и Тенгса был представлен сглаженный анализ, Вершинин еще больше улучшил свои границы в 2006 году. Он показал, что ожидаемое время работы в слегка возмущенных случаях является лишь полилогарифмическим по числу ограниченияN , а не N86 .
источник
Чтобы получить представление о анализе симплексного метода в наихудшем и среднем случае, вы должны прочитать «Сглаженный анализ: почему симплексный алгоритм обычно занимает полиномиальное время». Спилман и Тен.
источник
Хорошая ссылка на то, почему симплекс не работает за полиномиальное время, а не на то, почему он экспоненциальный, - это комбинаторная оптимизация Papadimitriou & Steiglitz, раздел 8.6, в которой они демонстрируют, что Simplex не является алгоритмом полиномиального времени.
источник
Кто-нибудь может предложить другие способы построения сложных задач для симплекс-метода, медленный, но не связанный с памятью?
Добавлено: латинские квадраты или 3d-перестановочные матрицы имеют много вершин - сколько?
Теория и практика ближе в теории, чем на практике.
источник
Оригинальный алгоритм симплекс могут расходиться; это циклы в определенных случаях. Следовательно, нет общей границы. Другие ответы дают вам ответы на различные модификации алгоритма Simplex.
источник