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

Этот метод основан на том, что строится некоторая новая, так называемая целевая функция:

F_k (x) = f(x) + C(k) Ф(h(x), g(x)),

где Ф(h(x), g(x)) штрафная функция, значения которой малы в допустимой области и резко возрастают вне ее;

k - индекс итерации;

C(k) - возрастающая числовая последовательность.

Далее решается последовательность задач иска безусловного минимума функции F_k(x) (k = 1, 2, 3,...), причем принимается

x⁰(k) = x^*(k-1),

где x⁰(k) - начальная точка k-й итерации;

x^*(k-1) - точка минимума, найденная на (k-1)-й итерации.

При этом x⁰(1) = x(0) - начальной точке поиска условного минимума (выбирается произвольно).

Как видно из определения штрафной функции, безусловный минимум x^*(k) функции F_k(x) на k-й итерации находится вблизи гра­ницы допустимой области (если только безусловный минимум f(x) лежит вне допустимой области). Это происходит потому, что целевая функция возрастает с обеих сторон от линии, образующей границу.

Условный минимум считается найденным при выполнении условия:

||x^*(k) – x^*(k-1)||<ε_x

где ε_x - заданная точность поиска.

Штрафные функции могут быть внутренними и внешними.

Внутренние функции имеют область определения внутри до­пустимой области. Они быстро возрастают в окрестности границы. Функция Ф(x) является, как правило, суммой компонент, соответст­вующих отдельным уравнениям ограничений g_j(x). Наиболее извест­ной здесь является логарифмическая функция. Например, j-й компо­нентой штрафной функции может быть ln(g_j(x)). Для ограничений-равенств внутренние штрафные функции обычно не применяются.

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

φ_j(x) = 0, g_j(x)>=0,

g_j(x), g_j(x)<0 или φ_j(x) = |h_i(x)|.

В штрафную функцию чаще всего входят четные степени указанных функций. От применения различных видов штрафных функций зависят скорости сходимости алгоритмов для различных исходных данных и вида функций f(x), g_j(x), h_i(x). Структура же алго­ритма при этом не меняется. Поэтому в качестве иллюстрации мето­да рассмотрим только так называемый квадратичный штраф, где

F(x) = f(x) + 1/2 C(k)(Σφ_i²(x) + Σφ_j²(x)).

В качестве C(k) применяется последовательность

C(k) = β^k-1 ,где = 4... 10.

Недостатком метода штрафных функций является необходи­мость быстрого роста последовательности C(k) для обеспечения при­емлемой скорости сходимости метода (относительно небольшого числа итераций для достижения условного минимума). Но при боль­ших C(k) функция F_k(x) имеет овражный характер, что, в свою оче­редь, замедляет сходимость алгоритмов поиска безусловного мини­мума и требует их усложнения. Поиск компромисса в этой ситуации привел к комбинации методов.

Дата добавления: 2014-01-07