Барьерная функция

В ограниченной оптимизации , области математики , барьерная функция — это непрерывная функция , значение которой увеличивается до бесконечности по мере приближения ее аргумента к границе допустимой области задачи оптимизации. ^[1]^[2] Такие функции используются для замены ограничений- неравенств штрафным членом целевой функции, с которым легче справиться. Барьерную функцию также называют внутренней штрафной функцией , поскольку это штрафная функция, которая заставляет решение оставаться внутри допустимой области.

Двумя наиболее распространенными типами барьерных функций являются обратные барьерные функции и логарифмические барьерные функции. Возобновление интереса к логарифмическим барьерным функциям было мотивировано их связью с методами прямо-двойственной внутренней точки .

Мотивация

Рассмотрим следующую задачу ограниченной оптимизации:

минимизировать

f (x)

при условии

x \leq b

где $b$ — некоторая константа. Если кто-то хочет удалить ограничение неравенства, проблему можно переформулировать как

минимизировать

f (x) + c (x)

,

где

c (x) = \infty,

если

x > b

, и ноль в противном случае.

Эта проблема эквивалентна первой. Он избавляет от неравенства, но создает проблему, заключающуюся в том, что штрафная функция $c$ и, следовательно, целевая функция $f (x) + c (x)$ являются разрывными , что не позволяет использовать исчисление для ее решения.

Барьерная функция теперь представляет собой непрерывное приближение $g$ к $c$ , которое стремится к бесконечности, когда $x$ приближается $к b$ сверху. С использованием такой функции формулируется новая задача оптимизации, а именно.

минимизировать

f (x) + μ g (x)

где $µ > 0$ — свободный параметр. Эта задача не эквивалентна исходной, но по мере того, как $µ$ приближается к нулю, она становится все лучшим приближением. ^[3]

Логарифмическая барьерная функция

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

Это вводит градиент в оптимизируемую функцию, который благоприятствует менее экстремальным значениям $x$ (в этом случае значения ниже, чем $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$

Определить логарифмический барьер $g(x)={\begin{cases}\sum _{i=1}^{m}-\log(b_{i}-a_{i}^{T}x)&{\text{for }}Ax<b\\+\infty &{\text{otherwise}}\end{cases}}$

См. также

Ссылки

^ Nesterov, Yurii (2018). Lectures on Convex Optimization (2 ed.). Cham, Switzerland: Springer. p. 56. ISBN 978-3-319-91577-7 .
^ Носедаль, Хорхе; Райт, Стивен (2006). Численная оптимизация (2-е изд.). Нью-Йорк, штат Нью-Йорк: Спрингер. п. 566. ИСБН 0-387-30303-0 .
^ Вандербей, Роберт Дж. (2001). Линейное программирование: основы и расширения . Клювер. стр. 277–279.

Внешние ссылки

Лекция 14: Барьерный метод от профессора Ливена Ванденберге из Калифорнийского университета в Лос-Анджелесе.

Эта прикладной математике, статья, посвященная незавершена . Вы можете помочь Википедии, расширив ее .

[1] Nesterov, Yurii (2018). Lectures on Convex Optimization (2 ed.). Cham, Switzerland: Springer. p. 56. ISBN 978-3-319-91577-7 .

[2] Носедаль, Хорхе; Райт, Стивен (2006). Численная оптимизация (2-е изд.). Нью-Йорк, штат Нью-Йорк: Спрингер. п. 566. ИСБН 0-387-30303-0 .

[3] Вандербей, Роберт Дж. (2001). Линейное программирование: основы и расширения . Клювер. стр. 277–279.

[1]

[2]

[3]