Правило Заде
В математической оптимизации правило Заде (также известное как правило наименьшего количества входов ) представляет собой алгоритмическое усовершенствование симплексного метода линейной оптимизации .
Правило было предложено примерно в 1980 году Норманом Заде (сыном Лотфи А. Заде ) и с тех пор вошло в фольклор выпуклой оптимизации. [ 1 ]
Заде предложил вознаграждение в 1000 долларов тому, кто сможет доказать, что правило допускает полиномиальное количество итераций, или доказать, что существует семейство линейных программ, в которых правило поворота требует субэкспоненциально большого числа итераций для нахождения оптимума. [ 2 ]
Алгоритм
[ редактировать ]Правило Заде принадлежит к семейству правил улучшения на основе истории, которые во время работы симплексного алгоритма сохраняют дополнительные данные в дополнение к текущей основе линейной программы.
В частности, правило выбирает среди всех улучшающих переменных ту, которая реже всего входит в базис, интуитивно гарантируя, что переменные, которые могут привести к существенному улучшению в долгосрочной перспективе, но лишь к небольшому улучшению за один шаг, будут применены после линейного числа шаги.
Таким образом, дополнительную структуру данных в алгоритме Заде можно смоделировать как запись о вхождении, сопоставляя все переменные с натуральными числами и отслеживая, как часто конкретная переменная попадает в базис. Затем на каждой итерации алгоритм выбирает улучшающую переменную, минимальную по отношению к сохраненной записи о вхождении.
Обратите внимание, что в правиле явно не указано, какая именно улучшающая переменная должна войти в базис в случае ничьей.
Суперполиномиальная нижняя граница
[ редактировать ]Было показано, что правило Заде имеет, по крайней мере, суперполиномиальную временную сложность в худшем случае путем построения семейства марковских процессов принятия решений , для которых алгоритм итерации политики требует суперполиномиального числа шагов. [ 3 ] [ 4 ]
Запуск симплексного алгоритма с правилом Заде в индуцированной линейной программе дает суперполиномиальную нижнюю границу.
Результат был представлен на конференции «Эффективность симплекс-метода: гипотеза Хирша Quo vadis?» Семинар IPAM в 2011 году Оливера Фридмана . [ 5 ] Заде, хотя в то время больше не работал в академических кругах, посетил семинар и выполнил свое первоначальное предложение. [ 6 ]
Экспоненциальная нижняя граница
[ редактировать ]Первоначальный результат Фридмана с тех пор был подкреплен построением экспоненциального примера правила Заде. [ 7 ]
Примечания
[ редактировать ]- ^ Заде, Норман (1980). «Каково наихудшее поведение симплексного алгоритма?». Технический отчет, Департамент исследования операций, Стэнфорд .
- ^ Циглер, Гюнтер (2004). «Типичные и экстремальные линейные программы». The Sharpest Cut (Серия MPS-Siam по оптимизации : 217–230. doi : 10.1137/1.9780898718805.ch14 . ISBN 978-0-89871-552-1 .
- ^ Фридманн, Оливер (2011). «Субэкспоненциальная нижняя граница правила поворота Заде для решения линейных программ и игр». Материалы 15-й Международной конференции по целочисленному программированию и комбинаторной оптимизации (IPCO) . стр. 192–206.
- ^ Диссер, Ю.; Хопп, А.В. (2019). «О субэкспоненциальной нижней границе Фридмана для правила поворота Заде». Материалы 20-й конференции по целочисленному программированию и комбинаторной оптимизации (IPCO) . стр. 168–180.
- ^ «Эффективность симплексного метода: гипотеза Quo vadis Хирша?» .
- ^ «Гюнтер Циглер: 1000 долларов из Беверли-Хиллз за математическую задачу. (Удаленный блог IPAM.)» . 20 января 2011 г.
- ^ Диссер, Янн; Фридманн, Оливер; Хопп, Александр В. (2022). «Экспоненциальная нижняя граница правила поворота Заде». Математическое программирование .