Методы штрафных функций

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

Общая формулировка задачи следующая. Найти min F(x) при ограничениях

где все или часть функций-ограничений c_j(x) могут быть нелинейны.

Идея метода штрафных функций, называемого также методом внешней точки, состоит в таком преобразовании целевой функции, чтобы в допустимой области ее значения не изменились, а за пределами допустимой области были очень велики по сравнению с исходной F(x). Тогда мини­мум новой функции и минимум исходной будут близки. Такое преобразование целевой функции может выполняться различными способами. Один из обычных приемов состоит в том, что к исходной F(x) прибавляется сумма штрафов g_j(x) за нарушение ограничений. Если в текущей точке х j-oe ограничение выполнено (т.е. c_j(x) <= 0), то штраф равен нулю, иначе, чем больше нарушение, тем больше штраф.

Часто принимают в качестве штрафов функции

Такая функция представляет собой квадрат невязки в j-ом ограничении, а общий штраф равен сумме штрафов. Так что преобразованная функция имеет вид

(2.13)

Далее решается задача поиска безусловного минимума Ф(х). Если взять коэффициент k_n очень большим, то теоре­тически минимумы Ф(х) и F(x) близки. Но этого делать нельзя, так как введение штрафа порождает овраг. В на­правлениях вдоль границ ОДР функция меняется медленно, но при малом изменении невязок в ограничениях функция меняется очень сильно. В такой ситуации методы безуслов­ной оптимизации работают плохо. Поэтому сначала реша­ется задача с малым значением коэффициента штрафа (на­пример, k₁ = 1), полученное решение используется как на­чальное приближение для следующей задачи с к₂ = 2, затем решается задача с к₃ = 4 и так далее при все большем значе­нии к. Фактически решается последовательность задач. Процесс останавливается, когда ограничения выполнены с требуемой точностью. Последняя точка минимума считает­ся решением исходной задачи.

Если в исходной системе были ограничения-равенства, то штрафуются как положительные, так и отрицательные значения c_j(x), т.е. g_j(x) = с_j²(х).

Естественно, что в самом лучшем случае метод может дать точку, близкую к одному из локальных минимумов F(x).