Лабораторная работа №3 - файл MO_lab3_v6.doc
Лабораторная работа №3скачать (69.3 kb.)
Доступные файлы (9):
MO_lab3_v6.doc
Уфимский Государственный Авиационный Технический Университет
Лабораторная работа №3 «Многомерная безусловная оптимизация
(Методы Ньютона и сопряжённых градиентов)»
по дисциплине:
Методы оптимизации
Выполнил: студент группы АСОИ-334
факультета ИРТ
Хиячин Р. А.
Проверил: Хасанов А.Ю.
Уфа 2008
Содержание:1. Цель работы 2
2. Вариант задания 2
3. Блок-схемы алгоритмов 3
3.1. Метод Золотого сечения 6
3.2. Метод Ньютона 6
3.3. Метод Ньютона-Рафсона с дроблением шага 7
3.4. Модификация I метода Ньютона-Рафсона с дроблением шага 8
3.5. Модификация II метода Ньютона-Рафсона с дроблением шага 10
3.6. Метод Ньютона-Рафсона с оптимальным шагом 11
3.7. Модификация II метода Ньютона-Рафсона с оптимальным шагом 13
4. Исходный текст программы 16
5. Графики нахождения точки минимума 21
6. Таблица результатов 24
7. Вывод программы 24
8. Вывод 24
1. Цель работы
Цель работы: знакомство с методами многомерной безусловной оптимизации второго порядка и близкого к ним по эффективности метода сопряжённых градиентов, освоение и сравнение эффективности их применения для конкретных целевых функций.
2. Задание
Изучить предлагаемые методы безусловной оптимизации второго порядка и метод сопряженных градиентов.
В соответствии с вариантом задания, определенным преподавателем, составить программы, реализующие методы поиска минимума; найти приближенное значение минимума с заданной точностью ?; определить количество точек, в которых пришлось вычислять функцию до достижения заданной точности; построить график траектории приближенных решений задачи минимизации.
Оформить о выполнении задания с приведением условия задачи, алгоритмов и программ, указанных в задании методов поиска, построенных графиков траекторий приближенных решений задачи минимизации, результатов сравнения рассмотренных методов, заключения по результатам сравнения методов.
Вариант задания:Методы многомерной безусловной оптимизации:а) Метод Ньютона;
б) Метод Ньютона-Рафсона с дроблением шага;
б
г) Модификация I метода Ньютона-Рафсона с дроблением шага;
б
д) Модификация II метода Ньютона-Рафсона с дроблением шага;
в) Метод Ньютона-Рафсона с оптимальным шагом;
в
д) Модификация II метода Ньютона-Рафсона с оптимальным шагом;
№ | Целевая функция | Начальное приближение | Точность решения |
a | b | c | d |
6 | 11 | -0,4 | 1 | 0,21 | (-1;0) | 0,0001 |
3. Блок-схемы алгоритмов 3.1. Метод Золотого сечения (функция
min_alfa())
3.2. Метод Ньютона (подпрограмма
newton ())

3.3. Метод Ньютона-Рафсона с дроблением шага (подпрограмма
NR_drob ())
3.4. Модификация I метода Ньютона-Рафсона с дроблением шага (подпрограмма
NR_drob_M1 ())
3.5. Модификация II метода Ньютона-Рафсона с дроблением шага (подпрограмма
NR_drob_M2 ())


3.6. Метод Ньютона-Рафсона с оптимальным шагом
(подпрограмма
NR_opt ())


