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

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

Тогда внешняя квадратичная штрафная функция запишется

ввиде

P (x1, x2) = (x1 − 2)2 + (x2 − 2)2+

+

+ R cut2[x21 + x22 − 4] + cut2[−x1 + x2]+

+cut2[x2 − 1] + cut2[−x1] + cut2[−x2], . (12.2)

На рис. 12.3 сплошными линиями показаны изолинии штрафной функции P (x1, x2) для данной задачи при значении штрафного параметра R = 2. На этом же рисунке построена допустимая

область, а также штриховыми линиями изображены изолинии исходной целевой функции f (x1, x2) = (x1 − 2)2 + (x2 − 2)2. Внут-

ри допустимой области оба семейства изолиний, как и следовало ожидать, совпадают.

*

Рис. 12.3. Изолинии исходной целевой (штриховые линии) и внешней штрафной (сплошные линии) функций. Параметр штрафа R=2

выпукла, поэтому любой метод выпуклой оптимизации даст точку глобального минимума.

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

колонке табл. 12.2 приведены соответствующие результаты без-

→−

условной оптимизации. Исходная точка X 0 = (1, 0.5)T .

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

— либо непосредственно, либо через функцию Лагранжа.

12.2.Общая схема релаксационных методов, учитывающих ограничения

Так же как и при оптимизации без ограничений, все релаксационные методы с ограничениями задаются стандартной итерационной процедурой

Следовательно, каждый конкретный метод характеризуется:

→−

• способом выбора направления движения d k на данном шаге;

• способом выбора длины шага tk;

• критерием остановки итерационного процесса.

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

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

то есть ограничения на неотрицательность всех или части пере-

−→

менных, если они существуют, уже заложены в условия gi(X ) 0.

правление называется возможным (feasible), если по нему можно

Отсюда следует дифференциальное условие возможности направ-

−→

Направление d мы называли ранее понижающим или прогрессивным, если по нему можно продвинуться на некоторое

нию (см. с. 30) следует дифференциальное условие прогрессивности направления через скалярное произведение

−→T −→ −→

d fi(X k) < 0.

(см. с. 19), замечаем, что оно неотрицательно, если cos ϕ 0, что соответствует −90◦ ϕ 90◦, т. е. угол между векторами ост-

рый или прямой. И наоборот, оно отрицательно, если угол тупой.

−→

Таким образом, направление d является возможным, если угол β между ним и вектором внешней нормали прямой или тупой, и является прогрессивным, если угол α между ним и а н т и - г р а д и е н т о м — острый.

Рис. 12.5. Возможные и прогрессивные направления для одного активного ограничения в двумерном случае

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

рованы следующим образом: полученный на k-м шаге план явля-

→−

ется оптимальным, если все возможные направления из X k не являются прогрессивными.

Существует множество способов выбора такого направления, в основном оно и определяет многообразие релаксационных мето-

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

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

−→

После того как направление d k выбрано, следует сделать шаг в данном направлении. В полношаговых релаксационных методах без ограничений длина шага tk выбиралась поиском без-

условного минимума целевой функции вдоль заданного направ-

При наличии ограничений так поступать нельзя, потому что полученное значение tk может оказаться слишком большим и вывести поиск за область ограничений.

Если обозначить через t значение, полученное в результате

безусловной минимизации, а через T — то значение t, при котором

→−

луч в направлении d протыкает область ограничений, то длину шага следует выбирать из условия

tk = min(t , T ).

В то время как величину t можно найти обычным линейным поиском, с определением предельной длины шага T проблем значительно больше. Для этого следует решить нелинейные уравне-

−→ −→

ния gi(X k + t d k) = 0 относительно переменной t для всех неак-

тивных ограничений и выбрать наименьший положительный ко-

Если функции ограничений простые, например линейные, то эта задача не составляет никакого труда, корни находятся аналитически. Для общего нелинейного случая часто используется другой подход к нахождению длины шага tk без вычисления в отдельности t и T , он основан на изложенной в предыдущем параграфе идее штрафных функций. Строится одномерная функция ψ(t), которая в англоязычной литературе называется merit

function, что можно перевести как функция выигрыша (выгоды,

Проще всего использовать внешний квадратичный штраф (12.1), однако возможны и другие варианты.

Поскольку функция качества уже учитывает ограничения, длина шага определяется из условия ее безусловного минимума:

tk = arg min ψ(t).

0 t<∞

Критерий

Как и в случае оптимизации без ограничений

остановки

(см. с. 95), могут использоваться различные условия остановки итерационного процесса. Критерии

по малости смещения текущей точки, по малости приращения целевой функции и по объему вычислений при этом не изменяются, однако условия первого порядка модифицируются с учетом ограничений.

Как следует из теории выпуклого программирования (см. с. 60), необходимыми условиями минимума для задачи в частном случае неограниченности переменных по знаку

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

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

В приближенном итерационном процессе оно формулируется как

где ε — установленный допуск (tolerance) по ограничениям, а cut[x] = max[0, x] — введенная ранее функция срезки (см. с. 159).

Для условий «а»–«в» в качестве меры оптимальности первого порядка используется бесконечная норма градиента лагранжиана,

−→

для условий «д» аналогичной мерой является maxi | yigi(X k)|, а в

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

Разумеется, проверка условия первого порядка по данному критерию производится только в тех алгоритмах, которые делают оценки множителей Лагранжа.

Рассмотрев общую схему релаксационных методов, учитывающих ограничения, вернемся к про-

блеме выбора конкретного направления движе-

→−

ния d k на каждой итерации. Разумеется, эта

→−

проблема возникает только тогда, когда текущая

точка X k находится на границе допустимой области, потому что внутри области наилучшим направлением всегда является направление антиградиента.

Практические приемы выбора прогрессивного направления

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

→−

ды, явно учитывающие ограничения gi(X ). Они стараются приспособить градиентный спуск к ситуации, когда движение прямо по антиградиенту невозможно. Существует обширный класс таких методов, созданных в основном в 1960–1970-х годах, из них

наиболее известен и широко используется вплоть до настоящего времени метод проектирования градиента (метод активного набора), который мы рассмотрим в следующем параграфе.

Вторая группа методов, интенсивно разрабатываемая в последние десятилетия, учитывает ограничения косвенным путем, через функцию Лагранжа. Наиболее передовым и эффективным представителем этой группы является метод последовательного квадратичного программирования — sequential quadratic programming (SQP), включенный во все современные библиотеки прикладных программ.

12.3. Метод проектирования градиента

Идею метода проиллюстрируем на простом примере (см. рис. 12.6). Пусть на k-й итерации релаксационного градиентного

Рис. 12.6. Проекция антиградиента на допустимую область D

−→

метода поиск пришел в такую точку X k на границе допустимой

−→ −→

области D, где направление антиградиента − f (X k) не является

−→ −→

возможным, поскольку угол α между ним и нормалью g(X k)

пределами допустимой области.