Метод Хука – Дживса

Метод состоит из последовательности итераций, каждая из которых содержит перемещения двух типов : исследующий поиск вокруг базисной точки, за которым в случае успеха следует поиск по образцу. 1. Задается начальная точка, вектор приращений для каждой координаты и точность решения задачи минимизации. 2. Вычисляется целевая функция f0=f(x0).

3. Запоминается базисная точка x1=x0, f1=f0.4. Задаем m=0. 5. Для каждой k-й координаты по очереди вычисляется: xt=x1+dkk, ft=f(xt), где k – единичный вектор в направлении оси xk. Если ft < f1, то полагаем x1=xt, f1=ft, и переходим к следующей координате, иначе вычисляется xt=x1-dkk, ft=f(xt). Если ft < f1, то полагаем x1=xt, f1=ft, и переходим к следующей координате, иначе значение m увеличиваем на единицу и переходим к следующей координате. После выполнения таких вычислений для всех координат (k=1,2,…,n), переходим к следующему пункту. 6. Если m=n, т. е. уменьшение функции не было достигнуто ни по одной координате, то вектор приращений d уменьшают и повторяют вычисления с 4-го пункта. Вычисления повторяются до тех пор, пока не будет достигнуто уменьшение функции. 7. При поиске по образцу используется информация, полученная в процессе исследующего поиска. Разумно двигаться из полученной точки x1 в направлении p=x1–x0, поскольку поиск в этом направлении уже привел к уменьшению значения целевой функции. Поэтому на этапе поиска по образцу решается задача одномерной минимизации целевой функции f(x1+p) относительно шага одним из рассмотренных ранее методов. После получения значения min вычисляется новая базисная точка x0=x1+minp и вычисления повторяются со 2-го пункта. (Методы нулевого порядка)

Метод Нелдера – Мида

Метод Нелдера – Мида является развитием симплексного метода Спендли, Хекста и Химсворда. Геометрическая фигура, порожденная n+1 точкой в n-мерном пространстве, называется симплексом, а сами точки называются вершинами симплекса. Следовательно, в двумерном пространстве симплексом является треугольник, в трехмерном пространстве – тетраэдр. Если вершины равноудалены друг от друга, симплекс называется правильным. Идея метода состоит в сравнении значений целевой функции в n+1 вершине симплекса и перемещении симплекса в направлении оптимальной точки с помощью итерационной процедуры. В результате последовательных итераций симплекс модифицируется, двигаясь к точке минимума и сжимаясь вокруг неѐ. Симплекс преобразуется с помощью операций отражения, растяжения, редукции и сжатия. Преобразование симплекса начинается с операции отражения. Если коэффициенты отражения, редукции и растяжения равны соответственно 1, 0,5, 2, то симплексный метод носит название метода Нелдера – Мида. (Методы нулевого порядка)

Метод наискорейшего спуска

Как известно, направление градиента является направлением наискорейшего возрастания функции. Следовательно, противоположное направление является направлением наискорейшего убывания функции. Это свойство антиградиента лежит в основе градиентных методов первого порядка. При этом направление наискорейшего убывания в данной точке не всегда оказывается наилучшим для спуска к точке минимума, поэтому для повышения эффективности вводят различные поправки. При выборе очередного направления используют накопленную информацию о функции из предыдущих спусков. Множество возможностей введения таких поправок определяет многообразие различных методов первого порядка. В этом методе на каждой к-й итерации решается задача одномерной минимизации целевой функции относительно величины шага в направлении антиградиента. Новая точка вычисляется по формуле. Процесс прекращается, когда выполняется условие достижения точности. (первый порядок)