Прямые методы условной оптимизации

Метод Зойтендейка

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

Напомним Определение 2. Рассмотрим задачу минимизации  при условии, что xD Rⁿ, где D- непустое множество. Ненулевой S называется возможным направлением спуска в точке xD, если существует такое , что  и x+SD для всех .

Вначале рассмотрим случай, когда ограничения линейные и задача НП имеет вид:
Минимизировать (10)
при условиях (11)
(12)
где  - матрица порядка ;  - матрица порядка ;
b – m-мерный вектор; k – l-мерный вектор.

Справедливо следующее утверждение.

Лемма 2. Рассмотрим задачу минимизации (10)-(12). Пусть x - допустимая точка и предположим, что , где , а .
Ненулевой вектор S является возможным направлением в точке  в том и только в том случае, если  и . Если, кроме того, f(x)^T·S<0, то S является возможным направлением спуска.
Доказательство этого утверждения очень простое. Предлагаем читателю выполнить это самостоятельно.
Проиллюстрируем геометрически множество возможных направлений спуска на следующем примере.


Пример 1. Минимизировать  при условиях

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

На рис. 1. изображена совокупность этих направлений, образующая конус возможных направлений. Здесь 1 - конус возможных направлений; 2 - конус возможных направлений спуска; 3 - линии уровня целевой функции; 4 - полупространство направлений спуска.
Если вектор S удовлетворяет неравенству , то он является направлением спуска. Таким образом, совокупность возможных направлений спуска определяется открытым полупространством . Пересечение конуса возможных направлений с этим полупространством задает множество всех возможных направлений спуска.