Полином
удовлетворяющий системе линейных неравенств (8.6), задает "направление спуска" из "точки"
для уклонения
Направление спуска будет в определенном смысле наилучшим, если
выбирается по следующему, более сложному в сравнение с (8.6), правилу
Задача (8.9) есть задача линейного программирования, но с меньшим, нежели (8.5), числом неравенств. Итак, усложненный алгоритм спуска [38] состоит в последовательном выполнении шагов: если на
шаге построен полином
то на следующем,
шаге решается сначала задача (8.9), затем задача (8.7) и полагается
Если задача (8.9), а значит, и (8.6), не имеют решения, то выполняется неравенство (8.8) и процесс заканчивается на
шаге. Заметим, что уменьшая
мы сокращаем количество неравенств в (8.9), но число шагов при этом, вероятно, увеличится.
Этот алгоритм оказался наиболее эффективным при решении прикладных задач.