Bariérová funkce

Bariérová funkce je spojitá funkce , jejíž hodnota v bodě inklinuje k nekonečnu, když se bod blíží k hranici oblasti možných řešení .

Bariérová funkce se používá v optimalizačních problémech jako korekční člen, aby se zajistilo, že existují řešení v přípustné oblasti. Například při hledání optimální hodnoty funkce může být proměnná omezena na hodnotu přísně menší než nějaká konstanta , a to nahrazením funkce $f(x)$ $X$ $b$

f(x)-\log(bx).

Zároveň funkce

x\mapsto -\log(bx)

hraje roli bariérové funkce.

Dva nejpoužívanější typy bariérových funkcí jsou inverzní bariérové funkce a logaritmické bariérové funkce. Obnovený zájem o logaritmické bariérové funkce je způsoben jejich spojením s metodami dvou přímých vnitřních bodů .

Logaritmická bariérová funkce

Pro logaritmické bariérové funkce je definována jako pro a jinak (v dimenzi 1. Vyšší rozměry viz níže). Tato definice se opírá o skutečnost, že má tendenci k mínus nekonečnu, když má tendenci k 0. $g(x,b)$ $-\log(bx)$ $x<b$ $\infty$ $\log(t)$ $t$

To poskytuje velké hodnoty gradientu pro optimalizovanou funkci blízko , zatímco změny ve funkci směrem od se mění jen málo. $b$ $b$

Namísto logaritmické bariérové funkce může být výhodnější použít inverzní bariérovou funkci, která má menší výpočetní náročnost, ale záleží na funkci, která je optimalizována.

Pokud existuje několik proměnných, měli byste pro každou proměnnou přidat bariérovou funkci , která by měla být přísně omezena hodnotou , add . $x_{i}$ $bi}$ $-\log(b_{i}-x_{i})$

Formální definice

Minimalizujte za podmínek $\mathbf {c} ^{T}x$ $\mathbf {a} _{i}^{T}x\leq b_{i},i=1,\ldots ,m$

Přijímáme přísná omezení: $\{\mathbf {x} |Axe<b\}\neq \emptyset$

Definujte logaritmickou bariéru $\Phi (x)={\begin{cases}\sum _{i=1}^{m}-\log(b_{i}-a_{i}^{T}x),Ax<b \\+\infty ,Ax\geq b\end{cases}}$

Literatura

George Nocedal, Stephen Wright. Numerická optimalizace. - New York, NY: Springer, 1999. - ISBN 0-387-98793-2 .
Přednáška 14: Bariérová metoda Archivováno 23. listopadu 2015 na Wayback Machine od profesora Lievena Vandenberghe z UCLA