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

Эффективность прямого поиска точки минимума можно повысить, если на ка­ждом 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.

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

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

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

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

Блок-схемы

Метод Свенна

Метод ЗС-1

Метод ЗС-2

Метод Фибоначчи-1

Метод Фибоначчи-2

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