Лабораторная работа №4 «Многомерная безусловная оптимизация» Вариант №4 Выполнил студент группы 8В83

Министерство образования и науки Российской Федерации

Государственное образовательное учреждение высшего профессионального образования

«Национальный исследовательский Томский политехнический университет»

Институт Кибернетики

Кафедра ИПС

Методы оптимизации


ЛАБОРАТОРНАЯ РАБОТА № 4

«Многомерная безусловная оптимизация»

Вариант №4

Выполнил студент группы 8В83		А.В.Колчанов
Проверил		О.В. Березняк

Задание на лабораторную работу
Найти минимум функции f(x) с точностью E=10^-5.

Применить методы:
1. Методом градиентного спуска;
2. Методом Марквардта.

Сравнить методы, для чего найти число итераций, число вычислений функции и ее производных.

 



Ход работы

Функция нахождения y:
double f(X x)

{

fc++;

return x.x1*x.x1+3*x.x2*x.x2+cos(x.x1+x.x2);

}
double fd1(X x)

{

return 2*x.x1+6*x.x2-sin(x.x1+x.x2);

}
double fd2(X x)

{

return 8-cos(x.x1+x.x2);

}


double norm(X x)

{

double x1=2*x.x1*pow(e,0.5*x.x2*x.x2+x.x1*x.x1)+2;

double x2=x.x2*pow(e,0.5*x.x2*x.x2+x.x1*x.x1)-5;;

double norm;

norm=sqrt((x1*x1)+(x2*x2));

return norm;

}
X X2(X x)

{

X a;

double x1=2*x.x1*pow(e,0.5*x.x2*x.x2+x.x1*x.x1)+2;

double x2=x.x2*pow(e,0.5*x.x2*x.x2+x.x1*x.x1)-5;;

a.x1=x.x1-l*(x1);

a.x2=x.x2-l*(x2);

return a;

}

Основная часть программы
void grad(double E)

{

double y=0, ym=1;

X p;

X pminus;

p.x1=0;

p.x2=0;

while(fabs(ym - y) >E){

it++;

ym=y;

y=f(p);

p=X2(p);

int j;

j++;

ymin=y;

xmin=p;

}


}

void markvardt(double E)

{

double m = 1011, k = 0, h[2][2], h_inv[2][2], sk[2], nf, fxk, fxk1;

X p1,p;

p1.x1 = 1.06; p1.x2 = 0;

l = 1e4;

p.x1= p1.x1; p.x2 = p1.x2;

fc=0;

it=0;

int q=0;

double n_grad;

do

{

double dx1;

double dx2;

double dx3;

double tmp;

if(q==0)

{

dx1 = fd1(p);

dx2 = fd2(p);

fc++;

n_grad = norm(p);

t= n_grad ;

tmp = pow(e,0.5*p.x2*p.x2+p.x1*p.x1);

}
h[0][0]=2*tmp+4*p.x1*p.x1*tmp;

h[0][0]+=l;

h[0][1]=2*p.x1*p.x2*tmp;

h[1][0]=2*p.x1*p.x2*tmp;

h[1][1]=tmp+p.x2*p.x2*tmp;

h[1][1]+=l;

double det = h[0][0]*h[1][1]-h[1][0]*h[0][1];

h_inv[0][0] = h[0][0]/det;

h_inv[0][1] = -h[1][0]/det;

h_inv[1][0] = -h[0][1]/det;

h_inv[1][1] = h[1][1]/det;

sk[0] = -(h_inv[0][0]*dx1 + h_inv[0][1]*dx2);

sk[1] = -(h_inv[1][0]*dx1 + h_inv[1][1]*dx2);


p1.x1 = p.x1 + sk[0]; p1.x2 = p.x2 + sk[1];
fxk = fxk1;

p=p1;

fxk1 = f(p1);

it++;

k++;

if(fxk1 < fxk)

{

l = l*0.5;

q=0;

}

else

{

l = l*2;

q=1;

}

xmin=p1;

ymin=fxk;

kk=k;

}while((n_grad > E )&&( k <= m));


}
grad(0.000005);

this->textBox1->Text=""+xmin.x1;

this->textBox2->Text=""+xmin.x2;

this->textBox3->Text=""+ymin;

this->textBox4->Text=""+it;

this->textBox5->Text=""+fc;

fc=0;it=0;

markvardt(0.000005);

this->textBox6->Text=""+xmin.x1;

this->textBox7->Text=""+xmin.x2;

this->textBox8->Text=""+ymin;

this->textBox9->Text=""+it;

this->textBox10->Text=""+fc;

t=(((double)((int)(t*10000000)))/10000000);

this->textBox11->Text=""+kk;
fc=0;it=0;

Результат работы программы



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

Метод марквардта – комбинация метода градиентного спуска и Ньютоновского метода. В методе требуется большое количество вычислений, так как на каждой итерации следует сначала вычислить элементы матрицы n×n, а затем решать систему линейных уравнений.