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

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

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

f(x) à min; (8.70)

ji(x) £ 0,. (8.71)

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

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

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

Обязательное условие: внутренность области не должна быть пустой (имеются точки, в которых "ji (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. Выбрать начальную точку x0так, чтобы "ji(x0)<0; задать точность e, начальное значение m0 и число b Î (0, 1).

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

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

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

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

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

f(x) = (x1-2)4+(x1-2x2)2® min;

j(x)= x2£ 0.

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

Q=(x1-2)4+(x1-2x2)2 —

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

Таблица 8.5

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

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

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

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