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

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

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

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

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

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

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

β = 10, ε = 10-4 – 10-8, k = 1, х¹, h₁= … =h_n=0.1;

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

Шаг 1.

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

Шаг 2.

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

Шаг 3.

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

Обозначить

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

Шаг 4.

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

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

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

Если f(x) является дважды дифференци­руемой в Rⁿ, то эффективность процесса поиска точки х* ее минимума можно повысить, используя информацию не толь­ко о градиенте этой функции, но и о ее матрице Г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 шагов вектор направления делают равным антиградиенту.

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

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

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

Шаг 1.

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

Шаг 2.

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

Шаг 3.

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

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

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

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

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

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

(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");

}

Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...

Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычис­лить, когда этот...

Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...

ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...

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