Методы нахождения безусловного и условного экстремума
Курсовой проект - Математика и статистика
Другие курсовые по предмету Математика и статистика
?ача
х(1) = [-8;-9]T;
Т.к. поиск был удачным, переходим к поиску по образцу:
хp(2) = 2х(1) - х(0);
хp (2) = [-7;-8]T f =147
- Исследующий поиск вокруг точки хp (2):
фиксируя х2, даём приращение переменной х1:
х2=-8;х1=-7+1=-6 f = 120<147удача
фиксируя х1, даём приращение переменной х2:
х1=-6; х2=-8+1=-7 f = 115<120удача
х(2) = [-6;-7]T;
Т.к. поиск был удачным, переходим к поиску по образцу:
хp (3) = 2х(2) - х(1);
хp (3) = [-4;-5]T f =63
- Исследующий поиск вокруг точки хp (3):
фиксируя х2, даём приращение переменной х1:
х2=-5;х1=-4+1=-3 f = 45<63удача
фиксируя х1, даём приращение переменной х2:
х1=-3; х2=-5+1=-4 f = 43<45удача
х(3) = [-3;-4]T;
Т.к. поиск был удачным, переходим к поиску по образцу:
хp (4) = 2х(3) - х(2);
хp (4) = [0;-1]T f =7
- Исследующий поиск вокруг точки хp (4):
фиксируя х2, даём приращение переменной х1:
х2=-1;х1=0+1=1 f = 15>7неудача
фиксируя х1, даём приращение переменной х2:
х1=1; х2=-1+1=0 f =9<15удача
х(4) = [1;0]T;
Т.к. поиск был удачным, переходим к поиску по образцу:
хp (5) = 2х(4) - х(3);
хp (5) = [5;4]T f =27.
. Исследующий поиск вокруг точки хp (5):
фиксируя х2, даём приращение переменной х1:
х2=4;х1=5+1=6 f = 36>27неудача
фиксируя х1, даём приращение переменной х2:
х1=6; х2=4+1=5 f =43>27неудача
х2=4-1=3 f =29<27удача
х(5) = [6;3]T;
Т.к. поиск был удачным, переходим к поиску по образцу:
хp (6) = 2х(5) - х(4);
хp (6) = [11;6]T f =70.
В результате исследующего поиска не было достигнуто увеличение значения целевой функции, т.е. значение шага нужно уменьшить. Таким образом, мы получили, что нужно уменьшить приращение для х1 и х2:
? = 1/2=0.5;
Далее необходимо произвести исследующий поиск вокруг точки
х (5) = [6][3], используя новое значение приращения ? =0.5;
Когда ? достигнет какого-то небольшого значения, заданного пользователем, поиск экстремума можно прекратить.
Т.о. мы получили точку х* = [6;3]Т, значение функции в которой
f(x*) = 36. Это значение значительно приближено к значению функции в стационарной точке (1), однако дальнейший ход решения укажет на улучшение результата.
Вывод: Как и в предыдущем методе, необходимо большое количество итераций для достижения точки оптимума целевой функции. Так же метод обладает низкой точностью.
В результате исследующего поиска не было достигнуто уменьшение значения целевой функции, то есть значение шага (векторной величины приращения) уменьшить в раз, до величины , затем необходимо произвести исследующий поиск вокруг точки , используя новое значение приращения .
Итерации продолжаются, пока величина шага не укажет на окончание поиска в окрестности точки минимума.
Рис 3. Графическое пояснение метода Хука-Дживса
Метод сопряжённых направлений Пауэлла
Описание алгоритма
Метод ориентирован на решение задач с квадратичными целевыми функциями. Основная идея алгоритма заключается в том, что если квадратичная функция:
приводится к виду сумма полных квадратов
то процедура нахождения оптимального решения сводится к одномерным поискам по преобразованным координатным направлениям.
В методе Пауэлла поиск реализуется в виде:
вдоль направлений , , называемых -сопряженными при линейной независимости этих направлений.
Сопряженные направления определяются алгоритмически. Для нахождения экстремума квадратичной функции переменных необходимо выполнить одномерных поисков.
Шаг 1. Задать исходные точки , и направление . В частности, направление может совпадать с направлением координатной оси;
Шаг 2. Произвести одномерный поиск из точки в направлении получить точку , являющуюся точкой экстремума на заданном направлении;
Шаг 3. Произвести одномерный поиск из точки в направлении получить точку ;
Шаг 4. Вычислить направление ;
Шаг 5. Провести одномерный поиск из точки (либо ) в направлении c выводом в точку .
Нахождение минимума целевой функции методом сопряжённых направлений Пауэлла.
Решение:
Целевая функция:
Начальная точка:
Значение целевой функции в этой точке:
Шаг 1. Зададим исходные точки S(1) и S(2):
S(1) = [1;0] S(2) = [0;1]
Шаг 2. Найдем значение l, при [Х(0)+2S(2)]. Произвольная точка на луче из точки Х(0) в направлении S(2) определяется как
Х = Х(0) + lS(2) = [-9;-10] + l[0;1]
откуда X1 = -9 X2 = l - 10
Подставляя эти значения в целевую функцию, получаем
(Х) =
Дифференцируем это выражение по и приравниваем нулю:
(X) = 2l - 31
l - 31 = 0
Отсюда находим l:
l = 15.5
X(1) = [-9;-10] + 15.5[0;1] = [-9;5.5]
[X(1)] = 99
Аналогично найдем значение l, при [Х(1)+S(1)].
Х = Х(1) + lS(1) = [-9;5.5] + l[1;0]
откуда X1 = l -9 X2 =5.5
Подставляя эти значения в целевую функцию, получаем
(Х) =
Дифференцируем это выражение по и приравниваем нулю:
(X) = 2l - 29
l - 29 = 0
Отсюда находим l:
l= 14.5
X(2) = [-9;5.5] + 10.5[1;0] = [0.5;5.5]
[X(2)] = 21
Также найдем значение l, при [Х(2)+2S(2)].
Х = Х(2) + lS(2) = [0.5;5.5] + l[0;1]
откуда X1 = 3 X2 = 5.5+ l
Подставляя эти значения в целевую функцию, получаем
(?/p>