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

Методы безусловной оптимизации

Отчет по лабораторной работе №2

по дисциплине

«Оптимизация инженерных вычислений»

 

 

Студенты: Кучеренко Г. А.

Антонова А.Н.

Группа: Р-200301

Преподаватель: Селиванова И.А.

 

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

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

(47)

Таким образом, в данном варианте градиентного спуска на каждой итерации необходимо решить задачу одномерной минимизации (47). Алгоритм метода наискорейшего спуска состоит в следующем:

 

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

 

2. Осуществляется спуск в направлении антиградиента с выбранным шагом до тех пор, пока значение функции убывает, т.е. выполняется условие (46).

 

3. Если на i-ом шаге , то в точке вычисляются новые значения градиента и шага и выполняется переход к п.2

 

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

 

Алгоритм метода наискорейшего спуска:

1. Задаются: xº — начальное приближение, ε1 > 0, ε2> 0, M – предельное число итераций;

2. Количество итераций n = 0;

3. Вычисляется: gradf(xⁿ);

4. Вычисляется || gradf(xⁿ) ||;

4.1) если || gradf(xⁿ) || < ε1, то

x*= xⁿ;

4.2) если || gradf(xⁿ) || > ε1, то к 5);

5. n < M

5.1) если выполняется, то к 6);

5.2) если нет, то x*= xⁿ;

6. найти минимум функции φ(tn) = f(xⁿ — tn * gradf(xⁿ));

7. xⁿ ¹ = xⁿ — tn * gradf(xⁿ);

8. Проверяется условие f(xⁿ ¹) — f(xⁿ) < 0

8.1) если выполняется, то к 9);

8.2) если нет, то tn= tn / 2 и к 7);

9. Проверяется условие ||xⁿ ¹ – xⁿ ||< ε2 и f(xⁿ ¹) — f(xⁿ) < ε2

9.1) если оба условия выполняются, то x*= xⁿ ¹;

9.2) если хотя бы одно не выполняется, то n = n+1 и к 3).

 

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

Пусть требуется найти наименьшее значение целевой функции u = f (x 1, x 2,…, xn). В качестве начального приближения выберем в п -мерном пространстве некоторую точку M 0 с координатами . Зафиксируем все координаты функции и, кроме первой. Тогда - функция одной переменной x 1. Решая одномерную задачу оптимизации для этой функции, мы от точки M 0 перейдем к точке , в которой функция и принимает наименьшее значение по координате x 1 при фиксированных остальных координатах. В этом состоит первый шаг процесса оптимизации, состоящий в спуске по координате x 1.

 

Зафиксируем теперь все координаты, кроме x 2, и рассмотрим функцию этой переменной . Снова решая одномерную задачу оптимизации, находим ее наименьшее значение при , т.е. в точке . Аналогично проводится спуск по координатам x 3, x 4,…, xn, а затем процедура снова повторяется от x 1 до xn и т.д. В результате этого процесса получается последовательность точек M 0, M 1,…, в которых значения целевой функции составляют монотонно убывающую последовательность f . На любом k -м шаге этот процесс можно прервать, и значение f (Mk) принимается в качестве наименьшего значения целевой функции в рассматриваемой области.

Таким образом, метод покоординатного спуска сводит задачу о нахождении наименьшего значения функции многих переменных к многократному решению одномерных задач оптимизации по каждому проектному параметру.

Данный метод легко проиллюстрировать геометрически для случая функции двух переменных z=f (x, y), описывающей некоторую поверхность в трехмерном пространстве. На рис. 1 нанесены линии уровня этой поверхности. Процесс оптимизации в этом случае проходит следующим образом. Точка M 0(x 0, y 0) описывает начальное приближение. Проводя спуск по координате х, попадем в точку M 1(x 1, y 0). Далее, двигаясь параллельно оси ординат, придем в точку M 2(x 1, y 1)и т.д.

Важным здесь является вопрос о сходимости рассматриваемого процесса оптимизации. Другими словами, будет ли последовательность значений целевой функции f (M 0), f (M 1),… сходиться к наименьшему ее значению в данной области? Это зависит от вида самой функции и выбора начального приближения.

 