3.7. Модификация II метода Ньютона-Рафсона с оптимальным шагом (подпрограмма
NR_opt _M2 ())
4. Исходный текст программы#include
#include
#include
#include
#include
#include
int N0=0,N1=0,N2=0;
double a=11, b=-0.4, c=1, d=0.21;
double f(double x1,double x2)
{
double y=a*x1+b*x2+exp(c*pow(x1,2)+d*pow(x2,2));
N0++;
return y;
}
double dfx1(double x1, double x2)
{
double y=a+2*c*x1*exp(c*pow(x1,2)+d*pow(x2,2));
N1++;
return y;
}
double dfx2(double x1, double x2)
{
double y=b+2*d*x2*exp(c*pow(x1,2)+d*pow(x2,2));
N1++;
return y;
}
double dfx11(double x1, double x2)
{
double y=2*c*exp(c*pow(x1,2)+d*pow(x2,2))+pow(2*c*x1,2)*exp(c*pow(x1,2)+d*pow(x2,2));
N2++;
return y;
}
double dfx12(double x1, double x2)
{
double y=2*c*x1*2*d*x2*exp(c*pow(x1,2)+d*pow(x2,2));
N2++;
return y;
}
double dfx21(double x1, double x2)
{
double y=2*d*x1*2*c*x2*exp(c*pow(x1,2)+d*pow(x2,2));
N2++;
return y;
}
double dfx22(double x1, double x2)
{
double y=2*d*exp(c*pow(x1,2)+d*pow(x2,2))+pow(2*d*x1,2)*exp(c*pow(x1,2)+d*pow(x2,2));
N2++;
return y;
}
double min_alfa(double a,double b,double x1,double x2,double p1,double p2)
{
double e, y1,y2,t,al1,al2;
e=0.0001;
t=(1+sqrt(5))/2;
al1=a+(b-a)/(t*t);
y1=f(x1-al1*p1,x2-al1*p2);
al2=a+(b-a)/t;
y2=f(x1-al2*p1,x2-al2*p2);
while(((b-a)/t)>(2*e))
{
if(y1
{
b=al2;
al2=al1;
y2=y1;
al1=a+b-al2;
y1=f(x1-al1*p1,x2-al1*p2);
}
else
{
a=al1;
al1=al2;
y1=y2;
al2=a+b-al1;
y2=f(x1-al1*p1,x2-al1*p2);
}
}
al1=(a+b)/2;
return(al1);
}
//----------------------------= Newton =----------------------------
void newton()
{
ofstream out;
out.open("newton.txt");
int k;
double x1[1000],x2[1000];
double e,z1,z2,z11,z12,z21,z22,p1,p2,x1_min,x2_min,f_min;
x1[0]=-1;
x2[0]=0;
e=0.0001;
z1=dfx1(x1[0],x2[0]);
z2=dfx2(x1[0],x2[0]);
k=0;
do
{
z11=dfx11(x1[k],x2[k]);
z12=dfx12(x1[k],x2[k]);
z21=dfx21(x1[k],x2[k]);
z22=dfx22(x1[k],x2[k]);
p2=(z2-z12*z1/z11)/(z22-z12*z21/z11);
p1=z1/z11-z12*p2/z11;
x1[k+1]=x1[k]-p1;
x2[k+1]=x2[k]-p2;
out<<
//x1[k+1]<<
x2[k+1]<<
endl;
z1=dfx1(x1[k+1],x2[k+1]);
z2=dfx2(x1[k+1],x2[k+1]);
k++;
// cout<<"k="<
// cout<<"x1="<
N0=0;N1=0;N2=0;
}
//---------------------= Newton-Rafson s drobleniem =---------------------
void NR_drob()
{
ofstream out;
out.open("NR_drob.txt");
int k;
double x1[1000],x2[1000];
double e,alfa,q,z1,z2,z11,z12,z21,z22,p1,p2,x1_min,x2_min,f_min;
x1[0]=-1;
x2[0]=0;
e=0.0001;
alfa=1;
q=0.25;
z1=dfx1(x1[0],x2[0]);
z2=dfx2(x1[0],x2[0]);
k=0;
do
{
z11=dfx11(x1[k],x2[k]);
z12=dfx12(x1[k],x2[k]);
z21=dfx21(x1[k],x2[k]);
z22=dfx22(x1[k],x2[k]);
p2=(z2-z12*z1/z11)/(z22-z12*z21/z11);
p1=z1/z11-z12*p2/z11;
while ((f(x1[k]-alfa*p1,x2[k]-alfa*p2)-f(x1[k],x2[k]))>(-q*alfa*(z1*p1+z2*p2)))
alfa=alfa/2;
x1[k+1]=x1[k]-alfa*p1;
x2[k+1]=x2[k]-alfa*p2;
out<<
x1[k+1]<<
//x2[k+1]<<
endl;
z1=dfx1(x1[k+1],x2[k+1]);
z2=dfx2(x1[k+1],x2[k+1]);
k++;
// cout<<"k="<
// cout<<"x1="<
N0=0;N1=0;N2=0;
}
//--------------------= Newton-Rafson s drobleniem M1 =--------------------
void NR_drob_M1()
{
ofstream out;
out.open("NR_drob_M1.txt");
int k;
double x1[1000],x2[1000];
double e,alfa,q,z1,z2,z11,z12,z21,z22,p1,p2,x1_min,x2_min,f_min;
x1[0]=-1;
x2[0]=0;
e=0.0001;
alfa=1;
q=0.25;
z1=dfx1(x1[0],x2[0]);
z2=dfx2(x1[0],x2[0]);
k=0;
z11=dfx11(x1[k],x2[k]);
z12=dfx12(x1[k],x2[k]);
z21=dfx21(x1[k],x2[k]);
z22=dfx22(x1[k],x2[k]);
do
{
p2=(z2-z12*z1/z11)/(z22-z12*z21/z11);
p1=z1/z11-z12*p2/z11;
while ((f(x1[k]-alfa*p1,x2[k]-alfa*p2)-f(x1[k],x2[k]))>(-q*alfa*(z1*p1+z2*p2)))
alfa=alfa/2;
x1[k+1]=x1[k]-alfa*p1;
x2[k+1]=x2[k]-alfa*p2;
out<<
x1[k+1]<<
//x2[k+1]<<
endl;
z1=dfx1(x1[k+1],x2[k+1]);
z2=dfx2(x1[k+1],x2[k+1]);
k++;
// cout<<"k="<
N0=0;N1=0;N2=0;
}
//-------------------= Newton-Rafson s drobleniem M2 =-------------------
void NR_drob_M2()
{
ofstream out;
out.open("NR_drob_M2.txt");
int i = 0;
int k;
double x1[1000],x2[1000];
double e,alfa,q,z1,z2,z11,z12,z21,z22,p1,p2,x1_min,x2_min,f_min;
x1[0]=-1;
x2[0]=0;
e=0.0001;
alfa=1;
q=0.25;
z1=dfx1(x1[0],x2[0]);
z2=dfx2(x1[0],x2[0]);
k=0;
z11=dfx11(x1[k],x2[k]);
z12=dfx12(x1[k],x2[k]);
z21=dfx21(x1[k],x2[k]);
z22=dfx22(x1[k],x2[k]);
do
{
p2=(z2-z12*z1/z11)/(z22-z12*z21/z11);
p1=z1/z11-z12*p2/z11;
while ((f(x1[k]-alfa*p1,x2[k]-alfa*p2)-f(x1[k],x2[k]))>(-q*alfa*(z1*p1+z2*p2)))
alfa=alfa/2;
x1[k+1]=x1[k]-alfa*p1;
x2[k+1]=x2[k]-alfa*p2;
out<<
x1[k+1]<<
//x2[k+1]<<
endl;
z1=dfx1(x1[k+1],x2[k+1]);
z2=dfx2(x1[k+1],x2[k+1]);
k++;
i++;
if(i==3)
{
z11=dfx11(x1[k],x2[k]);
z12=dfx12(x1[k],x2[k]);
z21=dfx21(x1[k],x2[k]);
z22=dfx22(x1[k],x2[k]);
i = 0;
}
// cout<<"k="<
// cout<<"x1="<
N0=0;N1=0;N2=0;
}
//--------------------= Newton-Rafson s opimalnym =---------------------
void NR_opt()
{
ofstream out;
out.open("NR_opt.txt");
int k,m;
double x1[1000],x2[1000],z1,z2,z11,z12,z21,z22,e,p1,p2,alfa_0,alfa,y1,y2,a,b,x1_min,x2_min,f_min;
x1[0]=-1;
x2[0]=0;
e=0.0001;
k=0;
m=0;
alfa_0=1.8;
z1=dfx1(x1[k],x2[k]);
z2=dfx2(x1[k],x2[k]);
do
{
z11=dfx11(x1[k],x2[k]);
z12=dfx12(x1[k],x2[k]);
z21=dfx21(x1[k],x2[k]);
z22=dfx22(x1[k],x2[k]);
p2=(z2-z12*z1/z11)/(z22-z12*z21/z11);
p1=z1/z11-z12*p2/z11;
y1=f(x1[k],x2[k]);
y2=f(x1[k]-(m+1)*alfa_0*p1,x2[k]-(m+1)*alfa_0*p2);
if(y2<=y1)
{
m++;
y1=y2;
}
if(m==0) a=0;
else a=m-1;
b=m+1;
alfa=min_alfa(a,b,x1[k],x2[k],p1,p2);
x1[k+1]=x1[k]-alfa*p1;
x2[k+1]=x2[k]-alfa*p2;
out<<
x1[k+1]<<
//x2[k+1]<<
endl;
z1=dfx1(x1[k+1],x2[k+1]);
z2=dfx2(x1[k+1],x2[k+1]);
k++;
}
while(sqrt(z1*z1+z2*z2)>e);
x1_min=x1[k];
x2_min=x2[k];
f_min=f(x1_min,x2_min);
cout<<"N-R opt "<
N0=0;N1=0;N2=0;
}
//------------------= Newton-Rafson s opimalnym M2 =--------------------
void NR_opt_M2()
{
ofstream out;
out.open("NR_opt_M2.txt");
int k,m,i;
double x1[1000],x2[1000],z1,z2,z11,z12,z21,z22,e,p1,p2,alfa_0,alfa,y1,y2,a,b,x1_min,x2_min,f_min;
x1[0]=-1;
x2[0]=0;
e=0.0001;
k=0;
m=0;
alfa_0=1.8;
z1=dfx1(x1[k],x2[k]);
z2=dfx2(x1[k],x2[k]);
z11=dfx11(x1[k],x2[k]);
z12=dfx12(x1[k],x2[k]);
z21=dfx21(x1[k],x2[k]);
z22=dfx22(x1[k],x2[k]);
do
{
p2=(z2-z12*z1/z11)/(z22-z12*z21/z11);
p1=z1/z11-z12*p2/z11;
y1=f(x1[k],x2[k]);
y2=f(x1[k]-(m+1)*alfa_0*p1,x2[k]-(m+1)*alfa_0*p2);
if(y2<=y1)
{
m++;
y1=y2;
}
if(m==0) a=0;
else a=m-1;
b=m+1;
alfa=min_alfa(a,b,x1[k],x2[k],p1,p2);
x1[k+1]=x1[k]-alfa*p1;
x2[k+1]=x2[k]-alfa*p2;
out<<
x1[k+1]<<
//x2[k+1]<<
endl;
z1=dfx1(x1[k+1],x2[k+1]);
z2=dfx2(x1[k+1],x2[k+1]);
k++;
i++;
if(i == 3)
{
z11=dfx11(x1[k],x2[k]);
z12=dfx12(x1[k],x2[k]);
z21=dfx21(x1[k],x2[k]);
z22=dfx22(x1[k],x2[k]);
i = 0;
}
}
while(sqrt(z1*z1+z2*z2)>e);
x1_min=x1[k];
x2_min=x2[k];
f_min=f(x1_min,x2_min);
cout<<"N-R opt M2 "<
N0=0;N1=0;N2=0;
}
void main ()
{
cout<<"Variant: 6\n"<
cout<<"a="<
cout<<"b="<
cout<<"c="<
cout<<"d="<
cout<<"\nNachalnoe priblizhenie: [-1;0]"<
cout<<"Tochnost': e=0.0001"<
cout<<"---------------------------------------------------------------------------"<
cout<
<
cout<<"---------------------------------------------------------------------------"<
newton();
NR_drob();
NR_drob_M1();
NR_drob_M2();
NR_opt();
NR_opt_M2();
cout<<"---------------------------------------------------------------------------"<
// getch();
}
5. Графики функций

-1 | 0 |
-1,34111 | 0,246733 |
-1,24539 | 0,230932 |
-1,22325 | 0,219726 |
-1,2224 | 0,21473 |
-1,22245 | 0,212833 |
-1,22247 | 0,212118 |
-1,22248 | 0,211848 |
-1,22248 | 0,211746 |
-1,22248 | 0,211708 |

-1 | 0 |
-1,17056 | 0,123367 |
-1,19975 | 0,155406 |
-1,21195 | 0,174146 |
-1,21753 | 0,186201 |
-1,22017 | 0,194251 |
-1,22142 | 0,199714 |
-1,22201 | 0,203452 |
-1,22229 | 0,206018 |
-1,22241 | 0,207783 |
-1,22247 | 0,208998 |
-1,22249 | 0,209834 |
-1,22249 | 0,210411 |
-1,22249 | 0,210807 |
-1,22249 | 0,21108 |
-1,22249 | 0,211269 |
-1,22249 | 0,211398 |
-1,22248 | 0,211487 |
-1,22248 | 0,211549 |
-1,22248 | 0,211591 |
-1,22248 | 0,21162 |
-1,22248 | 0,21164 |
-1 |
0 |
-1,17056 | 0,123367 |
-1,22438 | 0,183631 |
-1,22307 | 0,199733 |
-1,22277 | 0,20665 |
-1,2226 | 0,209552 |
-1,22253 | 0,210782 |
-1,2225 | 0,211303 |
-1,22249 | 0,211523 |
-1,22248 | 0,211616 |
-1,22248 | 0,211656 |

-1 | 0 |
-1,17056 | 0,123367 |
-1,22438 | 0,183631 |
-1,22307 | 0,199733 |
-1,22284 | 0,203446 |
-1,2227 | 0,206005 |
-1,22262 | 0,20777 |
-1,22257 | 0,208988 |
-1,22254 | 0,209827 |
-1,22252 | 0,210405 |
-1,22251 | 0,210804 |
-1,2225 | 0,211078 |
-1,22249 | 0,211267 |
-1,22249 | 0,211397 |
-1,22249 | 0,211487 |
-1,22248 | 0,211548 |
-1,22248 | 0,211591 |
-1,22248 | 0,21162 |
-1,22248 | 0,21164 |
-1 |
0 |
-1,26058 | 0,188479 |
-1,20663 | 0,207955 |
-1,2239 | 0,210511 |
-1,22175 | 0,211623 |
-1,22248 | 0,211661 |
-1,22248 | 0,211684 |

-1 | 0 |
-1,26058 | 0,188479 |
-1,22254 | 0,190938 |
-1,22338 | 0,210726 |
-1,22236 | 0,21104 |
-1,22259 | 0,211679 |
-1,22246 | 0,211648 |
-1,22248 | 0,211677 |
-1,22248 | 0,21168 |
6. Таблица результатов
| Метод: | X1 | X2 | Y | N0 | N1 | N | k |
б) | Градиентный с дроблением шага | -1.22252 | 0.210433 | -9.0329 | 177 | 168 | 345 | 84 |
в) | Наискорейшего спуска | -1.22248 | 0.211684 | -9.0329 | 133 | 14 | 147 | 6 |
д) | Гаусса-Зейделя | -1.22248 | 0.211685 | -9.0329 | 133 | 6 | 139 | 3 |
ж) | Овражий метод I | -1.22247 | 0.211658 | -9.0329 | 33 | 1254 | 1287 | 6 |
к) | Конфигураций | -1.22247 | 0.21167 | -9.0329 | 155 | 0 | 155 | 22 |
м) | Деформируемого симплекса | -1.22326 | 0.21272 | -9.0329 | 26 | 0 | 26 | 13 |
| Метод: | X1 | X2 | Y | N0 | N1 | N2 | N | k |
а) | Ньютона | -1.22248 | 0.211708 | -9.0329 | 1 | 20 | 36 | 57 | 9 |
б) | Н-Р с дроблением | -1.22248 | 0.21164 | -9.0329 | 45 | 44 | 84 | 173 | 21 |
бг) | Н-Р с дроблением (М1) | -1.22248 | 0.211656 | -9.0329 | 23 | 22 | 4 | 49 | 10 |
бд) | Н-Р с дроблением (М2) | -1.22248 | 0.21164 | -9.0329 | 39 | 38 | 28 | 105 | 18 |
в) | Н-Р с оптимальным | -1.22248 | 0.211684 | -9.0329 | 137 | 14 | 24 | 175 | 6 |
вд) | Н-Р с оптимальным (М2) | -1.22248 | 0.21168 | -9.0329 | 169 | 18 | 4 | 191 | 8 |
7. Вывод программы:

8. Вывод:
Как видно из таблицы результатов, наилучшим методом многомерной безусловной оптимизации с точки зрения количества итераций является метод Гаусса-Зейделя, лучший же метод с точки зрения количества экспериментов – это метод деформируемого симплекса.
Среди методов Ньютона же точку минимума за наименьшее число итераций находит метод Ньютона-Рафсона с оптимальным шагом. С точки зрения наименьшего количества экспериментов оптимальной является модификация I метода Ньютона-Рафсона с дроблением шага.