Лабораторная работа №3 - файл MO_lab3_v6.doc

Лабораторная работа №3
скачать (69.3 kb.)
Доступные файлы (9):
MO_lab3_v6.doc453kb.24.12.2008 15:09скачать
NR_drob.txt1kb.24.12.2008 15:09скачать
NR_drob_M1.txt1kb.24.12.2008 15:09скачать
NR_drob_M2.txt1kb.24.12.2008 15:09скачать
NR_opt.txt1kb.24.12.2008 15:09скачать
NR_opt_M2.txt1kb.24.12.2008 15:09скачать
n7.txt1kb.24.12.2008 15:09скачать
n8.cpp
n9.xls29kb.24.12.2008 15:10скачать

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. Задание


  1. Изучить предлагаемые методы безусловной оптимизации второго порядка и метод сопряженных градиентов.

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

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

Вариант задания:
Методы многомерной безусловной оптимизации:
а) Метод Ньютона;

б) Метод Ньютона-Рафсона с дроблением шага;

бг) Модификация 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 метода Ньютона-Рафсона с дроблением шага.

Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации