Бар'єрна функція

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

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

Мотивація

Розглянемо таку задачу оптимізації з обмеженнями:

мінімізувати 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 це вільний параметр. Ця задача не є тотожною до початкової, але коли μ наближається до нуля, вона стає все кращим наближенням.^[2]

Логарифмічна бар'єрна функція

Для логарифмічних бар'єрних функцій, ${\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}$ subject to ${\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)&Ax<b\\+\infty &Ax\geq b\end{cases}}}$

Примітки

1. Nocedal, Jorge; Wright, Stephen (1999). Numerical Optimization. New York, NY: Springer. ISBN 0-387-98793-2.
2. Vanderbei, Robert J. (2001). Linear Programming: Foundations and Extensions. Kluwer. с. 277—279.

Посилання

• Lecture 14: Barrier method [Архівовано 23 листопада 2015 у Wayback Machine.] від проф. Лівена Ванденберга UCLA