Методы многомерной оптимизации

Дана некоторая функция многих переменных f(x₁,x₂,x₃,…..,x_n) или надо найти такое значение при котором функция принимает экстремальное значение (минимальное или максимальное). Процесс поиска экстремального значения иногда называют оптимизацией. называют оптимизируемой или целевой функцией называют вектором параметров оптимизации. В области определения функции может быть несколько экстремумов. Все существующие методы многомерной оптимизации позволяют определить лишь один из экстремумов. Какой именно экстремум будет определён, зависит от выбора начального приближения: Методы поиска экстремума будем рассматривать относительно случая поиска минимума, для функции двух переменных.

Все методы многомерной оптимизации делятся на два класса: градиентные; безградиентные.

Градиентный метод. Градиентом называется вектор равный сумме произведений частных производных на соответствующие орты. Орта – единичный связанный вектор, направленный вдоль координатной оси.

 Основные свойства градиента: Норма градиента определяет скорость изменения функции в направление градиента; Градиент всегда направлен в сторону наиболее быстрого возрастания функции, т.е. в этом направлении норма вектора градиента максимальна; Градиент перпендикулярен линии уровня. Антиградиентом называется вектор, направленный в сторону противоположную градиенту.

Алгоритм

1) Дана функция n переменных точность ε, параметр шага h, задаем начальное приближение вычисляем значение функции

2) Вычисляем вектор градиента  и единичный вектор градиента

3) Вычисляем новое приближение, делая шаг в направление антиградиента  и вычисляем значение функции

4) Проверяем условие Fz < Fx

5) Если условие выполняется, то за начальное приближение принимаем  т.е. , переходим на пункт 2.

6) Иначе, проверяем условие окончания h < ε

7) Если условие выполняется, то выводим Конец алгоритма

8) Если не выполняется, то уменьшаем параметр шага h=h/3 и переходим на пункт 2

Программа. Многомерная оптимизация. Градиентный метод.

function DATA

global x0 h eps;

x0=[0.3;0.3];

h=0.5;

eps=0.1;

end

 

function [ fx ] = f(x)

fx=x(1)^2+x(2)^2-5;

end

 

function [ G ] = Grad(x)

G=[2*x(1);2*x(2)];

end

 

function [ x,fx ] = fun_MnogomernOpt_Grad(x0,h,eps)

x=x0;

fx=f(x);

for i=1:100

v=Grad(x)./norm(Grad(x));

z=x-h*v;

fz=f(z);

if fz<fx

   x=z;

   fx=fz;

else

   if abs(h)<eps

       i

       break;

   else

       h=h/3;

   end %if

end %if

end %for i

end % function

 

function GLAV_MnogomernOpt_Grad

global x0 h eps x fx;

DATA;

[ x,fx ] = fun_MnogomernOpt_Grad(x0,h,eps);

REPORT;

end % function

 

function REPORT

global x0 h eps x fx;

disp('Mnogomernaya optimizaciya gradient');

disp(' ');

disp('Arguments');

x0

disp(['h = ' num2str(h,'%10.5f') ]);

disp(['eps = ' num2str(eps,'%10.5f') ]);

disp('Results');

x

disp(['fx = ' num2str(fx,'%10.5f') ]);

end % function

 

Программа. Многомерная оптимизация. Метод наискорейшего спуска.

function DATA

global x0 h eps;

x0=[0.3;0.3];

h=0.5;

eps=0.1;

end

 

function [ fx ] = f(x)

fx=x(1)^2+x(2)^2-5;

end

 

function [ G ] = Grad(x)

G=[2*x(1);2*x(2)];

end

 

function [ xm,fm ] = rvs(x,v,h,eps)

xm=x;

fm=f(x);

for i=1:100

if abs(h)<=eps

   i

   break;

else

   x=xm-h*v;

   fx=f(x);

   if fx<fm

       xm=x;

       fm=fx;

   else

       h=-h/3;

   end %if

end %if

end %for i

end

 

function [ x,fx ] = fun_MnogomernOpt_NSpusk(x0,h,eps)

x=x0;

for i=1:100

v=Grad(x)./norm(Grad(x));

[ xm,fm ] = rvs(x,v,h,eps);

dx=xm-x;

ndx=norm(dx);

x=xm;

fx=fm;

if ndx<eps

   i

   break;

end %if

end %for i

end % function

 

function GLAV_MnogomernOpt_NSpusk

global x0 h eps x fx;

DATA;

[ x,fx ] = fun_MnogomernOpt_NSpusk(x0,h,eps);

REPORT;

end % function

 

function REPORT

global x0 h eps x fx;

disp('Mnogomernaya optimizaciya naiskor spusk');

disp(' ');

disp('Arguments');

x0

disp(['h = ' num2str(h,'%10.5f') ]);

disp(['eps = ' num2str(eps,'%10.5f') ]);

disp('Results');

x

disp(['fx = ' num2str(fx,'%10.5f') ]);

end % function

 

Симплексный метод. Симплексом в n-мерном пространстве называется выпуклый многоугольник с n+1 вершиной. n=2 треугольник n=3 тетраэдр.

Алгоритм

