Штрафной метод

Штрафные методы - это определенный класс алгоритмов для решения задач оптимизации с ограничениями .

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

Пример [ править ]

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

${\ Displaystyle \ мин е (\ mathbf {х})}$

при условии

${\ Displaystyle c_ {я} (\ mathbf {x}) \ leq 0 ~ \ forall i \ in I.}$

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

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

где

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

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

Практическое применение [ править ]

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

Барьерные методы [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]

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

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

Wotao, Y. Оптимизационные алгоритмы для оптимизации с ограничениями . Департамент математики, Калифорнийский университет в Лос-Анджелесе, 2015.