Штрафной метод - Penalty method

Методы наказания это определенный класс алгоритмы для решения ограниченная оптимизация проблемы.

Метод штрафа заменяет задачу оптимизации с ограничениями серией задач без ограничений, решения которых идеально сходятся к решению исходной задачи с ограничениями. Неограниченные проблемы образуются путем добавления члена, называемого штрафная функция, в целевая функция который состоит из параметр штрафа умноженное на меру нарушения ограничений. Мера нарушения отлична от нуля, когда ограничения нарушаются, и равна нулю в области, где ограничения не нарушаются.

пример

Допустим, мы решаем следующую ограниченную задачу:

${displaystyle min f (mathbf {x})}$

при условии

${displaystyle c_ {i} (mathbf {x}) leq 0 ~ forall iin I.}$

Эта проблема может быть решена в виде серии задач безусловной минимизации

${displaystyle min Phi _ {k} (mathbf {x}) = f (mathbf {x}) + sigma _ {k} ~ sum _ {iin I} ~ g (c_ {i} (mathbf {x}))}$

где

${displaystyle g (c_ {i} (mathbf {x})) = max (0, c_ {i} (mathbf {x})) ^ {2}.}$

В приведенных выше уравнениях ${displaystyle g (c_ {i} (mathbf {x}))}$ это внешняя штрафная функция в то время как ${displaystyle sigma _ {k}}$ являются штрафные коэффициенты. В каждой итерации k метода увеличиваем штрафной коэффициент ${displaystyle sigma _ {k}}$ (например, с коэффициентом 10), решите неограниченную задачу и используйте решение в качестве начального предположения для следующей итерации. Решения последовательных задач без ограничений в конечном итоге сведутся к решению исходной задачи с ограничениями.

Практическое применение

Сжатие изображения алгоритмы оптимизации могут использовать штрафные функции для выбора того, как лучше всего сжать цветовые зоны до единичных репрезентативных значений.^[1][2]

Барьерные методы

Барьерные методы представляют собой альтернативный класс алгоритмов ограниченной оптимизации. Эти методы также добавляют к целевой функции член типа штрафа, но в этом случае итерации вынуждены оставаться внутри допустимой области, и существует барьер, смещающий итерации, чтобы они оставались вдали от границы допустимой области.

Смотрите также

• Барьерная функция
• Метод внутренней точки
• Дополненный лагранжев метод

использованная литература

Смит, Элис Э .; Койт Дэвид В. Штрафные функции Справочник по эволюционным вычислениям, раздел C 5.2. Издательство Оксфордского университета и издательство Института физики, 1996.

Курант, Р. Вариационные методы решения задач равновесия и колебаний.. Бык. Амер. Математика. Soc., 49, 1–23, 1943.

Wotao, Ю. Алгоритмы оптимизации для оптимизации с ограничениями. Департамент математики, UCLA, 2015.