В оптимізації з обмеженнями, бар'єрна функція — це неперервна функція чиє значення у точці наближається до нескінченності якщо точка наближається до границі допустимої області задачі оптимізації. Такі функції використовуються для того, щоб замінити обмеження задані нерівностями через штрафний доданок у цільовій функції.
Двома найпоширенішими типами бар'єрних функцій є обернена бар'єрна функція і логарифмічна. Відновлення зацікавленості в логарифмічній бар'єрній функції змотивоване її зв'язком із двоїсто-прямими методами внутрішньої точки.
Мотивація
Розглянемо таку задачу оптимізації з обмеженнями:
- мінімізувати 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 це вільний параметр. Ця задача не є тотожною до початкової, але коли μ наближається до нуля, вона стає все кращим наближенням.
Логарифмічна бар'єрна функція
Для логарифмічних бар'єрних функцій, визначена як
коли
і
інакше (для одновимірного випадку. Дивись нижче для багатовимірного). По суті тут ми покладаємося на факт того, що
прагне до від'ємної нескінченності коли
прагне до 0.
Таким чином, до функції, яку ми оптимізуємо, ми додаємо градієнт, який віддає перевагу менш крайнім значенням (у цьому випадку значенням меншим ніж
), при цьому маючи порівняно маленький вплив на функцію вдалині від крайніх значень.
Можна обрати саме логарифмічні бар'єрні функції, а не обчислювально менш дорогі обернені бар'єрні функції залежно від функції, яку треба оптимізувати.
Вищі виміри
За умови, що кожен вимір є незалежним, розширення на вищі виміри просте. Для кожної змінної , яка має бути строго менша ніж
, додати
.
Формальне визначення
Мінімізувати subject to
Припустимо строгу допустимість:
Визначимо логарифмічний бар'єр
Примітки
- Nocedal, Jorge; Wright, Stephen (1999). Numerical Optimization. New York, NY: Springer. ISBN .
- Vanderbei, Robert J. (2001). Linear Programming: Foundations and Extensions. Kluwer. с. 277—279.
Посилання
- Lecture 14: Barrier method [ 23 листопада 2015 у Wayback Machine.] від проф. Лівена Ванденберга UCLA
На цю статтю не посилаються інші статті Вікіпедії. Будь ласка розставте посилання відповідно до . |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
V optimizaciyi z obmezhennyami bar yerna funkciya ce neperervna funkciya chiye znachennya u tochci nablizhayetsya do neskinchennosti yaksho tochka nablizhayetsya do granici dopustimoyi oblasti zadachi optimizaciyi Taki funkciyi vikoristovuyutsya dlya togo shob zaminiti obmezhennya zadani nerivnostyami cherez shtrafnij dodanok u cilovij funkciyi Dvoma najposhirenishimi tipami bar yernih funkcij ye obernena bar yerna funkciya i logarifmichna Vidnovlennya zacikavlenosti v logarifmichnij bar yernij funkciyi zmotivovane yiyi zv yazkom iz dvoyisto pryamimi metodami vnutrishnoyi tochki MotivaciyaRozglyanemo taku zadachu optimizaciyi z obmezhennyami minimizuvati f x za umov x b de b yakas stala Yaksho koristuvach bazhaye vidaliti obmezhennya nerivnosti zadachu mozhna pereformulyuvati yak minimizuvati f x c x de c x yaksho x lt b inakshe nul Cya zadacha totozhna pershij Tut mi pozbavilis nerivnostej ale dodali problemu sho shtrafna funkciya c i otzhe cilova funkciya f x c x ne ye neperervnimi tim samim vidkinuvshi mozhlivist vikoristannya obchislennya dlya rozv yazannya Bar yerna funkciya ce neperervne nablizhennya g do c yake pragne neskinchennosti koli x nablizhayetsya do b zgori Vikoristovuyuchi cyu funkciyu mozhna sformulyuvati novu zadachu optimizaciyi minimizuvati f x m g x de m gt 0 ce vilnij parametr Cya zadacha ne ye totozhnoyu do pochatkovoyi ale koli m nablizhayetsya do nulya vona staye vse krashim nablizhennyam Logarifmichna bar yerna funkciyaDlya logarifmichnih bar yernih funkcij g x b displaystyle g x b viznachena yak log b x displaystyle log b x koli x lt b displaystyle x lt b i displaystyle infty inakshe dlya odnovimirnogo vipadku Divis nizhche dlya bagatovimirnogo Po suti tut mi pokladayemosya na fakt togo sho log t displaystyle log t pragne do vid yemnoyi neskinchennosti koli t displaystyle t pragne do 0 Takim chinom do funkciyi yaku mi optimizuyemo mi dodayemo gradiyent yakij viddaye perevagu mensh krajnim znachennyam x displaystyle x u comu vipadku znachennyam menshim nizh b displaystyle b pri comu mayuchi porivnyano malenkij vpliv na funkciyu vdalini vid krajnih znachen Mozhna obrati same logarifmichni bar yerni funkciyi a ne obchislyuvalno mensh dorogi oberneni bar yerni funkciyi zalezhno vid funkciyi yaku treba optimizuvati Vishi vimiri Za umovi sho kozhen vimir ye nezalezhnim rozshirennya na vishi vimiri proste Dlya kozhnoyi zminnoyi x i displaystyle x i yaka maye buti strogo mensha nizh b i displaystyle b i dodati log b i x i displaystyle log b i x i Formalne viznachennya Minimizuvati c T x displaystyle mathbf c T x subject to a i T x b i i 1 m displaystyle mathbf a i T x leq b i i 1 ldots m Pripustimo strogu dopustimist x A x lt b displaystyle mathbf x Ax lt b neq emptyset Viznachimo logarifmichnij bar yer F x i 1 m log b i a i T x A x lt b A x b displaystyle Phi x begin cases sum i 1 m log b i a i T x amp Ax lt b infty amp Ax geq b end cases PrimitkiNocedal 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 s 277 279 PosilannyaLecture 14 Barrier method 23 listopada 2015 u Wayback Machine vid prof Livena Vandenberga UCLA Na cyu stattyu ne posilayutsya inshi statti Vikipediyi Bud laska rozstavte posilannya vidpovidno do prijnyatih rekomendacij