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

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

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

Мотивация

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

свести к минимуму ж(Икс)

при условии Икс ≥ б

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

свести к минимуму ж(Икс) + c(Икс),

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

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

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

свести к минимуму ж(Икс) + мкг(Икс)

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

Логарифмическая барьерная функция

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

Это вводит градиент в оптимизируемую функцию, который поддерживает менее экстремальные значения ${\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{cases}\sum _{i=1}^{m}-\log(b_{i}-a_{i}^{T}x)&{\text{for }}Ax<b\\+\infty &{\text{otherwise}}\end{cases}}}$

Смотрите также

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

Примечания

Рекомендации

1. Нестеров, Юрий (2018). Лекции по выпуклой оптимизации (2-е изд.). Чам, Швейцария: Springer. п. 56. ISBN  978-3-319-91577-7.
2. Нокедаль, Хорхе; Райт, Стивен (2006). Численная оптимизация (2-е изд.). Нью-Йорк, штат Нью-Йорк: Спрингер. п. 566. ISBN  0-387-30303-0.
3. Вандербей, Роберт Дж. (2001). Линейное программирование: основы и расширения. Kluwer. С. 277–279.

внешняя ссылка

• Лекция 14: Барьерный метод от профессора Ливена Ванденберге из UCLA