3. Методы решения задач условной оптимизации

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

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

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

;

, .

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

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

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

4.3.1. Метод последовательной безусловной оптимизации

Задачу

min

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

можно свести к безусловной задаче

min,

введя штрафную функцию вида , где- коэффициент штрафа.

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

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

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

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

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

4.3.2.Метод скользящего допуска

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

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

, ;

, .

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

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

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

при одном, но “укрупненном ” ограничении:

,

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

,

,

где - величина, характеризующая размер исходного многогранника;

- число ограничений типа равенства;

, число степеней свободы.

Здесь

и .

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

,

где

Таким образом, для любого допустимогоидля любого, не являющегося допустимым. Четкое различие между допустимыми и недопустимыми точками устанавливается следующим соотношением:

1. допустима, если ;

2. почти допустима, если ;

3. недопустима, если .

Таким образом, область квазидопустимости определяется соотношением

.

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

Общая схема работы алгоритма скользящего допуска выглядит следующим образом:

1 этап.

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

2. этап.

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

Работа алгоритма заканчивается при двух обстоятельствах:

• когда ; в этом случае поиск считается завершенным и квалифицируется как успешный;

• когда не удается найти допустимую или почти допустимую точку; в этом случае поиск начинается из новой стартовой точки.

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

Другим преимуществом стратегии скользящего допуска является то, что, оказывается удобно использовать в качестве критерия окончания процесса поиска.

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

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

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