Методы оптимизации и исследование операций для бакалавров информатики. Часть 2

стимой области (как мы знаем, множители Лагранжа есть коэффициенты разложения вектора антиградиента по внешним нормалям активных ограничений). Поэтому мы имеем полное право отправиться внутрь области ограничений. Тем не менее мы этим правом пользоваться не будем, а точно будем следовать алгоритму и пойдем по ребру.

Определим гиперплоскость (в нашем двумерном случае пря-

ветствующее первой строке матрицы Aq , т. е. 3-му ограничению в исходной нумерации.

Удалив из Aq первую строку, получаем матрицу из одной строки Aq−1 = (0, −1), таким образом мы оставляем только 4-е ограничение и будем проектировать на него антиградиент. Вычислим матрицу проектирования

т. е. мы будем двигаться в положительном направлении по оси абсцисс.

Ш а г 3. По формуле (12.18) определяем моменты пересечения

неактивных ограничений (1-го и 2-го). T1 = 0.5, T2 = ∞ (вектор

→−

d 1 параллелен прямой x2 = 1). Следовательно, предельная длина поиска T = 0.5.

Ша г 4. По формуле (12.20) вычисляем точку оптимума для квадратичной функции сечения, получаем t = 0.5. Следовательно, длина шага на этой итерации t0 = min (T, t ) = 0.5.

Ша г 5. Делаем шаг и приходим в новую точку

1-е и 4-е. Матрица, составленная из строк активного набора:

Действуем по образцу первой итерации. Матрицу проектирования не вычисляем, так как она заведомо нулевая. Определяем множители Лагранжа

План не оптимальный.

Ш а г 2. Опять имеем вариант «В». Из активного набора выводим вторую гиперплоскость (в исходной нумерации она 4-я).

= −→T = (1 1)

Составляем матрицу из одной строки Pq−1 a 1 , и на ее основе вычисляем матрицу проектирования

Ш а г 3. По формуле (12.18) определяем моменты пересечения неактивных ограничений (2-го и 3-го в исходной нумерации). T2 = 1, T3 = 2. Следовательно, предельная длина поиска T = 1

Ш а г 4. По формуле (12.20) вычисляем точку оптимума для квадратичной функции сечения, получаем t = 0.5. Следовательно, длина шага на этой итерации t0 = min (T, t ) = 0.5.

Ш а г 5. Делаем шаг и приходим в новую точку

182 Глава 12. Многомерная оптимизация с ограничениями

И т е р а ц и я 3

−→

Ш а г 1. Проверяем точку X 2 на оптимальность. Вычисляя

−→ −→

AX 2 − b = (0, −0.5, −1.5, −0.5)T , видим, что имеется одно актив-

ное ограничение за номером 1, q = 1. Матрица активного набора состоит из одной строки Aq = (1, 1)T , матрица проектирования (она та же, что и на шаге 2 в предыдущей итерации)

Замечание 1. Метод проектирования (метод активного набора) оказался особенно эффективным для задач, в которых целевая функция квадратична, а ограничения линейны. Подобно методу Вулфа (см. с. 65) он гарантирует нахождение т о ч н о г о решения за конечное число шагов, но при этом менее трудоемок. По этой причине он является стандартным методом квадратичного программирования (QP) в промышленных пакетах прикладных программ, о чем мы будем говорить в гл. 13.

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

12.4.. Последовательное квадратичное программирование 183

12.4.Последовательное квадратичное программирование

Если метод проекции градиента можно рассматривать как адаптацию стандартных градиентных методов (т. е. методов первого порядка) к ситуации с ограничениями, то последовательное квадратичное программирование представляет собой попытку приспособить к такой же ситуации методы второго порядка (ньютоноподобные методы). Вместо того, чтобы явно учитывать ограничения, строится процедура численного решения уравнений Куна — Таккера.

а необходимые условия оптимальности определяются (см. форму-

Будем решать эту систему классическим методом Ньютона (см. с. 115). Если ввести обозначения для составного вектора пе-

184 Глава 12. Многомерная оптимизация с ограничениями

то система (12.22) запишется в виде одного векторного уравне-

элементы которой определяются следующими выражениями (см. сноску на с. 115):

Следовательно, A представляет собой матрицу Гессе функции Лагранжа, а C = BT — матрицу Якоби (транспонированный матричный градиент) вектор-функции ограничений. Возвращаясь к первоначальным обозначениям, получаем рекуррентную формулу

12.4.. Последовательное квадратичное программирование 185

где величина итеративного шага по переменным определяется выражением

квадратичная го процесса. Изучая оптимизацию без ограниминимизация чений, мы замечали (см. с. 115), что существу-

ет тесная связь между ньютоновским процессом

−→ −→

нахождения корня векторного уравнения f (X ) = 0 и итератив-

−→

ной процедурой минимизации целевой функции f (X ), аппрокси-

мируемой параболоидом. Оказывается, подобная связь имеет место и при наличии ограничений, однако при этом мы будем иметь дело не с самой целевой функцией, а с функцией Лагранжа. Сейчас мы покажем, что каждая итерация классического ньютоновского метода решения уравнений Куна — Таккера эквивалентна решению некоторой вспомогательной оптимизационной задачи.

Пусть на k-й итерации ньютоновского процесса решения системы нелинейных уравнений Куна — Таккера (12.22) получены

186 Глава 12. Многомерная оптимизация с ограничениями

→− Поставим вспомогательную задачу нахождения такого шага d , который минимизирует квадратичную аппроксимацию функции Лагранжа (12.24) при линейных ограничениях (12.25). Для ее решения, пока ограничения заданы равенствами, нам не потребуется применять численные методы. Решение легко найти аналитически, если применить условия оптимальности первого порядка.