Градиентный метод с дроблением шага.

Дата добавления: 2015-06-12; просмотров: 3717; Нарушение авторских прав

Этот метод обеспечивает монотонное убывание целевой функции на каждой итерации и тем самым сходимость метода к точке минимума. Убывание функции обеспечивается коррекцией шага на каждой итерации. Расчетной формулой является рассмотренная выше

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

Если в точке , найденной с шагом предыдущей k – той итерации, функция уменьшилась, шаг увеличивается , пока функция продолжает убывать.

Описанный метод реализован в практическом алгоритме оптимизирующей функции, ориентированном на систему MATLAB.

Несколько первых строк кода функции:

function [ x,f ] = gradh(z,dz,x,e )

% Минимизация функции n переменных градиентным методом

% с дроблением шага

z=fcnchk(z);

dz=fcnchk(dz);

k=0;

hmax=-1;

hmin=1e7;

maxit=10000;

kz=0;

global xf;

d=-dz(x);

f=z(x);

h=1;

tic

while k<maxit

xf(1,k+1)=x(1);

xf(2,k+1)=x(2);

if norm(d)<e

toc

disp('gradh: минимум найден,')

disp(['итераций - ' num2str(k)....

', hmin=' num2str(hmin)....

', hmax=' num2str(hmax)])

disp(['вычислений функции - ' num2str(kz)])

disp(['вычислений градиента - ' num2str(k)])

f=z(x);

x=x';

return

end

. . . . . . . . . . . . . . . . .

Пример тестирующего скрипта

clear all

clc

x=[10 10];

e=0.00001;

x0=x

global xf;

[x,z]=gradh('fun','dfun',x,e), c='r';

plot(xf(1,:),xf(2,:),c)

hold on

x1=x(1)-5:0.1:x(1)+10;

x2=x(2)-5:0.1:x(2)+15;

[x1,x2]=meshgrid(x1,x2);

z=9*x1.^2+x2.^2-18*x1+6*x2+18;

contour3(x1,x2,z,[1 5 17 39 57 101 151 199 251 301])

начало

z=fcnchk(z) dz=fcnchk(dz) k=0 hmax= -1 hmin=1e7 maxit=10000 kz=0 h=1 f=z(x) d= -dz(x) tic

xf(1,k+1)=x(1) xf(2,k+1)=x(2)

xn=x+h*d fn=z(xn) kz=kz+1

toc k, kz hmin hmax

return

norm(d)<e

k<maxiter

число итераций достигло maxit

return

fn>f

x=x+h*d d=-d z(x) f=z(x) k=k+1 kz=kz+1

fn>f

h=h*0.05 xn=x+h*d fn=z(xn) kz=kz+1

hh=hh+hh xn=x+hh*d fn=z(xn) kz=kz+1

while 1

fn>f

h=hh f=fn

hh=h

h<hmin

h=hmin

h>hmax

h=hmax

Алгоритм функции градиентного метода с дроблением шага.

Результаты оптимизации функции z=9*x1^2+x2^2-8*x1+6*x2+18 из начальной точки [10 10]

x =

10 10

e =

1.0000e-005

Elapsed time is 0.005358 seconds.

gradh: минимум найден,

итераций - 46, hmin=0.0064, hmax=0.4398

вычислений функции - 193

вычислений градиента - 46

x =

1.0000

-3.0000

f =

5.2935e-012

Траектория оптимизации показана на рисунке

<== предыдущая лекция	\|	следующая лекция ==>
Градиентный метод с постоянным значением параметра шага.	\|	Градиентный метод с оптимизацией шага.