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

Ограничения задачи специальным образом отражаются в критерии, в результате чего критерий модифицируется, а исходная задача на условный экстремум сводится к задаче на безусловный экстремум. В методе штрафных функций в критерий вводится штраф при нарушении условий задачи. Пусть в общем случае имеем задачу f (x) à min; j_i (x) £ 0, ; y_i (x) = 0, . Тогда можно построить вспомогательную функцию

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

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

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

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

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

Алгоритм.

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

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

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

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

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