Метод барьерных функций excel
Обновлено: 02.07.2024
Функция является штрафной. Необходимо, чтобы при нарушении ограничений она «штрафовала» функцию Z, т.е. увеличивала её значение.В этом случае минимум функции Z будет находиться внутри области ограничений. Функция , удовлетворяющая этому условию, может быть не единственной. Задачу минимизации можно сформулировать следующим образом:
Функцию удобно записать следующим образом:
где r – положительная величина.
Тогда функция принимает вид
Если х принимает допустимые значения, т.е. значения, для которых , то Z принимает значения, которые больше соответствующих значений (истинной целевой функции данной задачи), и разность можно уменьшить за счет того, что r может быть очень малой величиной. Но если х принимает значения, которые хотя и являются допустимыми, но близки к границе области ограничений, и по крайней мере одна из функций близка к нулю, тогда значения функции , и следовательно значения функции Z станут очень велики. Таким образом, влияние функции состоит в создании «гребня с крутыми краями» вдоль каждой границы области ограничений. Следовательно, если поиск начнется из допустимой точки и осуществляется поиск минимума функции без ограничений, то минимум, конечно, будет достигаться внутри допустимой области для задачи с ограничениями. Полагая r достаточно малой величиной, для того чтобы влияние было малым в точке минимума, мы можем сделать точку минимума функции без ограничений совпадающей с точкой минимума задачи с ограничениями.
Алгоритм метода штрафных функций
Пусть имеется следующая задача: Минимизировать при ограничениях ,.
Начальный этап Выбрать в качестве константы остановки, начальную допустимую точку ∈, для которой , , скаляр и . Положить k=1 и перейти к основному этапу.
Основной этап. k-я итерация.
Первый шаг. При исходной точке решить следующую задачу безусловной оптимизации:
- параметр, значения которого убывают с каждой итерации при ; - положительные весовые коэффициенты.
Примерами штрафных функций являются:
1) обратная функция
2) логарифмическая функция
Положить равным оптимальному решению задачи минимизации и перейти ко второму шагу.
Минимизация штрафной функцию может быть выполнена любым методом безусловной оптимизации, например, градиентным.
Если , то остановиться. Решение является искомым.
В противном случае положить . Изменить и перейти к первому шагу (k+1)-й итерации.
Метод барьерных функций
Изложение метода
Метод штрафных функций относится к группе методов внутренней точки, т.е. он начинает работать с допустимой точки и генерирует последовательность допустимых точек . Метод барьерных функций, наоборот, относится к группе методов внешней точки, он начинает поиск с недопустимой точки и генерирует последовательность недопустимых решений, которая приближается к оптимальному решению извне допустимой области.
Пусть имеется задача минимизировать при ограничениях
В частности, для искомых функций – ограничений целесообразно использовать барьерную функцию следующего вида:
- непрерывные функции, которые удовлетворяют условиям: , если и , если , , если и , если .
Типичными являются следующие выражения для функций :
, , где р – целое положительное число.
Далее от исходной задачи переходим к задачи безусловной оптимизации вспомогательной функции: минимизировать , где - штрафной коэффициент.
Пусть α– непрерывная функция. Обозначим .
Подход, связанный с барьерной функцией состоит в решении задачи вида:
максимизировать при ограничении
Алгоритм метода барьерных функций
Пусть имеется следующая задача:
Минимизировать при ограничениях ,, где функции .
Начальный этап Выбрать Выбрать начальную точку , параметр штрафа и число . Положить k=1 и перейти к основному этапу.
Основной этап. k-я итерация.
Первый шаг. При начальной точке и параметре штрафа решить следующую задачу:
Положить равным оптимальному решению задачи и перейти ко второму шагу.
Если , то остановиться.
В противном случае положить . Заменить k на k+1 и перейти к первому шагу.
Пример реализации
Рассмотрим задачу Розена-Сузуки и реализуем её решение с помощью метода штрафных функций. Задача Розена-Сузуки заключается в следующем: необходимо минимизировать функцию
со следующими ограничениями
Ниже приведена таблица промежуточных результатов алгоритма.
| Число итераций | Значение миимизируемой функции | Координаты первой точки | Координаты второй точки | Координаты третьей точки | Координаты четвертой точки |
|---|---|---|---|---|---|
| 0 | nfmin=-43.739500 | x1=-0.010000 | x2=0.990000 | x3=1.990000 | x4=-0.990000 |
| 10 | nfmin=-43.762449 | x1=-0.009498 | x2=0.990302 | x3=1.991304 | x4=-0.990502 |
| 20 | nfmin=-43.785381 | x1=-0.008996 | x2=0.990604 | x3=1.992607 | x4=-0.991004 |
| 30 | nfmin=-43.808298 | x1=-0.008494 | x2=0.990906 | x3=1.993910 | x4=-0.991506 |
| 40 | nfmin=-43.831199 | x1=-0.007993 | x2=0.991208 | x3=1.995212 | x4=-0.992007 |
| 50 | nfmin=-43.854084 | x1=-0.007491 | x2=0.991509 | x3=1.996514 | x4=-0.992509 |
Оптимальную точку мы получаем на 114й итерации с оптимальным значением функции
Рекомендация программисту
Использование штрафных функций для решения задач связано с определенной вычислительной трудностью. Прежде всего поиск может начинаться с допустимой точки х, для которой , .Для некоторых задач находить такую точку довольно сложно. Кроме того, вследствие использования в алгоритме оптимизации дискретных шагов около границы возможен шаг, который выводит за границы допустимой области. Он приводит к уменьшению значений функции , т.е. к фиктивному успеху. Таким образом, нужна явная проверка допустимости каждой последующей точки, для чего на каждой итерации необходимо вычислять значения функции ,.
На эффективность метода барьерных функций существенно влияют выбор начального значения и метод сокращения значений в процессе минимизации, а также выбор весовых коэффициентов . Если в функции значение , выбирают слишком малым, то уже на начальной стадии процесса приходят к минимуму функции , который вряд ли окажется вблизи действительного условного минимума в точке ,. С другой стороны, если значение , выбирается слишком большим, то на первых итерациях вычислительного процесса текущая точка неизбежно окажется слишком далеко за пределами допустимой области, и поиск из-за необходимости возврата в пределы допустимой области окажется весьма затяжным.
В данном подразделе рассматриваются две группы методов: метод внешних штрафов и метод внутренних штрафов (метод барьерных функций).
Метод внешних штрафов
Опишем метод внешних штрафов [ 16] решения задачи условной оптимизации (2.1). Вводится следующая штрафная функция
где к. »1, у »1 и 0( |/ .) имеет вид
Будем искать минимум функции F(z,knу ) по переменным z при
фиксированных kh у,. Можно показать, что при выполнении некоторых условий решение задачи безусловной оптимизации
будет стремиться к решению задачи условной оптимизации (2.1) при —»оо и у . —>оо [16]. Обсудим смысл введения функции F(z,knу.).
Если во время поиска минимума в задаче (2.25) текущая точка нарушит ограничения задачи (2.1)
то при достаточно больших kh у, функция F резко увеличится. Однако поскольку мы ищем минимум функции F, большие нарушения ограничений будут предотвращаться. Таким образом, поиск минимума функции F будет проводиться в окрестности допустимой области D. Таким образом, задача условной минимизации (2.1) сводится к задаче безусловной минимизации (2.26) с целевой функцией (2.25). Для ее решения можно использовать любой из рассмотренных методов безусловной минимизации.
Из вышесказанного становится понятным название метода. Метод называется методом внешних штрафов, так как целевая функция резко увеличивается (штрафуется) при выходе поисковой точки из допустимой области.
К сожалению, описанный подход имеет существенный недостаток. При больших kj и у. функция F(z,k;,у является «овражной» функцией. «Овражной» называется функция, у которой по одним направлениям производные по направлениям велики, а по другим малы. Известно, что при минимизации таких функций возникают трудности при использовании любых методов безусловной минимизации. Чтобы частично избежать этих трудностей, используют следующую стратегию. Вначале проводят минимизацию функции F(z,A,,y ) при сравнительно
небольших значениях параметров к: и у . После этого (на втором шаге) штрафные коэффициенты увеличиваются, и минимизация функции F(z,knу.) проводится опять. При этом в качестве начальных приближений для поисковых переменных z используются оптимальные значения переменных z, полученных при первой минимизации. На следующем шаге штрафные коэффициенты опять увеличиваются и т.д. Итак, процедура решения задачи (2.1) опять оказывается двухуровневой, как и в случае метода множителей Лагранжа: минимизация функции F по переменным z соответствует первому уровню, а увеличение штрафных коэффициентов [/с,,у.] соответствует второму (верхнему) уровню. На
начальных шагах поиска коэффициенты [А,, у ] имеют небольшие значения, поэтому функция F(z,k;,уне является «овражной». Однако на последующих шагах с увеличением коэффициентов [А,, у ] функция Ft,yj) становится все более «овражной». В то же время
в этот момент мы будем иметь уже хорошее приближение к решению.
Рассмотрим геометрическую интерпретацию метода штрафов для случая, когда в задаче (2.1) имеется только одно ограничение типа равенства [см. формулу (2.10)]. В этом случае на нижнем уровне выполняется минимизация функции
где к и) является штрафным коэффициентом на /'-м шаге.
Линии уровней этой функции имеют вид
где а' есть некоторая постоянная.
В пространстве Y кривая (2.27) является параболой (рис. 2.4), ось которой совпадает с осью ординат пространства Y. Пусть при a J = а 1 * парабола соответствует точке С, в которой парабола (2.27) касается границы oQ области Q.. Аналогично методу множителей Лагранжа можно показать, что минимум функции F (,) будет совпадать с точкой С‘. Увеличим штрафной коэффициент до к и ' [) (А (,+1) > к иу ). Этому штрафному коэффициенту соответствует более крутая парабола (2.27). Из геометрического представления видно, что если ? (,+1) > к и) , то точка касания параболы с границей 0 функция />(z,p) стремится к бесконечности. В данном случае решается задача
При этом предполагается, что начальная точка лежит внутри допустимой области (ij (z0) z*. Поэтому, если будем решать задачу безусловной минимизации (2.29) для последовательности значений р, >р, >. рд. >. при рд —>0, то в пределе получим решение задачи (2.1). Опять решение задачи условной минимизации сводится к решению последовательности задач безусловной минимизации. Если в задаче имеется ограничение типа равенства
Читайте также: