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

Санкт-Петербургский Государственный

Электротехнический Университет «ЛЭТИ»

ФКТИ САПР

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

«Градиентные методы»

Вариант 1

Выполнили: Буторин

Данилович.

Проверил: Алешкевич П.А.

Санкт-Петербург

2004г

Описание методов оптимизации.

Метод Свенна 4.

Начальный этап. Для запуска метода необходимо:

(1) задать x₀ – начальная точка.

(2) выбрать шаг h равным 0.001 или min{η,|(y₁-y’)/y’₁|}, где η=1,2.

(3) выбрать направление поиска p.

Основной этап

Шаг 1. Установить направление убывания функции. h=h, если y’(x₀,p)<0 и h=-h, если y’(x₀,p)>0.

Шаг 2.Двигаться в направлении р, вычисляя значение функции в точках x_k+1=x_k+h_k*p, h_k=2h_k-1. Пока производная не поменяет знак, т.е. Y’_m-1*Y’_m<0

Шаг 3. Фиксируем начальный интервал: [X_m-1,X_m]

Метод Дэвидона.

Этот метод является аналогом метода кубической аппроксимации в задачах поиска минимума функции нескольких переменных по заданному направлению. Идея метода заключается в том, чтобы на ТИЛ найти аппроксимирующий минимум строя полином 3-го порядка.

Начальный этап:

1. Взять ε, х ₀ – начальную точку поиска, p – направление поиска.

2. Найти начальный шаг α₁ = min{ η,|(y₁-y’)/y’₁|}, где η=1,2. y₁=y(x₁), y’₁ =y’(x₁,p)

3. Получить начальный интервал поиска [a,b] методом Свенна 4.

Основной этап:

1. Найти аппроксимирующий минимум, т.е. точку r по формулам:

r = a+α_r *p

α_r = α _a +γ*( α _b - α_a )

γ=(z-f’_a+W)/(f’_b-f’_a+2*W)

W=√z²-f’_a*f’_b

z=f’_a+f’_b+3*(f_a-f_b)/(b-a)

2. Проверить КОП если Y’r<=ε, то остановиться. X= a+ α_r *p Иначе сократить ТИЛ двумя способами:

Y’r<0 -> [r,b]

Y’r>0 -> [a,r]

Установить k=k+1 и вернуться на шаг 1.

Можно модифицировать алгоритм – ввести смещение точек на α₀ .

Метод Коши

Начальный этап:

Взять ε - погрешность,

х ₀ – начальную точку поиска,

k=1 – счетчик количества итераций.

Основной этап:

Шаг1: Вычислить антиградиентное направление p_k = - grad (y_k );

Шаг2: Найти оптимальный шаг α_k с помощью метода Дэвидона;

Шаг3: Перейти в новую точку:

- x_k+1= x_k + α_k*p_k ;

- k=k+1;

Шаг4: Проверить КОП (любой): ‌

(1) ||∆ x_k|‌|<= e₁

(2) | ∆y_k‌|<= e₂

(3) ||grad (y_k)‌||<= e₃

(4) ||∆ x_k|‌|/(1+||∆ x_k|‌|)<= e₄

(5) ||grad (y_k)‌||/(1+||grad (y_k)‌||)<= e₅

Если КОП выполняется остановимся x_* = x_к+1 , иначе вернуться на

Шаг1.

Спецификация программы.

В прогорамме приведен метод Коши – градиентный метод наискорейшего спуска для функций нескольких переменных. Используется метод Дэвидона и вспомогательный метод Свенна 4 для получения оптимального шага для метода Коши. Присутствуют функции вычисления градиента и функция вычисления производной по направлению в точке. В качестве переменных-векторов используются обьекты класса complex, представляющие собой обьект из двух полей double, т.е. двумерные векторы. Также используются некоторые методы этого класса.

Текст программы.

#include<iostream.h>

#include<math.h>

#include<conio.h>

#include<complex.h>

#include<stdlib.h>

//++++++++++++++++++++++++++++++++++++++++++++++

complex a,b;

double r;

//++++++++++++++++++++++++++++++++++++++++++++++

double f (complex x)

{

return (100*pow(imag(x)-pow(real(x),2),2)+pow(1-real(x),2));

}

//++++++++++++++++++++++++++++++++++++++++++++++

complex grad(complex x)