1) Дана функция 2^x переменных  точность ε, параметр h, начальное приближение

2) Вычисляем координаты вершин симплекса

3) Вычисляем значения функции

4) Определяем (рис.2.10.1) худшую вершину  и координаты отраженной вершины, она будет лежать на прямой исходящей из худшей вершины и проходящей через середину противоположной грани

Рис.2.10.1. Переход от худшей вершины к отраженной.

5) Сравниваем значения функции  

6) Условие выполняется. За новый симплекс принимаем симплекс с вершиной и повторяем с пункта 3

7) Условие не выполняется. Проверяем условие окончания h< ε

8) Условие окончания выполняется. Выводим координаты и значение функции лучшей вершины

9) Условие не выполняется. За принимаем лучшую вершину последнего симплекса, уменьшаем длину грани h=h/3 и повторяем с пункта 2.

Операторы МАТЛАБа позволяют это сделать так:

fxx=inline(‘8*x(1)^2+5*x(2)^2+4x(1)*x(2)')

[x,y,opt]=fminsearch(fxx,[0;0])

Метод сканирования. В области исследуемой функции двух переменных выбирается значение одной из переменных, соответствующее краю области поиска. По другой переменной интервал поиска разбивается на равные участки, длина каждого из которых равна шагу поиска. Далее значение функции последовательно определяется во всех точках разбиения и на краях отрезка, наименьшее из них запоминается. Затем увеличивают переменную, значение которой было постоянным, на шаг поиска и повторяют процедуру. И так до тех пор, пока не будет исследована вся область поиска с заранее выбранным шагом по каждой из переменных. Минимальное из всех сохраненных значений минимумов и есть глобальный минимум.

Для повышения точности повторяют сканирование в области, края которой отстоят от найденной точки минимума на величину шага предыдущего сканирования. Новое значение шага сканирования будет многократно меньше.

Программа. Многомерная оптимизация. Сканирование.

function DATA

global xl xr yl yr nx ny m;

xl=-5;

xr=5;

yl=-5;

yr=5;

nx=6;

ny=6;

m=3;

end

 

function [ fx ] = f(x,y)

fx=x.^2+y.^2-5;

end

 

function [zmin,xmin,ymin]=minZ(z,x,y,nx,ny)

zmin=z(1,1);

xmin=x(1);

ymin=y(1);

for i=1:nx

for j=1:ny

   if zmin>z(i,j)

       zmin=z(i,j);

       xmin=x(i);

       ymin=y(j);

   end %if

end %for j

end %for i

end % function

 

function [ x,y,fx ] = fun_MnogomernOpt_Scanir(xl,xr,yl,yr,nx,ny,m)

for i=1:m

hx=(xr-xl)/nx;

hy=(yr-yl)/ny;

for j=1:nx

   if j==1

       x(j)=xl;

   else

       x(j)=x(j-1)+hx;

   end %if

   for k=1:ny

       if k==1

           y(k)=yl;

       else

           y(k)=y(k-1)+hy;

       end %if

       z(j,k)=f(x(j),y(k));

   end%for k

end %for j

[zmin,xmin,ymin]=minZ(z,x,y,nx,ny);

xl=xmin-hx;

xr=xmin+hx;

yl=ymin-hy;

yr=ymin+hy;

end %for i

x=xmin;

y=ymin;

fx=zmin;

end % function

 

function GLAV_MnogomernOpt_Scanir

global xl xr yl yr nx ny m x y fx;

DATA;

[ x,y,fx ] = fun_MnogomernOpt_Scanir(xl,xr,yl,yr,nx,ny,m);

REPORT;

end % function

 

function REPORT

global xl xr yl yr nx ny x y fx;

disp('Mnogomernaya optimizaciya scanirovaniye');

disp(' ');

disp('Results');

disp(['x = ' num2str(x,'%10.5f') ]);

disp(['y = ' num2str(y,'%10.5f') ]);

disp(['zmin = ' num2str(fx,'%10.5f') ]);

hx=(xr-xl)/nx;

hy=(yr-yl)/ny;

[x,y]=meshgrid(xl:hx:xr,yl:hy:yr);

z=f(x,y);

mesh(x,y,z);

xlabel('x');

ylabel('y');

zlabel('z');

title('Mnogomernaya optimizaciya scanirovaniye');

end % function

Метод Гаусса-Зейделя. Движение к оптимуму происходит поочередно по каждой из осей до нахождения частного экстремума (ниже на рис.2.10.2). После нахождения частного экстремума по одной из осей  начинается поиск экстремума по другой оси до частного минимума при условии, что значение первой переменной равно найденному минимуму (максимуму) на первой оси. И так поочередно. Процесс последовательно продолжается до тех пор, пока не будет достигнута заданная точность локализации экстремума, т. е. если шаг по каждой из осей приводит к возрастанию (уменьшению) функции, а величина шага меньше или равна заданной точности поиска, то расчет закончен.

Рис.2.10.2. Движение до достижения экстремума по одной оси.

Метод пробных движений. По каждой из переменных:

· из исходной точки делается маленький пробный шаг;

· находится значение функции;

· шаг делается обратно, чтобы вернуться в исходную точку.

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