Bariérová funkce - Barrier function

V omezeném stavu optimalizace, pole matematika, a bariérová funkce je spojitá funkce jehož hodnota v bodě se zvyšuje do nekonečna, když se bod blíží hranici proveditelný region optimalizačního problému.^[1]^[2] Takové funkce se používají k nahrazení nerovnosti omezení penalizujícím termínem v objektivní funkci, se kterou se snáze pracuje.

Dva nejběžnější typy bariérových funkcí jsou funkce inverzní bariéry a logaritmické bariérové funkce. Obnovení zájmu o funkce logaritmické bariéry bylo motivováno jejich spojením s primal-dual vnitřní bodové metody.

Motivace

Zvažte následující omezený optimalizační problém:

minimalizovat

F (X)

podléhá

X \geq b

kde $b$ je nějaká konstanta. Pokud si přejete odstranit omezení nerovnosti, problém lze znovu formulovat jako

minimalizovat

F (X) + C (X)

,

kde

C (X) = \infty

-li

X < b

a jinak nula.

Tento problém je ekvivalentní prvnímu. Zbavuje nerovnosti, ale zavádí problém, že trest funguje $C$ , a tedy objektivní funkce $F (X) + C (X)$ , je diskontinuální, bránící používání počet to vyřešit.

Bariérová funkce je nyní spojitá aproximace $G$ na $C$ který má sklon k nekonečnu jako $X$ přístupy $b$ shora. Pomocí takové funkce je formulován nový optimalizační problém, viz.

minimalizovat

F (X) + μ g (X)

kde $μ > 0$ je bezplatný parametr. Tento problém není ekvivalentní originálu, ale jako $μ$ blíží nule, stává se stále lepší aproximací.^[3]

Funkce logaritmické bariéry

Pro funkce logaritmické bariéry ${ displaystyle g (x, b)}$ je definován jako ${ displaystyle - log (b-x)}$ když ${ displaystyle x$ a ${ displaystyle infty}$ jinak (v 1 dimenzi. Definice ve vyšších dimenzích viz níže). To se v zásadě opírá o skutečnost, že ${ displaystyle log (t)}$ má sklon k negativnímu nekonečnu jako ${ displaystyle t}$ inklinuje k 0.

To zavádí přechod do optimalizované funkce, který upřednostňuje méně extrémní hodnoty ${ displaystyle x}$ (v tomto případě hodnoty nižší než ${ displaystyle b}$ ), přičemž má relativně malý dopad na funkci mimo tyto extrémy.

Funkce logaritmické bariéry mohou být upřednostňovány před výpočetně méně nákladnými funkce inverzní bariéry v závislosti na optimalizované funkci.

Vyšší rozměry

Rozšíření do vyšších dimenzí je jednoduché, pokud je každá dimenze nezávislá. Pro každou proměnnou ${ displaystyle x_ {i}}$ která by měla být omezena na přísně nižší než ${ displaystyle b_ {i}}$ , přidat ${ displaystyle - log (b_ {i} -x_ {i})}$ .

Formální definice

Minimalizovat ${ displaystyle mathbf {c} ^ {T} x}$ podléhá ${ displaystyle mathbf {a} _ {i} ^ {T} x leq b_ {i}, i = 1, ldots, m}$

Předpokládejme striktně proveditelné: ${ displaystyle { mathbf {x} | Sekera$

Definovat logaritmická bariéra ${ displaystyle Phi (x) = { začít {případy} součet _ {i = 1} ^ {m} - log (b_ {i} -a_ {i} ^ {T} x) & { text {for}} Sekera$

Viz také

Trestní metoda
Rozšířená Lagrangeova metoda

Poznámky

Reference

^ Nesterov, Yurii (2018). Přednášky o konvexní optimalizaci (2. vyd.). Cham, Švýcarsko: Springer. str. 56. ISBN 978-3-319-91577-7.
^ Nocedal, Jorge; Wright, Stephen (2006). Numerická optimalizace (2. vyd.). New York, NY: Springer. str. 566. ISBN 0-387-30303-0.
^ Vanderbei, Robert J. (2001). Lineární programování: základy a rozšíření. Kluwer. 277–279.

externí odkazy

Přednáška 14: Bariérová metoda od profesora Lievena Vandenberghe z UCLA

Tento aplikovaná matematika související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.

[1] ^ Nesterov, Yurii (2018). Přednášky o konvexní optimalizaci (2. vyd.). Cham, Švýcarsko: Springer. str. 56. ISBN 978-3-319-91577-7.

[2] ^ Nocedal, Jorge; Wright, Stephen (2006). Numerická optimalizace (2. vyd.). New York, NY: Springer. str. 566. ISBN 0-387-30303-0.

[3] ^ Vanderbei, Robert J. (2001). Lineární programování: základy a rozšíření. Kluwer. 277–279.

[1]

[2]

[3]