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

Данные методы применяются для решения задачи оптимизации в общей постановке, т. е. при наличии как ограничений-неравенств, так и ограничений-равенств. В рассматриваемых методах функции Ф(х, а) выбирают такими, что их значения равны нулю внутри и на границе допустимой области G, а вне ее ‑ положительны и возрастают тем больше, чем сильнее нарушаются ограничения (рис. 7.13). Таким образом, здесь «штрафуется» удаление от допустимой области G.

Рис. 7.13 ‑ Внешняя штрафная функция

Внешняя штрафная функция Ф(х, а) в общем случае может быть определена следующим образом:

(7.69)

Поиск минимума вспомогательной функции F(x, а) можно начинать из произвольной точки. В большинстве случаев она является недопустимой, поэтому траектория спуска располагается частично вне допустимой области. Если минимум целевой функции расположен на границе допустимой области, то эта траектория полностью находится снаружи области G. Перечисленные особенности функции Ф(х, а) определили название данной группы методов. Общий вид внешней штрафной функции:

, (7.70)

где j_j, f _j ‑ функции, определяемые соответственно ограничениями-равенствами и неравенствами исходной задачи нелинейного программирования. Вспомогательная функция F(х, а) при этом имеет форму

(7.71)

Одна из применяемых внешних штрафных функций имеет вид

(7.72)

Здесь (7.73)

Алгоритм метода внешних штрафных функций формулируется так же, как и алгоритм метода внутренних штрафных функций, и обладает аналогичными свойствами. Однако в этом случае не требуется, чтобы начальная точка х[0] G , а последовательность {a_k}, k 1, 2, ..., положительных чисел должна быть монотонно возрастающей.

Анализ методов штрафных функций позволяет сделать следующие выводы об их вычислительных свойствах. В соответствии с методами внутренних штрафных функций ведут поиск решения, не выходя за пределы допустимой области. Это весьма важно в тех случаях, когда целевая функция или ограничения не определены за пределами допустимого множества. Кроме того, прервав вычисления в любой момент времени, мы всегда получим допустимое решение. Однако для задания в качестве начальной некоторой допустимой точки иногда требуется решать задачу, по сложности сравнимую с исходной задачей нелинейного программирования. В этом смысле метод внешних штрафных функций предпочтительнее, так как он обеспечивает решение из любой начальной точки. В результате программирование для ЭВМ алгоритмов внешних штрафных функций существенно упрощается. Общим недостатком методов штрафных функций является сложность вспомогательной функции F(x, a), которая часто имеет овражную структуру. Степень овражности увеличивается с увеличением а. Кроме того, при больших значениях а точность вычислений минимума F(х, а) сильно уменьшается из-за ошибок округления.