Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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

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

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

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

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

Рассмотрим метод штрафных функций. Этот метод предназначен для решения задач нелинейного программирования с ограничениями, как в форме неравенств, так и в форме равенств. Будем рассматривать задачу:

¦(x) ® min; x Î X Ì Eⁿ, (8.17)

g_i (x) £ 0, i = 1: m, (8.18)

в которой все функции ¦, g_i считаются непрерывными на всем пространстве Eⁿ. Функция P (x), определенная и непрерывная на Eⁿ, называется штрафной функцией, если выполняются следующие условия:

1.) P (x) = 0 " x Î X,

2.) P (x) > 0 " x Ï X.

Введем обобщенную функцию (k = 1,2,…)

¦(x, k) = ¦(x) + kP (x), (8.19)

где k – некоторое положительное число, называемое коэффициентом штрафа. В этом методе функции P (x) подбираются так, чтобы при больших k функция ¦(x, k) мало отличалась от ¦(x) при " x Î X и быстро возрастала при удалении точки x Ï X от допустимого множества, т.е. функция P (x) назначает положительный «штраф» за выход за пределы допустимого множества X, тогда как для точек из X «штраф» отсутствует.

Хорошо изучены штрафные функции следующих видов

(8.20)

Алгоритм оптимизационного поиска по методу штрафных функций состоит в следующем. Рассматривается некоторая неограниченная, монотонно возрастающая последовательность { k }, k = 1,2,… положительных чисел. Для первого числа k ₁(k = 1) этой последовательности находится точка x ^(1)* , доставляющая минимум функции (8.19). Найденная точка x ^(1)* используется как начальное приближение для решения задачи поиска минимума функции ¦(x, k ₂), где k ₂ > k ₁ и т.д. Таким образом решается последовательность задач минимизации функции ¦(x, k), k = 1,2….

Поскольку для бесконечно возрастающей последовательности { k } локальные минимумы приближаются к допустимой области, то последовательность { x ^{( k )*}}, k = 1,2,…, сходится к локальному оптимуму функции ¦(x), расположенному внутри или на границе допустимой области.

В качестве критерия достижения требуемой точности решения задачи может служить неравенство || x ^{( k )} – x ^{( k /2)}|| £ e, где e - число, характеризующее точность, k – четное число. При его выполнении полагают x ^* » x ^{( k )} , ¦ ^* = ¦(x ^{( k )}).

Для решения задач (8.19) можно использовать методы безусловной минимизации. Если в задаче (8.17) выпуклая квадратичная функция, а ограничения (8.18) линейные функции, то точное решение вспомогательной задачи (8.19) можно найти из системы линейных уравнений ¶¦(x, k)/¶ x_j = 0, j = 1: n, определяющих стационарную точку функции ¦(x, k). Поскольку точки x ^{( k )*} расположены вне допустимой области, поэтому метод штрафных функций называют также методом внешней точки.