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

Постановка задачи

Даны дважды непрерывно дифференцируемые целевая функция f (x) = f (x 1,.., xn) и функции ограничений-неравенств gj (x) ≤ 0, j = 1,..., m, определяющие множество допустимых решений X.

Требуется найти локальный минимум целевой функции на множестве X, т. е. такую точку х *∈ X, что

где X = { x | gj (x) ≤ 0, j = 1,..., m }.

Стратегия поиска

Идея метода заключается в сведении задачи на условный минимум к решению последовательности задач поиска минимума вспомогательной функции F (x, rk) = f (x) + P (x, rk), где P (x, rk) — штрафная функция, rk > 0 — параметр штрафа.

Как правило, используются:

а) обратная штрафная функция (рис. 9.7, а);

б) логарифмическая штрафная функция (рис. 9.7, б).

Рис 9.7

Обе штрафные функции определены и непрерывны внутри множества Х, т. е. на множестве { x | gj (x) < 0, j = 1,..., m }, и стремятся к бесконечности при приближении к границе множества изнутри. Поэтому они называются барьерными функциями. При rk > 0 штрафная функция, задаваемая обратной функцией, положительна. Логарифмическая штрафная функция положительна при –1 < g (x) < 0 и отрицательна при g (x) < –1, т. е. внутренним точкам области отдается предпочтение перед граничными точками.

Начальная точка задается только внутри множества X. На каждой k - й итерации ищется точка x *(rk) минимума вспомогательной функции F (x, rk) при заданном параметре rk с помощью одного из методов безусловной минимизации. Полученная точка x *(rk) используется в качестве начальной на следующей итерации, выполняемой при уменьшающемся значении параметра штрафа. При rk → +0 последовательность точек x *(rk) стремится к точке условного минимума х *. Барьерные функции как бы препятствуют выходу из множества X, а если решение задачи лежит на границе, то процедура метода приводит к движению изнутри области к границе.

Заметим, что согласно описанной процедуре точки x *(rk) лежат внутри множества допустимых решений для каждого rk. Этим объясняется то, что метод барьерных функций иногда называется методом внутренних штрафов.

Алгоритм