Метод штрафа

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

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

Описание

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

\min _{x}f(\mathbf {x} )

при условии

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

Эту задачу можно решить как серию задач неограниченной минимизации.

\min f_{p}(\mathbf {x} ):=f(\mathbf {x} )+p~\sum _{i\in I}~g(c_{i}(\mathbf {x} ))

где

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

В приведенных выше уравнениях $g(c_{i}(\mathbf {x} ))$ – внешняя штрафная функция , а $p$ это штрафной коэффициент . Когда штрафной коэффициент равен 0, f _p = f . На каждой итерации метода увеличиваем штрафной коэффициент $p$ (например, в 10 раз), решить задачу без ограничений и использовать решение в качестве первоначального предположения для следующей итерации. Решения последовательных задач без ограничений будут асимптотически сходиться к решению исходной задачи с ограничениями.

Обычными штрафными функциями в ограниченной оптимизации являются квадратичная штрафная функция и линейная штрафная функция с мертвой зоной. ^[1].

Конвергенция

Сначала рассмотрим набор глобальных оптимизаторов исходной задачи X*. ^[2]^{: Thm.9.2.1}Предположим, что цель f имеет ограниченные множества уровня и что исходная задача выполнима. Затем:

Для каждого штрафного коэффициента p множество глобальных оптимизаторов штрафной задачи X _p * непусто.
Для каждого ε>0 существует штрафной коэффициент p такой, что множество X _p * содержится в ε-окрестности множества X*.

Эта теорема полезна в основном, когда f _p выпукла, поскольку в этом случае мы можем найти глобальные оптимизаторы f _p .

Вторая теорема рассматривает локальные оптимизаторы. ^[2]^{: Thm.9.2.2} Пусть x* — невырожденный локальный оптимизатор исходной задачи («невырожденный» означает, что градиенты активных ограничений линейно независимы и выполнено достаточное условие оптимальности второго порядка). Тогда существует окрестность V* точки x* и некоторый p ₀ >0, такие что для всех p > p ₀ штрафная цель f _p имеет ровно одну критическую точку в V* (обозначаемую x*(p)) , а x*( p ) приближается к x* при p →∞. Кроме того, целевое значение f (x*( p )) слабо увеличивается с ростом p .

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

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

Преимущество метода штрафов заключается в том, что, как только у нас есть штрафная цель без ограничений, мы можем использовать любой метод неограниченной оптимизации для ее решения. Недостаток состоит в том, что с ростом штрафного коэффициента p безусловная задача становится плохо обусловленной - коэффициенты очень велики, и это может привести к числовым ошибкам и медленной сходимости безусловной минимизации. ^[2]^{: Под.9.2}

См. также

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

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

Другие алгоритмы нелинейного программирования:

Ссылки

^ Бойд, Стивен; Ванденберге, Ливен (2004). «6.1». Выпуклая оптимизация . Издательство Кембриджского университета. п. 309. ИСБН 978-0521833783 .
^ Перейти обратно: ^а ^б ^с Немировский и Бен-Тал (2023). «Оптимизация III: Выпуклая оптимизация» (PDF) .
^ Галар, М.; Хурио, А.; Лопес-Молина, К.; Патернэн, Д.; Санс, Дж.; Бустинс, Х. (2013). «Функции агрегирования для объединения цветовых каналов RGB в стереосопоставлении». Оптика Экспресс . 21 (1): 1247–1257. дои : 10.1364/oe.21.001247 . hdl : 2454/21074 . ПМИД 23389018 .
^ «Исследователи восстанавливают изображение, используя версию, содержащую от 1 до 10 процентов информации» . Phys.org (Omicron Technology Limited) . Проверено 26 октября 2013 г.

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

Коэльо, AC [1] : Теоретические и численные методы обработки ограничений, используемые с эволюционными алгоритмами: обзор современного уровня техники. Вычислить. Методы Прикл. Мех. англ. 191(11-12), 1245-1287

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

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

[1] Бойд, Стивен; Ванденберге, Ливен (2004). «6.1». Выпуклая оптимизация . Издательство Кембриджского университета. п. 309. ИСБН 978-0521833783 .

[:0-2] Перейти обратно: ^а ^б ^с Немировский и Бен-Тал (2023). «Оптимизация III: Выпуклая оптимизация» (PDF) .

[3] Галар, М.; Хурио, А.; Лопес-Молина, К.; Патернэн, Д.; Санс, Дж.; Бустинс, Х. (2013). «Функции агрегирования для объединения цветовых каналов RGB в стереосопоставлении». Оптика Экспресс . 21 (1): 1247–1257. дои : 10.1364/oe.21.001247 . hdl : 2454/21074 . ПМИД 23389018 .

[4] «Исследователи восстанавливают изображение, используя версию, содержащую от 1 до 10 процентов информации» . Phys.org (Omicron Technology Limited) . Проверено 26 октября 2013 г.

[1]

[2]

[3]

[4]