Правило Заде

В математической оптимизации, правила Зада (также известные как наименее введенное правило ) является алгоритмическим уточнением симплекса - методы для линейной оптимизации.

Правило было предложено около 1980 года Норманом Заде (сыном Лотфи А. Заде ) и с тех пор вошло в фольклор выпуклой оптимизации.

Заде предложил вознаграждение в размере 1000 долларов каждому, кто сможет показать, что правило допускает полиномиально много итераций, или доказать, что существует семейство линейных программ, для которых правило поворота требует субэкспоненциального количества итераций, чтобы найти оптимум.

Правило Заде принадлежит к семейству правил улучшения на основе истории, которые во время выполнения симплексного алгоритма сохраняют дополнительные данные в дополнение к текущему основанию линейной программы.

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

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

Обратите внимание, что правило не указывает явно, какая конкретная улучшающая переменная должна входить в основу в случае ничьей.

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

Выполнение симплексного алгоритма с правилом Заде для индуцированной линейной программы затем дает суперполиномиальную нижнюю границу.

Результат был представлен на конференции "Эффективность симплексного метода: Quo vadis Hirsch?" Семинар по IPAM в 2011 году Оливер Фридманн. Заде, хотя в то время больше не работал в академических кругах, посетил семинар и выполнил свое первоначальное предложение.