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

Основная идея методов последовательной безусловной оптимизации состоит в преобразовании задачи нелинейного программирования

f(x) ≥ min, х∈U (4.16)

где допустимое множество U не совпадает со всем пространством E_n, в последовательность задач безусловной минимизации

fk(x) = f(x) + ϕ_k(x) ≥ min, x∈En, k = 1, 2,…, (4.17)

где ϕ_k(x) – функции, которые с ростом k во все большей степени учитывают ограничения, определяющие допустимое множество U исходной задачи. В качестве приближенного решения исходной задачи берется решение x^k вспомогательной задачи (4.17), соответствующее достаточно большому значению k.

При формировании задачи (4.17) различают метод штрафных функций и метод барьерных функций. В первом, функции ϕ_k(x) подбираются так, чтобы при больших k функция fk(x) мало отличалась при х∈Uи быстровозрасталаприудаленииточкихотграницы U допустимого множества. В методе барьерных функций функции ϕ_k(x)выбираются так, что при больших k функции fk(x) мало отличаются от f(x) во внутренних точках х допустимого множества U и, в то же время при приближении точки х∈Uк границе множества U эти функции неограниченно возрастают.

Метод штрафных функций является одним из наиболее простых и в то же время наиболее эффективным методом решения задачи минимизации с ограничениями. Для минимизации вспомогательной целевой функции fk(x) могут быть использованы мощные методы безусловной минимизации. Метод барьерных функций идейно близок к методу штрафных функций. Его иногда называют методом внутренних штрафов, так как поиск точки минимума ведется из внутренней точки области U и величина штрафа возрастает при приближении к границе U изнутри.