{

return (complex(400*real(x)*(pow(real(x),2)-imag(x))+2*(real(x)-1),200*(imag(x)-pow(real(x),2))));

}

//++++++++++++++++++++++++++++++++++++++++++++++

double dy (complex x,complex p)

{

return (real(grad(x))*real(p)+imag(grad(x))*imag(p));

}

//++++++++++++++++++++++++++++++++++++++++++++++

void Svenn4(complex x0,complex p)

{

double h=0.001;

if (dy(x0,p)>0) h=-h;

x0=x0+h*p;

while (dy(x0,p)*dy((x0-h*p),p)>=0)

{

h=2*h;

x0=x0+h*p;

}

a=x0-h*p;

b=x0;

}

//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

complex Davidon(complex x0,complex p,double e)

{

double da=real(a-x0)/real(p),db=real(b-x0)/real(p),z,w;

if (da>db)

{

r=db;

db=da;

da=r;

}

a=x0+da*p;

b=x0+db*p;

z=dy(a,p)+dy(b,p)+3*(f(a)-f(b))/(db-da);

w=sqrt(z*z-dy(a,p)*dy(b,p));

r=da+(db-da)*(z-dy(a,p)+w)/(dy(b,p)-dy(a,p)+2*w);

while (dy((x0+r*p),p)>=e)

{

if (dy((x0+r*p),p)<0)

da=r;

else

db=r;

a=x0+da*p;

b=x0+db*p;

z=dy(a,p)+dy(b,p)+3*(f(a)-f(b))/(db-da);

w=sqrt(z*z-dy(a,p)+dy(b,p) );

r=da+(db-da)*(z-dy(a,p)+w)/(dy(b,p)-dy(a,p)+2*w);

}

return x0+r*p;

}

//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

void main ()

{

clrscr();

double e=0.0001;

complex x0,x1,x;

int k=1,n;

do

{

clrscr();

cout<<"1. Startovaya tochka (-1.2,1)"<<endl;

cout<<"2. Startovaya tochka (1.5,2)" <<endl;

cout<<"3. Startovaya tochka (-2,-2)" <<endl;

cout<<"4. Exit";

switch(n=getch())

{

case '1': x0 = complex(-1.2,1);break;

case '2': x0 = complex(1.5,2); break;

case '3': x0 = complex(-2,-2); break;

case '4': exit(1);

}

clrscr();

while (1)

{

complex p = -grad(x0);

Svenn4(x0,p);

x0=Davidon(x0,p,e);

x1=x0+r*p;

k++;

if(abs(grad(x0))<=e && fabs(f(x1)-f(x0))<=e && abs(x1-x0)<=e && abs(x1-x0)/(1+abs(x1-x0))<=e && abs(grad(x0))/(1+abs(grad(x0)))<=e)

break;

}

x=x0;

cout << "Kolichestvo iteracii - k = " << k << endl;

cout << "Optimalniy shag - alfa = " << r << endl;

cout << "Minimum - x* = " << x;

}

while(n!=getch());

getch();

}

Результаты тестирования метода:

Ниже приведена таблица с результатами работы программы для функции f(x) = 100(x₂ - x₁²)² + (1 - x₁)², с различными стартовыми точками и точностями вычисления.

Точность:		0.0001		0.00001		0.000001
Метод Коши	К	x*	K	x*	K	x*
X0=(1.2,1)	6241	(0.999902, 0.999803)	9625	(0.999991, 0.999981)	14207	(0.999999, 0.999998)
X0=(1.5,2)	614	(1.00011, 1.000221)	812	(1.000011, 1.000022)	1106	(1.000001, 1.000002)
X0=(-2,-2)	5704	(0.999899, 0.999797)	7410	(0.99999, 0.99998)	9114	(0.999999, 0.999998)

Выводы:

В данной работе был использован метод Свенна4 и метод Дэвидона для получения оптимального шага. Поиск ведется в пространстве, начиная с заданной начальной точки x₀ по антиградиентному направлению p₀. И в результате выполнения метода Коши находится оптимальный шаг, доставляющий минимум в результате исчерпывающего спуска вдоль антиградиентного направления p_к. Полученный шаг соответствует точке x_* = x_к+1 . Большое количество итераций и неточность минимума объясняется тем, что вблизи минимума для реальных (овражных) функций метод зацикливается, либо рыскает и останавливается.