Безусловная многомерная оптимизация

Уфимский  Государственный Авиационный Технический  Университет

Кафедра Автоматизации Проектирования Информационных Систем

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Лабораторная  работа №2

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

 

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

 

Вариант 10

 

 

 

 

 

 

 

 

 

 

 

 

Проверил:

Хасанов А.Ю.

 

 

 

 

 

Уфа  2009

 

 

Содержание

 

Цель работы….………………………………..……………………………3

Задание….…………………………………...…………………............…..3

Постановка  задачи………………………………………………………….4

График функции……………………………………………………………4

Блок-схемы………………………………………………………………….5

1. Поиск по образцу……………………………………….............................5
2. Метод деформируемого симплекса …………………………………….6-8
3. Метод симплекса………………………………………………………..9-10
4. Градиентный метод с дроблением шага…………………..………....11-12
5. Метод наискорейшего спуска……………………..............................13-14
6. Подпрограмма Золотое сечение………………………………………….15
7. Метод Гаусса-Зейделя.………………………………………………..16-17
8. Эвристический алгоритм……………………………………………...18-19

Листинг программы…………………………………………………...20-33

Графики траекторий промежуточных приближений……………….34-36

Результирующая  таблица и вывод……………………………………...37

 

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

 

Задание:

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

2.В соответствие  с вариантом задания, определенным  преподавателем,    составить  программы реализующие методы  многомерной безусловной минимизации  и найти точку минимума целевой  функции f(x)=f(x⁽¹⁾, x⁽²⁾) с заданной точностью e указанными методами. Начальное приближение x₀ и точность e приводятся в условие задачи. Сравнить результаты, полученные разными методами для одной и той же целевой функции (в частности, сравнить число вычислении целевой функции и её производных, понадобившихся для получения заданной точности). Для каждого применяемого метода построить траекторию промежуточных точек, получаемых на очередных шагах метода и сходящихся к точке минимума.

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

 

 

Методы многомерной безусловной  оптимизации:

 

                  а) поиск по образцу;

              б) метод деформируемого симплекса;

              в) метод симплекса;

              г) градиентный метод с дроблением шага;

              д) метод наискорейшего спуска (дихотомия);

              е) метод Гаусса-Зейделя (золотое сечение);

              ж) эвристический алгоритм.

            

 

 

 

 

 

 

    

 

 

Постановка задачи:

Целевая функция f(x)=f(x⁽¹⁾, x⁽²⁾) зависит от двух аргументов. Функция f(x) следующего вида:

f(x)=a*x₁+b*x₂+

 

№	Целевая функция				Начальное приближение	Точность решения
	a	b	c	d
10	25	0,9	0,35	0,35	(1;0)	0,0004

 

График функции:

 

 

 

                       

                   

                    

 

         

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                

             

Подпрограмма double ZS(double a,double b,double x1k,double x2k,double z1,int n)

 

              е) метод Гаусса-Зейделя

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

              

 

 

Листинг программы:

#include <iostream.h>

#include <math.h>

#include <conio.h>

#include <stdlib.h>

#include <iomanip.h>

#include <stdio.h>

#include <ctype.h>

#include <strstrea.h>

 

struct znach_x

{double x1,x2;

};

 

int N0=0,N1=0;

double f(double x1,double x2)

{double y;

N0++;

y=25*x1+0.9*x2+exp(0.35*pow(x1,2)+0.35*pow(x2,2));

 

return y;

}

 

double dfx1(double x1,double x2)

{double y;

N1++;

y=25+0.7*x1*exp(0.35*pow(x1,2)+0.35*pow(x2,2));

return y;

}

 

 

double dfx2(double x1,double x2)

{double y;

N1++;

y=0.9+0.7*x2*exp(0.35*pow(x1,2)+0.35*pow(x2,2));

return y;

}

 

 

void poiskpoobrazcu()

