Лабораторная работа №3 - файл MO_lab3_v6.doc
Лабораторная работа №3скачать (69.3 kb.)
Доступные файлы (9):
| MO_lab3_v6.doc | 453kb. | 24.12.2008 15:09 | скачать |
| NR_drob.txt | 1kb. | 24.12.2008 15:09 | скачать |
| NR_drob_M1.txt | 1kb. | 24.12.2008 15:09 | скачать |
| NR_drob_M2.txt | 1kb. | 24.12.2008 15:09 | скачать |
| NR_opt.txt | 1kb. | 24.12.2008 15:09 | скачать |
| NR_opt_M2.txt | 1kb. | 24.12.2008 15:09 | скачать |
| n7.txt | 1kb. | 24.12.2008 15:09 | скачать |
| n8.cpp | |||
| n9.xls | 29kb. | 24.12.2008 15:10 | скачать |
- Смотрите также:
- Лабораторные работы (Лабораторная работа)
- Лабораторные работы №2-4 (Документ)
- Журнал лабораторных работ по дисциплине «Технические средства автоматизации в СУТП».(Ишимбай) (Документ)
- Лабораторная работа - Исследование вольтамперной характеристики полупроводникового диода (Лабораторная работа)
- Лепа Р. Информационные системы и технологии предприятий (лабораторный практикум) (Документ)
- Лабораторные работы по гидравлике (Лабораторная работа)
- Черемисинов В.И., Матушкин О.П. Детали машин. Лабораторный практикум. Учебное пособие (Документ)
- Лабораторная работа - Исследование переходных процессов в полупроводниковом диоде (Лабораторная работа)
- Лабораторная работа №1 ТГУ - Делопроизводство (Лабораторная работа)
- Лабораторная работа - Расчет характеристики направленности линейной сплошной гидроакустической антены в С++ (Лабораторная работа)
- Лабораторная работа №3 - Сети Петри (Лабораторная работа)
- Лабораторная работа. ABC - анализ (Лабораторная работа)
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 метода Ньютона-Рафсона с дроблением шага.