Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







Метод Хука-Дживса (конфигураций)





 

Эффективность прямого поиска точки минимума можно повысить, если на ка­ждом k-м шаге поиска соответствующим образом выбирать направление спуска. Для этого на каждом k-м шаге выделяют предварительный этап исследующего поиска. Целью этого этапа является выбор направления спуска путем исследования поведения целевой функции f(x) в окрестности точки xk-1, найденной на предыдущем шаге. В результате выполнения этапа исследующего поиска находится точка xk, для которой f(xk) < f(xk-1). Направление спуска, завершающего k-w. шаг поиска, определяется вектором xk - xk-1. Такая стратегия поиска, получила название метода Хука - Дживса.

 

Исследующий поиск 1

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

 

Ускоряющий поиск

Выполняем единичный шаг вдоль направления , . Затем производим исследующий поиск в окрестности x3, в надежде найти точку лучшую чем x2.

 

Начальный этап

β = 10, ε = 10-4 – 10-8 , k = 1, х1, h1= … =hn=0.1;

Основной этап

Шаг 1.

Выполнить ИП1 и отыскать т. х2 для которой .

Шаг 2.

Если ИП1 удачен т.е. найдена х2, то перейти на шаг 3, иначе, но в то же время h<ε необходимо уменьшить шаг в β раз и вернуться на шаг 1. При h<ε остановиться х* = х1.

Шаг 3.

Выполнить УП в пробную точку

Обозначить

В окрестности х3 попытаться ИП2 найти т. х4 «лучшую» чем х1.

Шаг 4.

Если ИП2 удачен, то положить и вернуться на шаг 1.

Иначе: уменьшить шаг в β раз и вернуться на шаг 1.


Метод Ньютона



 

Если f(x) является дважды дифференци­руемой в Rn, то эффективность процесса поиска точки х* ее минимума можно повысить, используя информацию не толь­ко о градиенте этой функции, но и о ее матрице Гecce H(x). Алгоритмы такого поиска обычно относят к ме­тоду Ньютона. В простейшем варианте алгоритма на каждой k-й итерации целевая функция аппроксимируется в окрестно­сти точки xk-1 (на первой итерации в окрестности начальной точки х0) квадратичной функцией и затем определяется точка xk минимума функции . На следующей, (k+1)-й итерации строится новая квадратичная аппроксимация уже в окрестности точки xk.

 

Начальный этап:

Выбрать x0, e, k=1.

Основной этап

Шаг 1

(1) Строится Ньютоновское направление: - градиент в заданной точке, H – матрица Гессе

(2) Найти как результат решения системы уравнений

(3)

(4)

Шаг 3

Проверить КОП: если , то , иначе на Шаг 1.

Метод Зангвилла

Начальный этап

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

Основной этап

Шаг 1. Взять в качестве оптимальное решение задачи минимизации при и положить . Если , то перейти к шагу 4; в противном случае перейти к шагу 2.

Шаг 2. Положить и взять в качестве оптимальное решение задачи минимизации при . Положить , и перейти к шагу 3.

Шаг 3. Если , то остановиться; -- оптимальное решение. В противном случае взять в качестве оптимальное решение задачи минимизации при . Положить . Если , то заменить на и повторить шаг 3. В противном случае положить , заменить на и перейти к шагу 1.

Шаг 4. Положить , , заменить на , положить и перейти к шагу 1.

 

Флетчера-Ривса

Метод сопряжённых направлений основан на свойствах векторов сопряженных относительно некоторой квадратной матрицы. Различие в способах построения системы сопряженных векторов, определяющих сопряжённые направления спуска, порождает несколько алгоритмов этого метода. В качестве матрицы сопряжений берётся матрица Гессе. Особенность алгоритмов метода сопряженных направле­ний состоит в том, что систему сопряженных векторов строят последовательно в процессе выполнения итераций, причем найденный на очередной, k-й итерации вектор pk определяет на этой итерации направление спуска. Для не квадратичных функций получаемые направления, в конце концов, перестают быть взаимносопряженными поэтому, как и в ДФП через n шагов вектор направления делают равным антиградиенту.

Начальный этап

Выбрать x1, e, k=1.

Основной этап

Шаг 1.

Построить вектор pk:

Шаг 2.

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

Шаг 3.

Проверить КОП: .

 

Расчетное соотношение Флетчера-Ривса

 

 

Метод Пауэлла

 

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

Первый варианталгоритма метода Пауэлла

Начальный этап

(1) Выбрать x1, e, k=1.

(2) Положить

Основной этап:

Шаг 1.

(1) Выполнить n переходов по векторам базиса :

(2) Определить новое направление и спуститься вдоль него:

Шаг 2.

Проверить КОП: если ,или k = n (для квадратичных функций) то прекратить поиск, иначе Шаг 3

Шаг 3.

Построить новую поисковую систему: из предыдущей системы удаляется первый вектор, а в конец добавляется вектор d.

Таким образом изменение системы поиска выглядит так:

 

 

Второй вариант алгоритма метода Пауэлла

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

Изменение поисковой системы выглядит так:

 

 

 

double dichot(double a,double b)

{

double alpha,myu,eps=0.0001,del=0.1*eps;

alpha=(a+b-del)/2;

myu=(a+b+del)/2;

while (abs(b-a)>eps)

{

if (f(alpha)<f(myu))

b=myu;

else

a=alpha;

alpha=(a+b-del)/2;

myu=(a+b+del)/2;

}

return ((a+b)/2);

}

 

void main()

{

setlocale(0,"RUS");

 

double x2,x1=0,a,b,eps=0.0001,h;

if (x1!=0)

h=0.01*x1;

else

h=0.01;

b=swanna(h,x1,x2);

a=b-h;

cout<<"f(x)= -exp(-x)*log(x)"<<endl;

cout<<"Метод Свенна: a="<<a<<" ,b="<<b<<endl;

//Метод Больцано

x1=bolzan(a,b);

cout<<"Метод Больцано: x="<<x1<<endl;

//Метод дихотомии

x1=dichot(a,b);

cout<<"Метод Дихотомии: x="<<x1<<endl;

//Метод золотого сечения 1

x1=zoloto(a,b);

cout<<"Метод Золотого сечения 1: x="<<x1<<endl;

//Метод золотого сечения 2

x1=zoloto2(a,b);

cout<<"Метод Золотого сечения 2: x="<<x1<<endl;

int n=0;

while (Fib(n) < (abs(a-b)/eps))

n++;

x1=fibonachchi1(a,b,n);

cout<<"Метод Фибоначчи1: x="<<x1<<endl;

x1=fibonachchi2(a,b,n);

cout<<"Метод Фибоначчи2: x="<<x1<<endl;

system("pause");

}









Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:


©2015- 2018 zdamsam.ru Размещенные материалы защищены законодательством РФ.