СКАЧАТЬ:  mns_my.zip [126,38 Kb] (cкачиваний: 52)

ЛАБОРАТОРНАЯ РАБОТА №2

ПО ДИСЦИПЛИНЕ «МОДЕЛИРОВАНИЕ СИСТЕМ»

НА ТЕМУ:

«МЕТОД НАИСКОРЕЙШЕГО СПУСКА»

Градиентные методы.

         Во всех градиентных методах вычисляются и анализируются производные целевой функции R(x). Если аналитический вид целевой функции R(x) известен, то вычисление производных не составляет особого труда. Если же зависимость в явном аналитическом виде записать нельзя или же аналитические выражения для производных получаются слишком сложными для практического использования в расчетах, то единственным способом определения производных является численный метод.

         К градиентным методам 1 порядка относят следующие методы:

1) метод релаксации;

2) метод градиента;

3) метод наискорейшего спуска (или крутого восхождения);

4) метод сопряженных градиентов.

          К градиентным методам 2 порядка относят следующие методы:

1) метод Ньютона;

2) метод переменной метрики, в котором используется информация о вторых производных.

          Градиентные методы в основном отличаются:

• способом определения направления движения к оптимуму;
• размером шага;
• продолжительностью поиска;
• критериями окончания поиска.

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

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

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

Рис.1. Характер движения к оптимуму в методе наискорейшего спуска.

         Критерием окончания поиска является условие

grad(x)=0

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

В качестве критерия окончания поиска может использоваться  следующее условие:

где -  координаты начальной и конечной точек последнего отрезка спуска (второй в этой части рис.1).

Этот же критерий может использоваться в сочетании с контролем значений целевой функции в точках :

Совместное применение этих двух условий оправдано в тех случаях, когда оптимизируемая функция имеет резко выраженный минимум.

Рис.2. К определению окончания поиска в методе наискорейшего спуска.

Расчетная часть

Задача. Пусть задана целевая функция

у=1–2*х1–2*х2–4*х1*х2+10*х1²+2*х2².

Найти минимум целевой функции, считая, что шаг переменный.

Решение. Примем начальные координаты равными:

                                                  х1=5

                                                  х2=3

Program MNS;

label l;

label n;

var x1,x2,e,y,z,q2:real;

function d1(x1,x2:real):real;

begin

d1:=-2-4*x2+20*x1

end;

function d2(x1,x2:real):real;

begin

d2:=-2-4*x1+4*x2

end;

function k(d1,d2:real):real;

begin

k:=d1/d2

end;

function q1(k:real):real;

begin

q1:=k*q2

end;

begin

write ('x1=');

read (x1);

write ('x2=');

read (x2);

write ('e=');

read (e);

q2:=0.5;

y:=1-2*x1-2*x2-4*x1*x2+10*x1*x1+2*x2*x2;

l:  z:=y;

n:         if d1(x1,x2)>0 then x1:=x1-q1(k(d1(x1,x2),d2(x1,x2)))

                 else x1:=x1+q1(k(d1(x1,x2),d2(x1,x2)));

            if d2(x1,x2)>0 then x2:=x2-q2

                 else x2:=x2+q2;

     if abs(y-z)<=e then writeln('y=',y:8:3,'  x1=',x1:8:3,'  x2=',x2:8:3)

                  else      begin if y<z then goto l else

begin y:=z;

if q2>=0.1 then q2:=q2-0.2 else q2:=q2/2;

goto n;

end;

       end;

end.