Правило Заде́ (также известное как правило меньшего использования) — алгоритмическое улучшение симплекс-метода для линейной оптимизации.

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

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

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

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

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

Правило не уточняет, какая именно переменная выбирается при равенстве количества вхождений.

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

Результаты были представлены на конференции 2011 года «Целочисленное программирование и комбинаторная оптимизация». Норман Заде, хотя уже не занимался в это время научной деятельностью, присутствовал на конференции и выполнил своё обещание.

Примечания

Литература

Категория:Алгоритмы и методы оптимизации Категория:Линейное программирование