Градієнтні методи
Контрольная работа - Математика и статистика
Другие контрольные работы по предмету Математика и статистика
точки мінімуму функції f (x) у яружній ситуації. Більшість із них засновані на евристичні (тобто інтуїтивних, не обґрунтованих строго) міркуваннях. Їх можна застосовувати в ситуаціях, коли застосування більше зроблених методів неможливо або недоцільно, наприклад, значення цільової функції обчислюється зі значними погрішностями, інформація про її властивості недостатня, і т.д. Ці методи прості в реалізації й досить часто застосовуються на практиці, дозволяючи в ряді випадків одержати задовільне рішення задачі.
Схема яружного методу 1.
Евристичні алгоритми
Іноді, використовуючи градієнтний спуск для мінімізації функцій зі складною топографічною структурою, застосовують евристичні схеми, які ідейно близькі до методів спуска. Ми розглянемо дві такі схеми.
Перша евристична схема містить два основних етапи. Обидва етапи являють собою аналоги градієнтного спуска з постійним кроком. Тільки замість градієнта використовується вектор g (x), формований з координат , але на кожному з етапів за різними правилами.
На першому етапі задається мале число 1<<1 і використовується градієнтний спуск, де замість градієнта береться вектор g (x) ={g (1) (x),…,g (n) (x) }, який визначається в такий спосіб:
Таким чином, спуск виробляється лише по тими змінним, у напрямку яких похідна цільової функції досить велика. Це дозволяє швидко спуститися на "дно яру". Ми спускаємося доти, поки метод не зациклиться, тобто доти, поки кожна наступна ітерація дозволяє знайти точку, у якій значення функції менше, ніж значення, знайдене в попередній ітерації. Після цього переходимо до наступного етапу.
На другому етапі задається деяке велике число 2>>1 і використовується процедура спуска, де замість градієнта береться вектор g (x) ={g (1) (x),…,g (n) (x) }, який визначається в такий спосіб:
У цьому випадку переміщення відбувається по "березі" яру уздовж його "дна". Як і на першому етапі, спуск триває доти, поки метод не зациклиться.
Після виконання першого й другого етапів приймається рішення про завершення роботи або продовження. Для цього рівняється норма різниці попередньої точки, тобто точки, що ми мали до застосування першого й другого етапів, з поточною точкою, тобто отриманої після застосування з точністю рішення задачі 1. Якщо ця норма менше 1 і норма градієнта в поточній точці менше 3, то пошук закінчується й остання обчислена точка приймається за наближене рішення задачі. Інакше для поточної точки знову повторюємо перший і другий етапи й т.д.
Схема алгоритму
Крок 1.
Задаються х0, 1, 3,1,2,1 - постійний крок пункту 1 і 2 - постійний крок пункту 2 (1<2). Привласнюється до=0.
Крок 2. (Перший етап).
Із точки хк здійснюється спуск на "дно яру" з постійним кроком 1.
При спуску обчислення чергової точки здійснюється з використанням формул:
xj+1 = xj - 1g (xj), де g (x) ={g (1) (x),…,g (n) (x) },
Нехай цей процес зупиниться в точці xl.
Крок 3. (Другий етап).
Із точки xl здійснюється спуск уздовж "дна яру" з постійним кроком 2. При спуску використовуються формули: xj+1 = xj - 2g (xj), де
g (x) ={g (1) (x),…,g (n) (x) },
Нехай цей процес зупинився в точці xm.
Крок 4.
Якщо ||xk - xm|| 1 і || || 3, то думаємо:
і пошук мінімуму закінчується.
Інакше k=m і переходимо до кроку 2.
2. Завдання на лабораторну роботу
- Вивчити викладені методи багатомірної безумовної оптимізації.
- У відповідність із варіантом завдання, вказаним викладачем, скласти програми для методів багатомірної безумовної мінімізації й знайти точку мінімуму цільової функції f (x) =f (x (1), x (2)) із заданою точністю ? зазначеними методами. Початкове наближення x0 і точність приводяться в умові задачі. Порівняти результати, отримані різними методами для однієї й тієї ж цільової функції (зокрема, порівняти число обчислень цільової функції і її похідних, що знадобилися для одержання заданої точності). Для кожного використаного методу побудувати траєкторію проміжних точок, які одержані на чергових кроках методу й збіжних до точки мінімуму.
- Оформити звіт про виконання завдання із приведенням умови задачі, алгоритмів і програм, зазначених у завданні методів мінімізації, графіків траєкторій проміжних наближень, таблиці результатів порівняння розглянутих методів, висновку за результатами порівняння методів.
Методи
- метод найшвидшого спуску;
- евристичний алгоритм;
Варіанти завдань
Цільова функція f (x) =f (x (1), x (2)) залежить від двох аргументів. Функція f (x) наступного виду:
f (x) =a*x (1) +b*x (2) +ec* (x) +d* (x).
№ вар№ методуЦільова функціяПочаткове
наближенняТочність
розвязкуabcd63, 63-1,20,021,3 (-1; 0) 0,0001
Програма до методу № 1
#include
#include
#include
#include
// ing namespace std;
double f (double x1, double x2)
{ double f;
f=3*x1-1.2*x2+exp (0.02*x1*x1+1.3*x2*x2);
return (f);
}
double df1 (double x1, double x2)
{double f1;
f1=3+0.04*x1*exp (0.02*x1*x1+1.3*x2*x2);
return (f1);
}
double df2 (double x1, double x2)
{double f2;
f2=-1.2+2.6*x2*exp (0.02*x1*x1+1.3*x2*x2);
return (f2);
}
double zsech (double a,double b,double x1k,double x2k,double z1,double z2)
{
double eps=0.0001;
double x1,x2,y1,y2,t;
t= (1+sqrt (5)) /2;
x1=a- (b-a) / (t);
y1=f (x1k-x1*z1,x2k-x1*z2);
x2=a+ (b-a) /t;
y2=f (x1k-x2*z1,x2k-x2*z2);
while ( (b-a) >eps) {
if (y1<=y2) { b=x2; x2=x1; y2=y1; x1=a+b-x2; y1=f (x1k-x1*z1,x2k-x1*z2); }
else { a=x1; x1=x2; y1=y2; x2=a+b-x1; y2=f (x1k-x2*z1,x2k-x2*z2); }
}
// if (y1<y2) b=x2;
// else a=x1;
return ( (a+b) /2);
}
void main ()
{int k, i,N,N0,N1,l1,l2;
double a,b,d,y