Исследование методов штрафных функций

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

     2.1.1 Алгоритм метода  барьерных поверхностей

     Пусть задача нелинейного программирования имеет следующий вид:

     минимизировать 

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

     Начальный этап. Выбрать  в качестве константы остановки, начальную допустимую точку , для которой , , скаляр и . Положить и перейти к основному этапу.

     Основной  этап. k-я итерация. Первый шаг. При исходной точке решить следующую задачу безусловной оптимизации:

     минимизировать  

      ,(2.9) 

     где описывается одним из выражений (2.8).

     Положить равным оптимальному решению задачи (2.9) и перейти ко второму шагу.

     Второй  шаг. Если , то остановиться. Решение является искомым. В противном случае положить . Изменить и перейти к первому шагу (k+1)-й итерации.

     Пример. Рассмотрим следующую задачу:

     минимизировать 

     при условии .

     Решим ее методом барьерных поверхностей с барьерной функцией . В табл. 6.7 приведены результаты вычислений. Вычисления начались при n=10, а безусловная оптимизация функции начиналась с точки . В качестве начального значения параметра выбрано . После шести итераций получена точка для которой и выполнение алгоритма остановлено. Можно непосредственно проверить, что эта точка близка к оптимальной. Учитывая, что уменьшаются, по табл. 6.7 легко заметить, что - функции, которые не уменьшаются от , а - не увеличивается от .

     Кроме того, стремится к нулю.

     Таблица 1

 

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

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

     

     Рисунок – 4 

     На  рисунке 4 представлена функция P вида 

       

     для трех различных значений: а) ; б) ; в) , где легко увидеть влияние барьерных поверхностей при больших значениях . Штриховой линией изображена траектория поиска. 

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

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

     Пусть, как и выше, имеется задача нелинейного  программирования:

     минимизировать  

       (2.10) 

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

      , (2.11)

      . (2.12) 

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

     В частности, для ограничений типа (2.11), (2.12) целесообразно использовать штрафную функцию следующего вида:

      , (2.13) 

     где  R1, R2 - непрерывные функции, которые удовлетворяют условиям:

       , если и , если ,

       , если и , если .

     Типичными являются следующие выражения для  функций R1, R2: 

      ; , 

     где p - целое положительное число.

     Таким образом, штрафная функция  обычно имеет вид 

      ,(2.14) 

     Далее от задачи нелинейного программирования (2.10)-(2.12) переходим к задаче безусловной  оптимизации вспомогательной функции:

     минимизировать  

      , (2.15) 

     где - штрафной коэффициент.

     Пусть - непрерывная функция вида (2.13). Обозначим 

      (2.16) 

     Подход, связанный со штрафной функцией, состоит  в решении задачи вида:

     максимизировать (2.17)

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

     Справедлива следующая теорема, которая обосновывает этот метод [1].

     Теорема. Пусть задача нелинейного программирования задана в виде (2.10)-(2.12), где - непрерывные на Rn функции.

     Предположим, что задача имеет допустимые решения  и пусть - непрерывная штрафная функция вида (2.13). Предположим также, что для любого r существует решение xr, задачи минимизации вспомогательной функции и все xr принадлежат некоторому компактному подмножеству X. Тогда справедливо следующее уравнение: 

      (2.18) 

     где определяется в соответствии с (2.16).

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

     Эта теорема служит обоснованием метода штрафных функций и из нее следует, что оптимальное значение xr может быть сделано наиблизким к допустимой области при довольно большом r. Кроме того, выбрав r довольно большим, значение можно сделать как угодно близким к оптимальному значению целевой функции исходной задачи f(x).

     2.2.1 Алгоритм метода  штрафных функций

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

     Итак, пусть имеем задачу нелинейного  программирования:

     минимизировать  f(x)

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

     где функции  непрерывны.

     Начальный этап. Выбрать  . Выбрать начальную точку x1, параметр штрафа и число . Положить и перейти к основному этапу.

     Основной  этап. Первый шаг. При начальной точке  xk и параметре штрафа решить следующую задачу:

     минимизировать 

      ,(2.19) 

     где - целое.

     Положить  xk+1 равным оптимальному решению этой задачи и перейти ко второму шагу.

     Второй  шаг. Если , то остановиться. В противном случае положить . Заменить k на k+1 и перейти к первому шагу.

     Пример. Рассмотрим следующую задачу:

     минимизировать  ,

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

     В качестве штрафной функции  выберем . Тогда на k-й итерации при заданном значении параметра rk необходимо решать следующую задачу: 

     минимизировать  , 

     где .

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

     Процесс остановлен после четырех итераций, где  . Но, чтобы убедиться, что последовательность стремится к нулю, выполнена еще одна итерация и найдено x6. Можно убедиться, что в точке выполняются условия Куна-Таккера с заданной точностью.

     Таблица 2

 

 

      ЗАКЛЮЧЕНИЕ 

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