Оценка скорости сходимости симплексного алгоритма

[Andrey_Kireew]

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

Я исходил из представлений, что сложность алгоритма определяется количеством вершин многогранника для конкретной задачи оптимизации (это произведение числа ограничений на количество переменных). Число итераций должно зависеть от этой величины экспоненциально - в худшем случае, полиномиально - в лучшем и субэкспоненциально - в среднем.
Но результаты практических вычислений, с этими представлениями, мягко говоря не согласуются. Всё время наблюдается почти линейная зависимость числа итераций от числа ограничений, для разных алгоритмом различается лишь коэффициент наклона линии. Зависимость от числа переменных более сложная и определяется конкретным алгоритмом, но всё равно, никакого экспоненциального роста не наблюдается.

Есть ли какая нибудь полезная информация по этому вопросу?

[Xaositect]

Это известный вопрос в теории сложности.
В худшем случае симплекс-метод экспоненциален, то есть есть "плохие" задачи линейного программирования сколь угодно большого размера, на которых количество итераций экспоненциально.
Но тем не менее множество этих плохих задач очень узкое, и на практике такое происходит очень редко. ФОрмализовать это можно по-разному, есть много работ о том, что в среднем для разных вероятностных распределений матриц задачи симплекс-метод полиномиален. Есть работа Шпильмана и Тенга (за которую они получили Геделевскую премию), где они доказали, что если взять произвольную задачу линейного программирования и дать ее коэффициентам случайное возмущение (с нормальным распределением), то в среднем время работы одного из вариантов симплекс-метода полиномиально зависит от размера задачи и относительной дисперсии возмущения. Почитать можно тут: https://arxiv.org/abs/cs/0111050.

[vpb]

Добавлю, что первым то, что симплекс метод, "как правило", имеет полиномиальную сложность, установил Смейл. Больше ничего по вопросу не знаю.

[Andrey_Kireew]

Спасибо Xaositect, сейчас почитаю.
Ещё один момент - везде пишут о полиномиальном времени, но не о числе итераций. Это плохо, т.к. время зависит от трудоёмкости одной итерации, а она - от размера задачи. На мой взгляд, это вносит путаницу, ведь трудоёмкость итерации можно оценить точно (она обычно квадратичная), а кол-во итераций - нельзя.
Лично у меня получается, что количество итераций примерно линейно зависит от размера задачи, но из-за квадратичной сложности итерации, общая трудоёмкость получается кубическая.