Бар’ерная функцыя

Пры аптымізацыі з абмежаваннямі бар'ерная функцыя — гэта бесперапынная функцыя, значэнне якой у кропцы імкнецца да бясконцасці пры набліжэнні кропкі да мяжы вобласці дапушчальных рашэнняў (Nocedal, Wright, 1999). Бар'ерная функцыя выкарыстоўваецца як штрафны член пры парушэнні абмежаванняў. Двума найбольш выкарыстоўванымі тыпамі бар'ерных функцый з'яўляюцца зваротныя бар'ерныя функцыі і лагарыфмічныя бар'ерныя функцыі. Аднаўленне цікавасці да лагарыфмічных бар'ерных функцый выклікана іх сувяззю з дваіста-прамымі метадамі ўнутранай кропкі.

Калі шукаецца аптымальнае значэнне функцыі f(x), тэмпература $x$ можа быць абмежаваная значэннем, строга меншым, чым некаторая канстанта $b$, шляхам замены на аптымізацыю функцыі $f(x)+g(x,b)$. Тут $g(x,b)$ — бар'ерная функцыя.

Лагарыфмічная бар'ерная функцыя

Для лагарыфмічных бар'ерных функцый $g(x,b)$ вызначаецца як $-\log(b-x)$ для $x<b$ і $\infty$ ў адваротным выпадку (у памернасці 1. Глядзіце ніжэй для больш высокіх памернасцяў). Пры такім вызначэнні абапіраюцца на той факт, што $\log(t)$ імкнецца да мінус бясконцасці, калі $t$ імкнецца да 0.

Гэта дае вялікія значэнні градыенту для функцыі, якую аптымізуюць, паблізу $b$, у той час як змены функцыі удалечыні ад $b$ мала змяняюцца.

Замест лагарыфмічнай бар'ернай функцыі можа быць зручней выкарыстоўваць зваротную бар'ерную функцыю, якая мае меншую вылічальную складанасць, але гэта залежыць ад функцыі, якую аптымізуюць.

Высокія памернасці

Пашырэнне да высокіх памернасцяў адбываецца проста, абслугоўваючы кожную памернасць асобна. Для кожнай зменнай $x_{i}$, якая павінна быць строга абмежаваная значэннем $b_{i}$, дадаем $-\log(b_{i}-x_{i})$.

Фармальнае вызначэнне

Мінімізаваць $\mathbf {c} ^{T}x$ пры ўмовах $\mathbf {a} _{i}^{T}x\leq b_{i},i=1,\ldots ,m$

Прымаем строгія абмежаванні: $\{\mathbf {x} |Ax<b\}\neq \emptyset$

Вызначым лагарыфмічны бар'ер $\Phi (x)={\begin{cases}\sum _{i=1}^{m}-\log(b_{i}-a_{i}^{T}x),Ax<b\\+\infty ,Ax\geq b\end{cases}}$

Літаратура

• Numerical Optimization. — New York, NY: Springer, 1999. — ISBN 0-387-98793-2.
• Lecture 14: Barrier method from Professor Lieven Vandenberghe of UCLA