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

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

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

Мотивація

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

мінімізувати Шаблон:Math

за умов Шаблон:Math

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

мінімізувати Шаблон:Math,

де Шаблон:Math якщо Шаблон:Math, інакше нуль.

Ця задача тотожна першій. Тут ми позбавились нерівностей, але додали проблему, що штрафна функція Шаблон:Mvar і, отже, цільова функція Шаблон:Math, не є неперервними, тим самим відкинувши можливість використання обчислення для розв'язання.

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

мінімізувати Шаблон:Math

де Шаблон:Math це вільний параметр. Ця задача не є тотожною до початкової, але коли Шаблон:Mvar наближається до нуля, вона стає все кращим наближенням.

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

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

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

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

Вищі виміри

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

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

Мінімізувати ${𝐜}^{T}x$ subject to ${𝐚}_i^{T}x\le b_i,i=1,\dots ,m$

Припустимо строгу допустимість: $\{𝐱|Ax<b\}\ne \mathrm{\varnothing }$

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

Посилання

• Lecture 14: Barrier method Шаблон:Webarchive від проф. Лівена Ванденберга UCLA