ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 24.10.2023
Просмотров: 14
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Метод барьерных функций
Изложение метода
Метод штрафных функций относится к группе методов внутренней точки, т.е. он начинает работать с допустимой точки x_0 и генерирует последовательность допустимых точек x_1,x_2,\dots,x_n. Метод барьерных функций, наоборот, относится к группе методов внешней точки, он начинает поиск с недопустимой точки и генерирует последовательность недопустимых решений, которая приближается к оптимальному решению извне допустимой области.
Пусть имеется задача минимизировать f(x) при ограничениях
g_i(x)\ge0, i=\bar{1,m}
h_i(x)=0 ,i=\bar{m+1,l}
В частности, для искомых функций – ограничений целесообразно использовать барьерную функцию следующего вида:
\alpha(x)=\sum_{i=1}^{m}R_1(g_i(x))+ \sum_{i=m+1}^{l}R_2(h_i(x))
R_1,R_2 - непрерывные функции, которые удовлетворяют условиям:
R_1(y)=0 , если y>=0 и R_1(y)>0 , если y<0,
R_2(y)=0 , если y=0 и R_2(y)>0 , если y\not=0.
Типичными являются следующие выражения для функций R_1,R_2:
R_1(y)=(max\{0,-y\})^p,
R_2(y)=|y|^p, где р – целое положительное число.
Далее от исходной задачи переходим к задачи безусловной оптимизации вспомогательной функции: минимизировать f(x)+r\alpha(x), где r>0 - штрафной коэффициент.
Пусть α– непрерывная функция. Обозначим \theta(r)=inf\{f(x)+r\alpha(x)\}.
Подход, связанный с барьерной функцией состоит в решении задачи вида:
максимизировать \theta(r) при ограничении r\ge0
Алгоритм метода барьерных функций
Пусть имеется следующая задача:
Минимизировать f(x) при ограничениях g_i(x)\ge0,h_i(x)=0, где функции f,g_i,h_i.
Начальный этап Выбрать \epsilon>0 Выбрать начальную точку x^1, параметр штрафа r_1 и число \beta>1. Положить k=1 и перейти к основному этапу.
Основной этап. k-я итерация.
Первый шаг. При начальной точке x_k и параметре штрафа r_kрешить следующую задачу:
минимизировать
f(x)+r_k\alpha(x)=f(x)+r_k\left[\sum_{i=1}^{m}(max\{0,-g_i(x)\})^p+ \sum_{i=m+1}^{l}|h_i(x)|^p\right] , где
p>0,p - целое.
Положить x_{k+1} равным оптимальному решению задачи и перейти ко второму шагу.
Второй шаг
Если r_k\alpha(x_{k+1})<\epsilon, то остановиться.
В противном случае положить r_{k+1}=\beta r_k. Заменить k на k+1 и перейти к первому шагу.