Метод покоординатного спуска
Методы безусловной оптимизации
Отчет по лабораторной работе №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(x1,x2,…,xn). В качестве начального приближения выберем в п-мерном пространстве некоторую точку M0 с координатами 
. Зафиксируем все координаты функции и, кроме первой. Тогда 
- функция одной переменной x1. Решая одномерную задачу оптимизации для этой функции, мы от точки M0 перейдем к точке 
, в которой функция ипринимает наименьшее значение по координате x1 при фиксированных остальных координатах. В этом состоит первый шаг процесса оптимизации, состоящий в спуске по координате x1.
Зафиксируем теперь все координаты, кроме x2, и рассмотрим функцию этой переменной 
. Снова решая одномерную задачу оптимизации, находим ее наименьшее значение при 
, т.е. в точке 
. Аналогично проводится спуск по координатам x3,x4,…,xn, а затем процедура снова повторяется от x1 до xn и т.д. В результате этого процесса получается последовательность точек M0,M1,…, в которых значения целевой функции составляют монотонно убывающую последовательность f 
. На любомk-м шаге этот процесс можно прервать, и значение f(Mk) принимается в качестве наименьшего значения целевой функции в рассматриваемой области.
Таким образом, метод покоординатного спуска сводит задачу о нахождении наименьшего значения функции многих переменных к многократному решению одномерных задач оптимизации по каждому проектному параметру.
Данный метод легко проиллюстрировать геометрически для случая функции двух переменных z=f(x,y), описывающей некоторую поверхность в трехмерном пространстве. На рис. 1 нанесены линии уровня этой поверхности. Процесс оптимизации в этом случае проходит следующим образом. Точка M0(x0,y0) описывает начальное приближение. Проводя спуск по координате х, попадем в точку M1(x1,y0). Далее, двигаясь параллельно оси ординат, придем в точку M2(x1,y1)и т.д.
Важным здесь является вопрос о сходимости рассматриваемого процесса оптимизации. Другими словами, будет ли последовательность значений целевой функции f(M0), f(M1),… сходиться к наименьшему ее значению в данной области? Это зависит от вида самой функции и выбора начального приближения.
Рис. 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 |