Метод штрафных функций и барьерных функций

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

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

f (x) à min; (8.65)

j_i (x) £ 0, ; (8.66)

y_i (x) = 0, . (8.67)

Тогда можно построить вспомогательную функцию

Q (x) = f (x) + a × H (x), (8.68)

где H (x)–функция штрафа, a - параметр штрафа.

Вспомогательная функция играет роль модифицированного критерия, который при выполнении всех ограничений должен совпадать с исходным. Поэтому необходимо, чтобы в допустимой области Н (х) равнялась нулю, а вне ее была положительной. Для задачи (8.65)-(8.67) функция штрафа включает две составляющие Н (х) = Н_j (x) + Н_y (x), учитывающие ограничения-неравенства и ограничения-равенства соответственно и удовлетворяющие условиям

(8.69)

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

где р – натуральное число. Для дифференцируемости функций берут четные значения р, обычно р = 2.

Чем больше a, тем сильнее влияет функция штрафа и, значит, тем точнее выполняются условия задачи.

Пример 8.8. Дана задача

f (x) = x à min;

j (x)=3 – x £ 0.

Ответ очевиден: x ^*=3. Теперь сведем эту задачу к определению безусловного экстремума вспомогательной функции. Построим штрафную функцию в соответствии с (8.69): H = [max (0, 3-x)]². Тогда приходим к задаче

Q = x + a [max (0, 3-x)]²® min.

На рис. 8.41 и 8.42 показаны функции aH и Q для двух значений a. Видно, что точки минимума вспомогательной функции с увеличением a приближаются к точке условного минимума исходной задачи. Такой же вывод следует из аналитического решения. Действительно, при x <3 вспомогательная функция имеет вид

Q = x + a × (3 - x)².

Находим минимум этой функции:

Отсюда получаем

Пример 8.9. Рассмотрим влияние параметра шага в задаче

Здесь и На рис. 8.43 построены линии уровня функции q для разных значений a и линия ограничения y. При a =0 имеем q = f,и минимум q достигается в точке безусловного минимума f: x ₁= x ₂=1. С увеличением a меняется форма линий уровня q и положение минимума. При a =1 минимум q смещается к линии ограничения, а при a =1000 он практически точно совпадает с условным минимумом задачи.

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

Таким образом, чтобы безусловный минимум вспомогательной функции был близок к условному минимуму решаемой задачи, необходимо брать очень большое значение a, теоретически бесконечное. Однако при больших a возникают серьезные трудности при поиске минимума вспомогательной функции. Поэтому предлагается решать последовательность задач минимизации Q с возрастающими значениями a. При этом в качестве начальной точки следующей задачи берется оптимальная точка предыдущей. Такой прием использован в следующем алгоритме штрафных функций.

Алгоритм.

1. Задать: начальную точку x ⁰, точность e, начальное значение a ₀ и число b > 1.

2. Минимизировать Q (x) одним из методов безусловной оптимизации, в результате чего определяется .

3. Проверить: если , то остановиться, приняв за оптимальное решение задачи.

4. Положить , за начальную точку принять и вернуться на шаг 2.▲

Рекомендуется выбирать значения параметров алгоритма из диапазонов: a ₀Î(0,1], b Î(1,10]. Начальную точку следует задавать в недопустимой области.

Пример 8.10. Алгоритмом штрафных функций решить задачу

Возьмем начальную точку x ⁰=(-5;5), a ₀=0,21, b =5 и e =0,0001. Применяя для минимизации Q метод Ньютона, получаем результаты, представленные в табл. 8.4.

Таблица 8.4

№ итерации	a	x 1	x 2	f	Q	aH
	0.21	-5			283.533	13.533
	1.05	-0.191	-0.132	-0.094	0.939	1.032
	5.25	-0.209	-0.169	-0.09	5.035	5.125
	26.25	-0.654553	-1.059105	1.651353	13.504372	11.853019
	131.25	-0.990765	-1.731532	5.068137	7.691651	2.623514
	656.25	-1.046856	-1.843717	5.814225	6.343889	0.529664
	3281.25	-1.057736	-1.865478	5.964774	6.070887	0.106113
	16406.25	-1.059899	-1.869804	5.994933	6.016163	0.02123
	82031.25	-1.060331	-1.870668	6.000967	6.005213	0.004246
	410156.25	-1.060417	-1.870841	6.002174	6.003023	0.000849
	2050781.25	-1.060434	-1.870876	6.002415	6.002585	0.00017
	>10^7	-1.060434	-1.870884	6.002469	6.002503	3.397E-05

