Відкрити головне меню

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

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

МотиваціяРедагувати

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

мінімізувати f(x)
за умов xb

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

мінімізувати f(x) + c(x),
де c(x) = ∞ якщо x < b, інакше нуль.

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

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

мінімізувати f(x) + μ g(x)

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

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

Для логарифмічних бар'єрних функцій,   визначена як   коли   і   інакше (для одновимірного випадку. Дивись нижче для багатовимірного). По суті тут ми покладаємося на факт того, що   прагне до від'ємної нескінченності коли   прагне до 0.

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

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

Вищі виміриРедагувати

За умови, що кожен вимір є незалежним, розширення на вищі виміри просте. Для кожної змінної  , яка має бути бути строго менша ніж  , додати  .

Формальне визначенняРедагувати

Мінімізувати   subject to  

Припустимо строгу допустимість:  

Визначимо логарифмічний бар'єр  

ПриміткиРедагувати

  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. 

ПосиланняРедагувати