Рис. 1.

Для функции двух переменных очевидно, что метод неприменим в случае наличия изломов в линиях уровня. Это соответствует так называемому оврагу на поверхности. Здесь возможен случай, когда спуск по одной координате приводит на “дно” оврага. Тогда любое движение вдоль любой координаты ведет к возрастанию функции, соответствующему подъему на “берег” оврага. Поскольку поверхности типа “оврага” встречаются в инженерной практике, то при использовании метода покоординатного спуска следует убедиться, что решаемая задача не имеет этого недостатка.

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

Алгоритм метода покоординатного спуска:

В двумерном пространтсве R2. Решение задачи (2) методом покоординатного спуска, иначе называемого методом Гаусса - Зейделя, производят по следующей общей схеме.
Выбирают произвольно начальную точку х(0) из области определения функции f(х). Приближения х(k) определяются соотношениями (3):
x(k+1)=x(k)+t(k)S(k) (k=0,1,2,...),
где вектор направления спуска s(k)- это единичный вектор, совпадающий с каким-либо координатным направлением (например, если S(k) параллелен х1, то S(k)= {1,0,0,...,0}, если он параллелен x2, то S(k)={0, 1, 0,...,0} и т.д.); величина t(k) является решением задачи одномерной минимизации:
f(x(k)+ts(k)) --> min, t ОR1, (k=0,1,2,...),
и может определяться, в частности, методом сканирования.
Детальная реализация общей схемы в двумерном случае R2 дает траекторий приближения к точке х* методом покоординатного спуска, состоящую из звеньев ломаной, соединяющих точки х(k), х~(k), x(k+1) (k=0, 1, 2,) (рис.2). При k=0, исходя из начальной точки х(0)=(x1(0),x2(0)), находят точку х~(0)= (x1~(0),x2(0)), минимума функции одной переменной f(x1,x2(0)); при этом f(x~(0))<=f(x(0)).Затем находят точку минимума x(1) функции f (x1~(0),x2) по второй координате. Далее делают следующий шаг вычислений при k=1. Полагают, что исходной точкой расчета является х(1). Фиксируя вторую координату точки х(1), находят точку минимума х~(1)= (x1~(1),x2(1)), функции f(x1,x2(1)) одной переменной x(1); при этом f(x~(1))<=f(x(1))<=f(x(0)). Точку х(2) получают, минимизируя целевую функцию f(x1~(1),x2), вновь по коорданате х2, фиксируя координату x1~(1),точки x(1), и т.д.
Условием прекращения вычислительной процедуры при достижении заданной точности e может служить неравенство
||x(k+1) - x(k) ||<e (4)

 

 

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

clc

clear

 

%xx0=[2 3];

%xx0=[13 10];

xx0=[8.5 14.3];

[x11 x22]=meshgrid([-15:0.1:15],[-15:0.1:15]);

z=7.*x11.^2+2.*x11.*x22+5.*x22.^2-2.*x11-10.*x22;

contour(x11,x22,z);

hold on;

grid on;

syms x1 x2;

 

f=7*x1^2+2*x1*x2+5*x2^2-2*x1-10*x2;

eps=10^(-5);

h=1;

k=0;

plot(xx0(1),xx0(2),'o');

hold on

tic

 

while(1)

grad=[subs(diff(f,x1),[x1 x2],xx0)

subs(diff(f,x2),[x1 x2],xx0)];

l=norm(grad,inf);

grad1=grad./l;

fx0=subs(f,[x1 x2],xx0);

xxk=xx0-h*grad1';

fxk=subs(f,[x1 x2],xxk);

if (fxk<fx0)

fxp=fx0;

xxp=xx0;

while(fxk<fxp)

xxp=xxk;

xxk=xxp-h*grad1';

fxk=subs(f,[x1 x2],xxk);

xxp=xxk+h*grad1';

fxp=subs(f,[x1 x2],xxp);

plot(xxk(1),xxk(2),'.');

hold on

end

xx0=xxp;

plot(xx0(1),xx0(2),'o');

hold on

else

h=h/10;

end

 

if (h<eps)

break;

end

 

if (norm(grad,inf)<eps)

break;

