4b). Если fl
4с). Если fh>fr>fg , то меняем обозначения xr,xh (и соответствующие значения функции) местами и переходим на шаг 5.
4d). Если fr>fh, то переходим на шаг 5.
5. Сжатие. Строим точку xs=?xh+(1-?)xc и вычисляем в ней значение fs.
6. Если fs
7. Если fs>fh, то производим сжатие симплекса — гомотетию к точке с наименьшим значением x0: xi x0+(xi-x0)/2 для всех требуемых точек xi.
8. Последний шаг — проверка сходимости. Может выполняться по-разному, например, оценкой дисперсии набора точек. Суть проверки заключается в том, чтобы проверить взаимную близость полученных вершин симплекса, что предполагает и близость их к искомому минимуму. Если требуемая точность ещё не достигнута, можно продолжить итерации с шага 1.
4 Анализ метода
Изучение сходимости алгоритма Нелдера-Мида является трудной математической задачей. Известные результаты о сходимости симплекс-методов основаны на следующих предположениях:
- Симплекс не должен вырождаться при итерациях алгоритма
- На гладкость функции накладываются некоторые условия
В общем случае для метода Нелдера-Мида не выполняются сразу оба эти предположения, а следовательно, об условиях сходимости известно весьма мало. МакКиннон в 1998 году описал семейство строго выпуклых функций и класс начальных симплексов в двухмерном пространстве, для которых все вершины рабочего симплекса сходятся не к оптимальной точке. В 1998 году Лагариас опубликовал статью, в которой он исследовал сходимость метода в одно- и двухмерном пространствах для некоторых строго выпуклых функций с ограниченными поверхностями уровня.
Алгоритм Нелдера-Мида дает сильное уменьшение значение функции уже при первых нескольких итерациях и быстро достигает необходимой точности. Как правило, алгоритм производит одно или два вычисления функции на каждой итерации, если не учитывать сжатие, которое редко используется на практике. Это крайне важно в тех ситуациях, когда вычисление значений функции очень дорого или же требует много времени. Для подобных задач алгоритм Нелдера-Мида гораздо эффективнее многих других методов, требующих вычисления не менее значений функции на каждой итерации.
Главными преимуществами алгоритма являются его простота и эффективность.
С другой стороны, в силу отсутствия теории сходимости, на практике метод может приводить к неверному ответу даже для гладких функций. Также возможна ситуация, когда рабочий симплекс находится далеко от оптимальной точки, а алгоритм производит большое число итерации, при этом мало изменяя значения функции. Эвристический метод решения этой проблемы заключается в запуске алгоритма несколько раз и ограничении числа итераций.
5 Числовой эксперимент
В качестве числового эксперимента метод Нелдера-Мида был применен для вычисления минимума функции Розенброка:
для которой и . В качестве начального приближения был взят симплекс .
Ниже приведена таблица промежуточных результатов после каждых 10 итераций алгоритма.
Таблица 1 – Промежуточные результаты
Число итераций Координаты первой точки симплекса Координаты второй точки симплекса Координаты третьей точки симплекса fl fh
10 x=2.78; y=7.55; x=2.39; y=6.39; x=1.73; y=6.87; 6.725 1479.400
20 x=2.63; y=6.96; x=2.70; y=7.29; x=2.64; y=6.88; 2.769 3.225
30 x=2.24; y=4.94; x=2.35; y=5.50; x=2.42; y=5.86; 1.823 2.017
40 x=1.90; y=3.58; x=1.83; y=3.38; x=1.97; y=3.89; 0.821 0.996
50 x=1.51; y=2.28; x=1.53; y=2.36; x=1.57; y=2.47; 0.273 0.327
60 x=1.20; y=1.42; x=1.23; y=1.51; x=1.27; y=1.61; 0.050 0.079
70 x=0.99; y=0.97; x=1.01; y=1.02; x=0.96; y=0.93; 0.000 0.003
Итоговое количество итераций 79. Вычисленный минимум функционала равен .
Метод Нелдера-Мида прост в реализации, в качестве параметров алгоритма как правило используются следующие:
В качестве начального, как правило, используется произвольный симплекс. Также возможно многократное вычисление минимума при различных случайных начальных симплексах.
ЗАКЛЮЧЕНИЕ
Была осуществлена реализация метода поиска по деформируемому многограннику для функции Розенброка с визуализацией траектории метода.
Симплекс-метод Нелдера-Мида является очень эффективным алгоритмом поиска экстремума функции многих переменных, не накладывающим ограничений на гладкость функции. На каждой итерации алгоритма производится как правило одно-два вычисления значений функции, что чрезвычайно эффективно если эти вычисления очень медленны. Кроме того, алгоритма очень прост в реализации. Главным же его недостатком является отсутствие теории сходимости и наличие примеров, когда метод расходится даже на гладких функциях.
СПИСОК ИСПОЛЗОВАННЫХ ИСТОЧНИКОВ
1. Банди Б. Методы Оптимизации. Вводный курс. М.: Радио и связь, 1988.
2. http://www.scholarpedia.org/article/Nelder-Mead_algorithm
Приложение А
import java.awt.*;
import java.util.*;
import java.awt.event.*;
public class Dot
{
public double x1,x2;
public Dot(){x1=0;x2=0;}
public Dot(double X1,double X2){x1=X1;x2=X2;}
public Dot(Dot D){x1=D.x1; x2=D.x2;}
public Dot (Dot d1,Dot d0){x1 = 2*d1.x1-d0.x1; x2 = 2*d1.x2-d0.x2;}
public void setDot(Dot D){x1=D.x1; x2=D.x2;}
public void setDot(Dot d1,Dot d0){x1 = 2*d1.x1-d0.x1; x2 = 2*d1.x2-d0.x2;}
public void setDot(double x1,double x2){this.x1=x1;this.x2=x2;}
public boolean equalTo(Dot D){ if ((x1==D.x1)&&(x2==D.x2)) return true; return false; }
}
public class Triangle
{
public Dot xl,xg,xh;
public int[] masx = new int[3];
public int[] masy = new int[3];
public Triangle(){ xl = new Dot(); xg = new Dot(); xh = new Dot(); }
public Triangle(Dot xl,Dot xg,Dot xh){ this.xl = new Dot(xl); this.xg = new Dot(xg); this.xh = new Dot(xh); }
public Triangle(Triangle T){ xl = new Dot(T.xl); xg = new Dot(T.xg); xh = new Dot(T.xh); }
public void setTriangle(Triangle T){ xl.setDot(T.xl); xg.setDot(T.xg); xh.setDot(T.xh); }
public void setTriangle(Dot xl,Dot xg,Dot xh){ this.xl.setDot(xl); this.xg.setDot(xg); this.xh.setDot(xh); }
public void cutInHalf() { xg.setDot((xg.x1+xl.x1)/2, (xg.x2+xl.x2)/2); xh.setDot((xh.x1+xl.x1)/2, (xh.x2+xl.x2)/2);}}
public class Method extends Frame
{
double scl = 630;
double indent = 30;
double topY = 23;
int mesure = 13;
double step = mesure/5;
int precision = -8;
double alfa = 1;
double beta = 0.5;
double gama = 2;
double masX1[]=new double [(int)(2*scl)+2];
double masX2[]=new double [(int)scl*2+2];
int masx1[] = new int [(int)scl*2+2];
int masx2[] = new int [(int)scl*2+2];
Triangle T[] = new Triangle[(int)(10*scl)];
int t = 0;
String message = "";
String message2 = "";