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

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

Барьерная функция используется в задачах оптимизации как поправочный член чтобы гарантировать наличие решений в допустимой области. Например, когда ищется оптимальное значение функции f ( x ) {displaystyle f(x)} , переменная x {displaystyle x} может быть ограничена значением, строго меньшим, чем некоторая константа b {displaystyle b} , путём замены функции на

f ( x ) − log ⁡ ( b − x ) . {displaystyle f(x)-log(b-x).}

При этом функция

x ↦ − log ⁡ ( b − x ) {displaystyle xmapsto -log(b-x)}

играет роль барьерной функции.

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

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

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

Это даёт большие значения градиента для оптимизируемой функции вблизи b {displaystyle b} , в то время как изменения функции вдали от b {displaystyle b} мало изменяются.

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

Если переменных несколько, то следует добавить по барьерной функции для каждой переменной x i {displaystyle x_{i}} , которая должна быть строго ограничена значением b i {displaystyle b_{i}} , добавляем − log ⁡ ( b i − x i ) {displaystyle -log(b_{i}-x_{i})} .

Формальное определение

Минимизировать c T x {displaystyle mathbf {c} ^{T}x} при условиях a i T x ≤ b i , i = 1 , … , m {displaystyle mathbf {a} _{i}^{T}xleq b_{i},i=1,ldots ,m}

Принимаем строгие ограничения: { x | A x < b } ≠ ∅ {displaystyle {mathbf {x} |Ax<b} eq emptyset }

Определим логарифмический барьер Φ ( x ) = { ∑ i = 1 m − log ⁡ ( b i − a i T x ) , A x < b + ∞ , A x ≥ b {displaystyle Phi (x)={egin{cases}sum _{i=1}^{m}-log(b_{i}-a_{i}^{T}x),Ax<b+infty ,Axgeq bend{cases}}}