Участник:Айнагуль Джумабекова
Материал из MachineLearning.
Строка 115: | Строка 115: | ||
::<tex> 10 -x_1^2-2x_2^2-x_3^2-2x_4^2+x_1-x_4>0</tex> | ::<tex> 10 -x_1^2-2x_2^2-x_3^2-2x_4^2+x_1-x_4>0</tex> | ||
::<tex>5 - 2x_1^2 - x_2^2 - x_3^2 - 2x_1 + x_2 + x_4>0</tex> | ::<tex>5 - 2x_1^2 - x_2^2 - x_3^2 - 2x_1 + x_2 + x_4>0</tex> | ||
+ | |||
+ | Ниже приведена таблица промежуточных результатов алгоритма. | ||
+ | {| class="wikitable" | ||
+ | |- | ||
+ | ! Число итераций | ||
+ | ! Значение миимизируемой функции <tex>f(x)</tex> | ||
+ | ! Координаты первой точки <tex>x_1</tex> | ||
+ | ! Координаты второй точки <tex>x_2</tex> | ||
+ | ! Координаты третьей точки <tex>x_3</tex> | ||
+ | ! Координаты четвертой точки <tex>x_3</tex> | ||
+ | |- | ||
+ | | 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 | ||
+ | |} | ||
+ | Оптимальную точку <tex>x^*=(0,1,2,-1)</tex> мы получаем на 114й итерации с оптимальным значением функции <tex>f(x^*)=-44</tex> | ||
==Рекомендация программисту== | ==Рекомендация программисту== |
Версия 14:59, 26 декабря 2008
Содержание |
Метод штрафных функций
Изложение метода
Основная задача метода штрафных функций состоит в преобразовании задачи минимизации функции
с соответствующими ограничениями, наложенными на х, в задачу поиска минимума без ограничений функции
Функция является штрафной. Необходимо, чтобы при нарушении ограничений она «штрафовала» функцию Z, т.е. увеличивала её значение.В этом случае минимум функции Z будет находиться внутри области ограничений. Функция , удовлетворяющая этому условию, может быть не единственной. Задачу минимизации можно сформулировать следующим образом:
- минимизировать функцию
при ограничениях .
Функцию удобно записать следующим образом:
где r – положительная величина.
Тогда функция принимает вид
- .
Если х принимает допустимые значения, т.е. значения, для которых , то Z принимает значения, которые больше соответствующих значений (истинной целевой функции данной задачи), и разность можно уменьшить за счет того, что r может быть очень малой величиной. Но если х принимает значения, которые хотя и являются допустимыми, но близки к границе области ограничений, и по крайней мере одна из функций близка к нулю, тогда значения функции , и следовательно значения функции Z станут очень велики. Таким образом, влияние функции состоит в создании «гребня с крутыми краями» вдоль каждой границы области ограничений. Следовательно, если поиск начнется из допустимой точки и осуществляется поиск минимума функции без ограничений, то минимум, конечно, будет достигаться внутри допустимой области для задачи с ограничениями. Полагая r достаточно малой величиной, для того чтобы влияние было малым в точке минимума, мы можем сделать точку минимума функции без ограничений совпадающей с точкой минимума задачи с ограничениями.
Алгоритм метода штрафных функций
Пусть имеется следующая задача: Минимизировать при ограничениях ,.
Начальный этап Выбрать в качестве константы остановки, начальную допустимую точку ∈, для которой , , скаляр и . Положить k=1 и перейти к основному этапу.
Основной этап. k-я итерация.
Первый шаг. При исходной точке решить следующую задачу безусловной оптимизации:
минимизировать, где
- параметр, значения которого убывают с каждой итерации при ; - положительные весовые коэффициенты.
Примерами штрафных функций являются:
1) обратная функция
2) логарифмическая функция
Положить равным оптимальному решению задачи минимизации и перейти ко второму шагу.
Минимизация штрафной функцию может быть выполнена любым методом безусловной оптимизации, например, градиентным.
Второй шаг
Если , то остановиться. Решение является искомым.
В противном случае положить . Изменить и перейти к первому шагу (k+1)-й итерации.
Метод барьерных функций
Изложение метода
Метод штрафных функций относится к группе методов внутренней точки, т.е. он начинает работать с допустимой точки и генерирует последовательность допустимых точек . Метод барьерных функций, наоборот, относится к группе методов внешней точки, он начинает поиск с недопустимой точки и генерирует последовательность недопустимых решений, которая приближается к оптимальному решению извне допустимой области.
Пусть имеется задача минимизировать при ограничениях
- ,
- ,
В частности, для искомых функций – ограничений целесообразно использовать барьерную функцию следующего вида:
- - непрерывные функции, которые удовлетворяют условиям:
- , если и , если ,
- , если и , если .
Типичными являются следующие выражения для функций :
- ,
- , где р – целое положительное число.
Далее от исходной задачи переходим к задачи безусловной оптимизации вспомогательной функции: минимизировать , где - штрафной коэффициент.
Пусть α– непрерывная функция. Обозначим .
Подход, связанный с барьерной функцией состоит в решении задачи вида:
- максимизировать при ограничении
Алгоритм метода барьерных функций
Пусть имеется следующая задача:
Минимизировать при ограничениях ,, где функции .
Начальный этап Выбрать Выбрать начальную точку , параметр штрафа и число . Положить k=1 и перейти к основному этапу.
Основной этап. k-я итерация.
Первый шаг. При начальной точке и параметре штрафа решить следующую задачу:
минимизировать
- , где
,p - целое.
Положить равным оптимальному решению задачи и перейти ко второму шагу.
Второй шаг
Если , то остановиться.
В противном случае положить . Заменить 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й итерации с оптимальным значением функции
Рекомендация программисту
Использование штрафных функций для решения задач связано с определенной вычислительной трудностью. Прежде всего поиск может начинаться с допустимой точки х, для которой , .Для некоторых задач находить такую точку довольно сложно. Кроме того, вследствие использования в алгоритме оптимизации дискретных шагов около границы возможен шаг, который выводит за границы допустимой области. Он приводит к уменьшению значений функции , т.е. к фиктивному успеху. Таким образом, нужна явная проверка допустимости каждой последующей точки, для чего на каждой итерации необходимо вычислять значения функции ,.
На эффективность метода барьерных функций существенно влияют выбор начального значения и метод сокращения значений в процессе минимизации, а также выбор весовых коэффициентов . Если в функции значение , выбирают слишком малым, то уже на начальной стадии процесса приходят к минимуму функции , который вряд ли окажется вблизи действительного условного минимума в точке ,. С другой стороны, если значение , выбирается слишком большим, то на первых итерациях вычислительного процесса текущая точка неизбежно окажется слишком далеко за пределами допустимой области, и поиск из-за необходимости возврата в пределы допустимой области окажется весьма затяжным.
Список литературы
- Банди Б. Методы Оптимизации. Вводный курс. М.: Радио и связь, 1988.
- http://iasa.org.ua/iso?lang=eng&ch=6&sub=8