Глава 12. МЕТОДЫ ШТРАФНЫХ ФУНКЦИЙ И БАРЬЕРОВ

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

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

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

12.1. ОСНОВЫ МЕТОДОВ ШТРАФНЫХ ФУНКЦИЙ И БАРЬЕРОВ

Методы штрафных функций и барьеров используются для решения задачи НЛП

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

Чтобы решить задачу (12.1) при методы штрафных функций и барьеров учитывают влияние ограничений, модифицируя целевую функцию

Рис. 12.1. Бесконечно большой штраф.

В качестве иллюстрации этого подхода рассмотрим функцию

где — допустимое множество.

Комбинируя составляем функцию

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

Таким образом, задача (12.1) преобразована в эквивалентную задачу без ограничений.

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

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

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

Рис. 12.2. Представление функции

этих функций, скажем непрерывных и дифференцируемых, эти методы обходят вычислительные трудности, связанные с использованием или

Идея метода штрафных функций. Чтобы построить метод штрафных функций, рассмотрим сначала частный случай штрафной функции

Очевидно, что

При этом, если то функция аппроксимирует функцию при (рис. 12.2).

Метод штрафных функций использует последовательность для которой для всех

Определим как точку , максимизирующую

(мы полагаем, что эти существуют). Тогда

Задача (12.1) с помощью метода штрафных функций решается следующим образом. При заданном где обычно выбирается равным 1, определяем используя какой-нибудь метод максимизации для задачи без ограничений. Далее, воспользовавшись определяем опять применяя метод максимизации функции без ограничений.

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

Показаны точки и оптимальная точка х. Ясно, что

Таким образом, вырабатывается последовательность Как будет доказано, предел любой сходящейся подпоследовательности будет решением задачи (12.1) (рис. 12.3).

При строгом доказательстве используется более общая форма функции , чем та, которая дана в выражении (12.8). Отметим также, что последовательное вычисление по может быть нетрудным. Действительно, предположим, что только что вычислено. Если не намного меньше то точка должна быть недалеко от

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

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

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

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

Рассмотрим функцию

и последовательность такую, что

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

Рис. 12.4. Метод барьеров.

что максимизирует на Дальше мы докажем, что любая предельная точка этой последовательности является оптимальной для задачи (12.1) (рис. 12.4).

Несмотря на то, что задача максимизации на является задачей с ограничениями, решая ее специальным образом, мы можем фактически пользоваться методами максимизации для задач без ограничений. Для определения отправляемся в поиск от некоторой которой . Тогда, так как при приближении точки к границе допустимой области точки, вырабатываемые методом максимизации для задач без ограничений, будут оставаться внутри допустимой области и определять При этом будет удовлетворять условиям .

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

Завершив на этом пояснение идей метода штрафных функций и метода барьеров, мы приступаем к подробному обсуждению и обоснованию метода штрафных функций.