end

k=k+1;

end

k

xxk

fxk

 

f=7*x1^2+2*x1*x2+5*x2^2-2*x1-10*x2;

xx0=[0 1];

 

 

 

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

clc

clear

 

%xx0=[2 3];

%xx0=[13 10];

xx0=[8.5 14.3];

[x11 x22]=meshgrid([-15:0.1:15],[-15:0.1:15]);

z=7.*x11.^2+2.*x11.*x22+5.*x22.^2-2.*x11-10.*x22;

contour(x11,x22,z);

hold on;

grid on;

plot(xx0(1),xx0(2),'o');

hold on;

syms x1 x2;

 

f=7*x1^2+2*x1*x2+5*x2^2-2*x1-10*x2;

eps=10^(-5);

h1=1;

h2=1;

k=0;

tic

while(1)

dfx1=subs(f,[x1 x2],[xx0(1) xx0(2)]);

xxk_=[xx0(1)+h1 xx0(2)];

xx_k=[xx0(1)-h1 xx0(2)];

dfx1_=subs(f,[x1 x2],xxk_);

df_x1=subs(f,[x1 x2],xx_k);

 

if (dfx1_<df_x1)&&(dfx1_<dfx1)

xxk=xxk_;

fxk=dfx1_;

fx0=dfx1;

while(fxk<fx0)

fx0=fxk;

xx0=xxk;

xxk=[xx0(1)+h1 xx0(2)];

fxk=subs(f,[x1 x2],xxk);

plot(xxk(1),xxk(2),'.');

hold on

end

else

if (df_x1<dfx1_)&&(df_x1<dfx1)

xxk=xx_k;

fxk=df_x1;

fx0=dfx1;

while(fxk<fx0)

fx0=fxk;

xx0=xxk;

xxk=[xx0(1)-h1 xx0(2)];

fxk=subs(f,[x1 x2],xxk);

plot(xxk(1),xxk(2),'.');

hold on

end

else

h1=h1/10;

end

plot(xx0(1),xx0(2),'o');

hold on

end

 

 

dfx2=subs(f,[x1 x2],[xx0(1) xx0(2)]);

xxk_=[xx0(1) xx0(2)+h2];

dfx2_=subs(f,[x1 x2],xxk);

xx_k=[xx0(1) xx0(2)-h2];

df_x2=subs(f,[x1 x2],xx_k);

 

if (dfx2_<df_x2)&&(dfx2_<dfx2)

xxk=xxk_;

fxk=dfx2_;

fx0=dfx2;

while(fxk<fx0)

fx0=fxk;

xx0=xxk;

xxk=[xx0(1) xx0(2)+h2];

fxk=subs(f,[x1 x2],xxk);

plot(xxk(1),xxk(2),'.');

hold on

end

else

if (df_x2<dfx2_)&&(df_x2<dfx2)

xxk=xx_k;

fxk=df_x2;

fx0=dfx2;

while(fxk<fx0)

fx0=fxk;

xx0=xxk;

xxk=[xx0(1) xx0(2)-h2];

fxk=subs(f,[x1 x2],xxk);

plot(xxk(1),xxk(2),'.');

hold on

end

else

h2=h2/10;

end

end

 

 

if((h1<eps)&&(h2<eps))

break;

end

plot(xx0(1),xx0(2),'+');

hold on

fx0=subs(f,[x1 x2],xx0);

k=k+1;

end

 

fx0

k

xx0

toc

 

f=7*x1^2+2*x1*x2+5*x2^2-2*x1-10*x2;

 

xx0=[0 1];

 

 

Шаг h=1; eps=10^(-5);

 

X0=[2 3]

 

Название	Число итераций	Время работы
Метод наискорейшего спуска		1.683678 seconds
Метод покоординатного спуска		0.924417 seconds

 

X0=[13 10]

 

Название	Число итераций	Время работы
Метод наискорейшего спуска		1.978522 seconds
Метод покоординатного спуска		1.152933 seconds

 

 

X0=[8.5 14.3]

 

Название	Число итераций	Время работы
Метод наискорейшего спуска		2.023583 second
Метод покоординатного спуска		1.675416 seconds