Как следует из таблицы, решение с заданной высокой точностью получено за 11 итераций алгоритма. Заметим, что несмотря на увеличение a значение aH сходится к нулю, обеспечивая сходимость алго­ритма. Траектория поиска и линии уровня функции f изображены на рис. 8.44.▲

Другой пример поиска методом штрафных функций приведен на рис. 8.45 для задачи

Поиск проведен из начальной точки (-2;-7) с параметрами a ₀=0,1 и b =2. Здесь, как и в предыдущем примере, на первой итерации алгоритма движение направлено в сторону безусловного минимума целевой функции. Это объясняется небольшим начальным значением параметра штрафа, при котором основное влияние на направление оказывает целевая функция. С возрастанием a направление поиска ориентируется на условный экстремум.

Еще один пример поиска показан на рис. 8.46 для задачи

Здесь поиск производился при a ₀=1 и b =10. Такие параметры обусловили другой характер движения к условному минимуму: первая итерация уже не приводит в окрестность безусловного экстремума и траектория не имеет резких изменений направ­ления поиска.

Таким образом, выбор параметров поиска имеет существенное влияние на эффективность алгоритма.

Метод барьерных функций

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

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

Исходная задача на условный экстремум задается в виде

f (x) à min; (8.70)

j_i (x) £ 0, . (8.71)

Она преобразуется в задачу безусловной минимизации вспомогательной функции

Q (x) = f (x) + mB (x),

где B (x) – барьерная функция, m - параметр барьера.

Обязательное условие: внутренность области не должна быть пустой (имеются точки, в которых " j_i (x) < 0).

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

Как и в случае штрафной функции, существует несколько конструкций B (x), удовлетворяющих этим условиям. Но в основном используется барьерная функция в виде

(8.72)

Понятно, что решение вспомогательной задачи зависит от значения параметра барьера. Покажем на задаче из примера 8.7 влияние m на результат минимизации Q.

Пример 8.11. Исходная задача:

f (x) = x à min;

j (x)=3 – x £ 0.

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

Находим точку минимума Q:

Отсюда получаем

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

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

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

Алгоритм.

1. Выбрать начальную точку x ⁰ так, чтобы " j_i (x ⁰)<0; задать точность e, начальное значение m ₀ и число b Î (0, 1).

2. Минимизировать Q (x) одним из методов безусловной оптимизации, в результате чего определяется .

3. Проверить: если , то остановиться, приняв за оптимальное решение задачи.

5. Положить , за начальную точку принять и вернуться на 2.▲

Значение m ₀ можно брать из интервала [2, 10]. Важное замечание касается п.2 алгоритма: в процессе поиска минимума вблизи границы из-за дискретности шагов возможен выход за допустимую область, где барьерная функция становится отрицательной, что повлечет расхождение поиска. Поэтому необходима явная проверка на допустимость точек на каждом шаге при минимизации Q.

Пример 8.10 (Базара, Шетти). Исходная задача:

f (x) = (x ₁ - 2)⁴+(x ₁-2 x ₂)²® min;

j (x)= x ₂£ 0.

Решение находим, используя соответствующую вспомогательную функцию

Q =(x ₁ - 2)⁴+(x ₁-2 x ₂)² -

За начальную точку возьмем допустимую точку (0;1), значения m и b принимаем равными 10. Результаты поиска алгоритмом барьерных функций представлены в табл. 8.5 и на рис. 8.48.

 

 

Таблица 8.5

№ итерации	m	x 1	x 2	f	Q	mB
		0.7079	1.5315	8.3338	18.0388	9.705
	1.0	0.8282	1.1098	3.8214	6.1805	2.3591
	0.1	0.8989	0.9638	2.5282	3.1701	0.6419
	0.01	0.9294	0.9162	2.1291	2.3199	0.1908
	0.001	0.9403	0.9011	2.0039	2.0629	0.0590
	0.0001	0.94389	0.89635	1.9645	1.9829	0.0184

Как и следовало ожидать, с уменьшением m значение mB стремится к нулю.

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

Q (x) = f (x) + mB (x) + где барьерная функция B (x) применяется к неравенствам, а штрафная функция Н (х) – к ограничениям-равенствам. Последовательность задач минимизации Q решается с уменьшающимися значениями параметра m.