Барьерная функция

В стесненном оптимизации , поле математики , A барьерная функция является непрерывной функцией , значение которой на точку возрастает до бесконечности, что и точка приближается к границе допустимой области задачи оптимизации. ^{[1] [2]} Такие функции используются для замены ограничений неравенства штрафным членом в целевой функции, с которым легче справиться.

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

Мотивация [ править ]

Рассмотрим следующую задачу оптимизации с ограничениями:

минимизировать f ( x )

при условии x ≥ b

где b - некоторая постоянная. Если кто-то хочет удалить ограничение неравенства, проблема может быть переформулирована как

минимизировать f ( x ) + c ( x ) ,

где c ( x ) = ∞, если x < b , и ноль в противном случае.

Эта проблема эквивалентна первой. Это избавляет от неравенства, но вводит проблему, заключающуюся в том, что функция штрафа c и, следовательно, целевая функция f ( x ) + c ( x ) , являются прерывистыми , что не позволяет использовать исчисление для ее решения.

Барьерная функция теперь представляет собой непрерывное приближение g к c, которое стремится к бесконечности, когда x приближается к b сверху. С помощью такой функции формулируется новая задача оптимизации, а именно.

минимизировать f ( x ) + μ g ( x )

где μ > 0 - свободный параметр. Эта проблема не эквивалентна исходной, но по мере приближения μ к нулю она становится все лучшим приближением. ^[3]

Логарифмическая барьерная функция [ править ]

Для логарифмических барьерных функций определяется как когда, так и иначе (в одном измерении. См. Ниже определение в более высоких измерениях). Это по существу зависит от того факта, что стремится к отрицательной бесконечности, как стремится к 0.${\ Displaystyle г (х, Ь)}$${\ Displaystyle - \ журнал (bx)}$${\ displaystyle x <b}$${\ displaystyle \ infty}$${\ Displaystyle \ журнал (т)}$${\ displaystyle t}$

Это вводит градиент в оптимизируемую функцию, который поддерживает менее экстремальные значения (в данном случае значения ниже, чем ), в то же время оказывая относительно небольшое влияние на функцию вдали от этих крайних значений .${\ displaystyle x}$${\ displaystyle b}$

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

Высшие измерения [ править ]

Расширение до более высоких измерений просто при условии, что каждое измерение является независимым. Для каждой переменной, значение которой должно быть строго меньше , добавьте .${\ displaystyle x_ {i}}$${\ displaystyle b_ {i}}$${\ displaystyle - \ log (b_ {i} -x_ {i})}$

Формальное определение [ править ]

Свернуть при условии${\ displaystyle \ mathbf {c} ^ {T} x}$${\ displaystyle \ mathbf {a} _ {i} ^ {T} x \ leq b_ {i}, i = 1, \ ldots, m}$

Допустим строго выполнимо: ${\ displaystyle \ {\ mathbf {x} | Ax <b \} \ neq \ emptyset}$

Определить логарифмический барьер ${\ displaystyle \ Phi (x) = {\ begin {case} \ sum _ {i = 1} ^ {m} - \ log (b_ {i} -a_ {i} ^ {T} x) & {\ text {for}} Ax <b \\ + \ infty & {\ text {иначе}} \ end {case}}}$

См. Также [ править ]

• Штрафной метод
• Дополненный лагранжев метод

Ссылки [ править ]

Внешние ссылки [ править ]

• Лекция 14: Барьерный метод от профессора Ливена Ванденберге из Калифорнийского университета в Лос-Анджелесе.