{const int L=1000;

znach_x x[L];

znach_x x_,k;

double y[L],h,eps,ymin,y_,t;

int i,N,l,p;

cout<<"Vvedite bazovuyu tochku:/n"<<endl;

cout<<"x0(x1,x2) ";cout<<endl;

cout<<"x1 = ";

cin>>x[0].x1;

cout<<"x2 = ";

cin>>x[0].x2;

cout<<"Vvedite shag:\n";

cout<<"h = ";cin>>h;

cout<<"Vvedite tochnost':\n";

cout<<"e = "; cin>>eps;

N=0;

y[0]=25*x[0].x1+0.9*x[0].x2+exp(0.35*(x[0].x1*x[0].x1+x[0].x2*x[0].x2));

cout<<"y0 = "<<y[0]<<endl; N++;

p=0;

t=0;

while(true)

{p++;

x[1].x1=x[0].x1+h;

x[1].x2=x[0].x2+h;

x[2].x1=x[0].x1-h;

x[2].x2=x[0].x2+h;

x[3].x1=x[0].x1-h;

x[3].x2=x[0].x2-h;

x[4].x1=x[0].x1+h;

x[4].x2=x[0].x2-h;

/*cout<<"x[0].x1="<<x[0].x1<<" x[0].x2="<<x[0].x2<<endl;

cout<<"x[1].x1="<<x[1].x1<<" x[1].x2="<<x[1].x2<<endl;

cout<<"x[2].x1="<<x[2].x1<<" x[2].x2="<<x[2].x2<<endl;

cout<<"x[3].x1="<<x[3].x1<<" x[3].x2="<<x[3].x2<<endl;

cout<<"x[4].x1="<<x[4].x1<<" x[4].x2="<<x[4].x2<<endl;

getch();

 

cout<<endl; */

for (i=1;i<=4;i++)

 

{ if ((x[i].x1==k.x1)&&(x[i].x2==k.x2)) {y[i]=t; continue;}

  y[i]=25*x[i].x1+0.9*x[i].x2+exp(0.35*(x[i].x1*x[i].x1+x[i].x2*x[i].x2));

  N++;

  cout<<y[i]<<endl;

}

 

ymin=y[0];

 

for (i=1;i<=4;i++)

  if (y[i]<ymin) {ymin=y[i];l=i;}

cout<<"ymin = "<<ymin<<endl;

 

if (y[l]<y[0]) { k=x[0];t=y[0];

x[0]=x[l];

y[0]=y[l];

continue;

       }

     else if (h>eps) {h=h/2.0;continue;}

    else break;

 

}

 

 

x_=x[0];y_=y[0];

cout<<"Resultat:\n";

cout<<"x_(x1,x2) = x_( "<<x_.x1<<","<<x_.x2<<" )"<<endl;

cout<<"y_ = "<<y_<<endl;

cout<<"Kol-vo iteracii: N = "<<N<<endl;

cout<<"p="<<p<<endl;

}

 

 

void diform_simplex()

