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

В математической формулировке задача нелинейного программирования может быть записана так:

Найти минимум функции f(x), x∈En

при ограничениях

gi(x) ≤ 0, i = 1, …, m (4.18)

где x = (x1, …, xn ) – вектор управляемых параметров; f(x) и gi(x) – нелинейные в общем случае функции.

f(x) → min (max), x∈En, (4.13)

gi(x) ≤ 0, i∈I1, (4.14)

gi(x) = 0, i∈I2, (4.15)

Одним из возможных методов решения задачи (4.13)-(4.15) является метод штрафных функций. Основная идея метода штрафных функций состоит в преобразовании задачи минимизации функции f(x) с соответствующими ограничениями в задачу безусловной минимизации функции ϕ(x) = f(x) + p(x). Функция p(x) называется штрафной. Необходимо, чтобы она «штрафовала» ϕ(x), т.е. увеличивала ее значение при выходе х за границу допустимой области. Тогда, если p(x) возрастает достаточно быстро с выходом x за границу допустимой области, минимум ϕ(x) будет находитсявнутри этой области. Необходимо также, чтобы минимум ϕ(x) совпал с минимумом f(x), если x находится внутри допустимой области. Для этого p(x) должна быть близка кнулю внутри допустимой области.

Существуют различные виды штрафных функций. Одними из самыхраспространенных являются штрафные функции, зависящие от некоторого штрафногопараметра и обладающие следующими свойствами:

– на большей части допустимого множества задачи нелинейного программирования эти функции близки к нулю;

– каждая из них достаточно быстро возрастает либо при приближении изнутри к границе допустимого множества (внутренние или барьерные штрафные функции), либо при выходе за его пределы (внешние штрафные функции);

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

Примером штрафной функции может служить функция, где

Или

где s – штрафной параметр.

(Про штрафной параметр что-то еще говорилось на лекции и при сдаче лабораторных:

Если штрафной параметр слишком мал, то решение может быть найдено за границей допустимой области; если слишком большой, то значения за границей могут стать равны бесконечности и алгоритмы могут не сойтись и не найти решения. Как написать все это по-умному я не знаю)

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

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