Штрафной метод - 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]

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

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

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

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

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

1. Галар, М .; Jurio, A .; Lopez-Molina, C .; Paternain, D .; Sanz, J .; Бустинс, Х. (2013). «Функции агрегирования для объединения цветовых каналов RGB в стереорежиме». Оптика Экспресс. 21 (1): 1247–1257. Дои:10.1364 / oe.21.001247. HDL:2454/21074. PMID  23389018.
2. «Исследователи восстанавливают изображение, используя версию, содержащую от 1 до 10 процентов информации». Phys.org (Omicron Technology Limited). Получено 26 октября 2013.

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

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

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