Метод штрафов

Методы штрафов (методы штрафных функций) — методы, широко используемые для решения технических и экономических задач оптимизации.

Эффективны если штрафная функция естественно вытекает из технического смысла задачи.

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

Довольно часто применяются как в теоретических исследованиях, так и при разработке алгоритмов.

Хорошо подходит для приближённой оценки глобального минимума многоэкстремальных задач в сложной допустимой области.

Этот подход может быть использован не только как вычислительный метод, но и как метод «мягкого» описания систем. Он позволяет заменять задачи со сложными системами ограничений задачами с простыми системами ограничений или вовсе без них, а также решать задачи с несовместными системами ограничений, получая практически приемлемые решения.

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

История

Строго математически метод штрафа впервые использовал американский математик Р. Курант в 1943 г. (для изучения движения в ограниченной области).

Методы широко применялись для решения задач локальной минимизации в 60-е годы. Одной из наиболее популярных была программа SUMT (разработчики — американцы Фиакко и Мак Кормик).

Недостатки

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

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