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

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

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

Мотивація ред.

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

мінімізувати

f (x)

за умов

x \geq b

де $b$ — якась стала. Якщо користувач бажає видалити обмеження-нерівності, задачу можна переформулювати як

мінімізувати

f (x) + c (x)

,

де

c (x) = \infty

якщо

x < b

, інакше нуль.

Ця задача тотожна першій. Тут ми позбавились нерівностей, але додали проблему, що штрафна функція $c$ і, отже, цільова функція $f (x) + c (x)$ , не є неперервними, тим самим відкинувши можливість використання обчислення для розв'язання.

Бар'єрна функція це неперервне наближення $g$ до $c$ , яке прагне нескінченності коли $x$ наближається до $b$ згори. Використовуючи цю функцію можна сформулювати нову задачу оптимізації.

мінімізувати

f (x) + μ g (x)

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

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

Для логарифмічних бар'єрних функцій, $g(x,b)$ визначена як $-\log(b-x)$ коли $x<b$ і $\infty$ інакше (для одновимірного випадку. Дивись нижче для багатовимірного). По суті тут ми покладаємося на факт того, що $\log(t)$ прагне до від'ємної нескінченності коли $t$ прагне до 0.

Таким чином, до функції, яку ми оптимізуємо, ми додаємо градієнт, який віддає перевагу менш крайнім значенням $x$ (у цьому випадку значенням меншим ніж $b$ ), при цьому маючи порівняно маленький вплив на функцію вдалині від крайніх значень.

Можна обрати саме логарифмічні бар'єрні функції, а не обчислювально менш дорогі обернені бар'єрні функції залежно від функції, яку треба оптимізувати.

Вищі виміри ред.

За умови, що кожен вимір є незалежним, розширення на вищі виміри просте. Для кожної змінної $x_{i}$ , яка має бути строго менша ніж $b_{i}$ , додати $-\log(b_{i}-x_{i})$ .

Формальне визначення ред.

Мінімізувати $\mathbf {c} ^{T}x$ subject to $\mathbf {a} _{i}^{T}x\leq b_{i},i=1,\ldots ,m$

Припустимо строгу допустимість: $\{\mathbf {x} |Ax<b\}\neq \emptyset$

Визначимо логарифмічний бар'єр $\Phi (x)={\begin{cases}\sum _{i=1}^{m}-\log(b_{i}-a_{i}^{T}x)&Ax<b\\+\infty &Ax\geq b\end{cases}}$

Примітки ред.

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

Посилання ред.

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

[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.

[1]

[2]