Правление Заде - Zadehs rule - Wikipedia

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

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

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

Алгоритм

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

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

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

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

Суперполиномиальная нижняя граница

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

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

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

Примечания

  1. ^ Заде, Норман (1980). «Каков наихудший случай поведения симплексного алгоритма?». Технический отчет, Департамент операционных исследований, Стэнфорд.
  2. ^ Циглер, Гюнтер (2004). «Типовые и экстремальные линейные программы». Самая резкая резка (серия MPS-Siam по оптимизации.
  3. ^ https://www.ipam.ucla.edu/programs/workshops/efficiency-of-the-simplex-method-quo-vadis-hirsch-conjecture/?tab=schedule
  4. ^ https://gilkalai.wordpress.com/2011/01/20/gunter-ziegler-1000-from-beverly-hills-for-a-math-problem-ipam-remote-blogging