Правило Заде́ (также известное как правило меньшего использования) — алгоритмическое улучшение симплекс-метода для линейной оптимизации.
Правило было предложено в 1980-х годах и с тех пор широко используется в выпуклой оптимизации.
Заде объявил о награде в размере $1000 любому, кто сможет показать, что правило приводит к полиномиальному числу итераций, либо доказать существование семейства задач линейного программирования, для которых это правило ввода переменных в базис требует субэкспоненциального числа шагов для нахождения оптимума.
Алгоритм Правило Заде относится к семейству исторически обусловленных правил улучшения, которые при работе симплекс-метода используют дополнительные данные помимо текущего базиса.
Суть правила заключается в выборе среди всех переменных, которые могут быть введены в базис, той, которая реже всего попадала в базис. Это позволяет учитывать переменные, которые на отдельных шагах дают небольшое улучшение, но в долгосрочной перспективе могут существенно улучшить решение.
Дополнительная структура данных алгоритма представляет собой учет числа вхождений: каждой переменной сопоставляется целое число, показывающее, сколько раз она попадала в базис. На каждой итерации выбирается переменная, имеющая минимальное значение в этом учете.
Правило не уточняет, какая именно переменная выбирается при равенстве количества вхождений.
Суперполиномиальная нижняя граница Было показано, что правило Заде обладает как минимум суперполиномиальной сложностью в худшем случае. Для этого построено семейство марковских процессов, на которых алгоритм требует суперполиномиального числа шагов.
Результаты были представлены на конференции 2011 года «Целочисленное программирование и комбинаторная оптимизация». Норман Заде, хотя уже не занимался в это время научной деятельностью, присутствовал на конференции и выполнил своё обещание.
Примечания
Литература
Категория:Алгоритмы и методы оптимизации Категория:Линейное программирование