Методы первого порядка. Задачи и методы условной оптимизации нелинейного программирования, страница 8

R(X) = z(X) + aH(X) .                                                       (4.42)

Функция R(X) называется штрафной функцией, коэффициент a - коэффициентом штрафа (a >0), а функция H(X) – штрафом  (функцией штрафа).

З а м е ч а н и е  4.28. Некоторые авторы называют штрафной функцией функцию H(X), а  функцию R(X) – вспомогательной функцией.   

В функции R(X) на X не накладывается каких-либо ограничений. Добавление слагаемого aH(X) к функции z(X) можно рассматривать как введение специального “штрафа” за неточное выполнение ограничений. 

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

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

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

Для  задач с ограничениями-равенствами обычно используется штраф вида

H(X) = ,                                                   (4.43)

называемый квадратичным штрафом. Такой штраф препятствует отклонению величин g_i(X) от нуля (как в ту, так и другую сторону). Вид рассматриваемой функции для n=1 и m=1 приведен на рис. 4.14.

Рис. 4.14

Однозначные рекомендации по выбору коэффициента штрафа a отсутствуют. При его увеличении сходимость процесса поиска уменьшается (в связи с увеличением “овраж-ности” функции R(X)). При слишком малом a уменьшается точность определения точки экстремума.

В связи с этим методом предусматривается решение последовательности задач  безусловной оптимизации функции R(X) при  увеличивающемся значении a. Первоначальное значение a определяется опытным путем. Увеличение a обычно осуществляется путем его последовательного умножения  на некоторое фиксированное положительное число b (например, b=2).

В качестве критерия окончания итераций обычно рассматривается ограничение на величину модуля минимально допустимой разности двух последовательных значений штрафных функций R(X):

| R(X)_k+1 - R(X)_k | £ e .                                                       (4.44)

Детальный алгоритм метода штрафных функций приведен в [18].

Методы второй группы  включают метод прямого поиска с возвратом и метод проектирования вектора-градиента. 

В первом из методов условия строгого соблюдения ограничений g_i(X)=0 заменяют менее строгими, например:

 £ e             или                  £ e  ,                         (4.45)

где e - допустимое нарушение ограничения (в процессе поиска).

В этом случае внутри допустимого “коридора”, который образуется по обе стороны от ограничения, оптимум z(X) ищется любым методом без учета ограничений. Как только в процессе поиска достигается одна или несколько границ, задаваемых соотношениями g_i(X)=0, то происходит возврат на ограничения, причем это осуществляется по нормали  к функциям (поверхностям) ограничений. Графическое изображение процесса поиска оптимума (при n=2 и m=1) представлено на рис. 4.15.

Рис 4.15.

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