{

int k=0,l1,l2,m=0,N;

double e,x1[3],x2[3],y[4],r,beta,gamma,alfa,c1,c2,u1,u2,d,v1,v2,z,x1_min,x2_min,f_min;

cout<<"Vvedite bazovuyu tochku:/n"<<endl;

cout<<"x0(x1,x2) ";cout<<endl;

cout<<"x1 = ";

cin>>x1[0];

cout<<"x2 = ";

cin>>x2[0];

cout<<"Vvedite tochnost':\n";

cout<<"e = "; cin>>e;

cout<<"Vvedite dlinu storoni:\n";

cout<<"r = "; cin>>r;

cout<<"Vvedite alfa:\n";

cout<<"alfa = "; cin>>alfa;

cout<<"Vvedite beta:\n";

cout<<"beta = "; cin>>beta;

cout<<"Vvedite gamma:\n";

cout<<"gamma = "; cin>>gamma;

 

x1[1]=x1[0]+r;

x2[1]=x2[0];

x1[2]=x1[0];

x2[2]=x2[0]+r;

 

cout<<"Nachalnii simplex:"<<endl;

cout<<"V1: x1="<<setw(4)<<x1[0]<<"  x2="<<x2[0]<<endl;

   cout<<"V2: x1="<<setw(4)<<x1[1]<<"  x2="<<x2[1]<<endl;

cout<<"V3: x1="<<setw(4)<<x1[2]<<"  x2="<<x2[2]<<endl;

 

y[0]=25*x1[0]+0.9*x2[0]+exp(0.35*(x1[0]*x1[0]+x2[0]*x2[0]));

y[1]=25*x1[1]+0.9*x2[1]+exp(0.35*(x1[1]*x1[1]+x2[1]*x2[1]));

y[2]=25*x1[2]+0.9*x2[2]+exp(0.35*(x1[2]*x1[2]+x2[2]*x2[2]));

cout<<y[0]<<" "<<y[1]<<" "<<y[2]<<endl; N=3;

do

{

k++;

l1=0;

l2=0;

if (y[1]<y[0])

l1=1;

else l2=1;

if(y[2]<y[l1])

l1=2;

if(y[2]>y[l2])

l2=2;

for (int i=0;i<3;i++)

if((i!=l1)&&(i!=l2))

m=i;

d=sqrt((pow((y[l2]-y[l1]),2)+pow((y[m]-y[l1]),2))/2);

if(d<e){break;}

{

c1=0,c2=0;

for(int i=0;i<3;i++)

if(i!=l2)

{

c1=c1+x1[i];c2=c2+x2[i];

}

c1=c1/2;

  c2=c2/2;

u1=c1+alfa*(c1-x1[l2]);

u2=c2+alfa*(c2-x2[l2]);

y[3]=25*u1+0.9*u2+exp(0.35*(u1*u1+u2*u2));

  N++;

if(y[3]<y[l1])

{

v1=c1+beta*(u1-c1);

  v2=c2+beta*(u2-c2);

z=25*v1+0.9*v2+exp(0.35*(v1*v1+v2*v2));

  N++;

if(z<y[3])

{

 

x1[l2]=v1;x2[l2]=v2;y[l2]=z;  //optim

 

}

else

{

x1[l2]=u1;x2[l2]=u2;y[l2]=y[3];   //optim

}

    cout<<setw(5)<<k;

cout<<setw(14)<<x1[l2]<<setw(14)<<x2[l2]<<endl;

}

else

{

if(y[3]>y[m])

{

if(y[3]<y[l2])

  {

v1=c1+gamma*(u1-c1);v2=c2+gamma*(u2-c2);

 

}

else

{

v1=c1+gamma*(x1[l2]-c1);v2=c2+gamma*(x2[l2]-c2);

 

}

z=25*v1+0.9*v2+exp(0.35*(v1*v1+v2*v2));

  N++;

if((z<y[l2])&&(z<y[3]))

{

x1[l2]=v1;x2[l2]=v2;y[l2]=z;   //optim

}

else

{

for(int i=0;i<3;i++)

{

if(i!=l1)

{

x1[i]=(x1[i]+x1[l1])/2;

x2[i]=(x2[i]+x2[l1])/2;

y[i]=25*x1[i]+0.9*x2[i]+exp(0.35*(x1[i]*x1[i]+x2[i]*x2[i]));;;

N++;

}

    cout<<setw(5)<<k;

      cout<<setw(14)<<x1[i]<<setw(14)<<x2[i]<<endl;

     }

           }

           cout<<setw(5)<<k;

         cout<<setw(14)<<x1[l2]<<setw(14)<<x2[l2]<<endl;

 

}

else

{

x1[l2]=u1;x2[l2]=u2;y[l2]=y[3];

cout<<setw(5)<<k;

cout<<setw(14)<<x1[l2]<<setw(14)<<x2[l2]<<endl;

 

}

}

}

    }

while(d>e);

x1_min=x1[l1];

x2_min=x2[l1];

f_min=25*x1_min+0.9*x2_min+exp(0.35*(x1_min*x1_min+x2_min*x2_min));

cout<<"Resultat:\n";

cout<<"x_(x1,x2) = x_( "<<x1_min<<","<<x2_min<<" )"<<endl;

cout<<"y_ = "<<f_min<<endl;

cout<<"Kol-vo icpitanii: N = "<<N<<endl;

cout<<"k= "<<(k-1)<<endl;

}