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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

В оптимізації з обмеженнями, бар'єрна функція — це неперервна функція чиє значення у точці наближається до нескінченності якщо точка наближається до границі допустимої області задачі оптимізації.[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.

Посилання

[ред. | ред. код]