Лабораторная работа № 28 Метод покоординатного спуска

Метод применяется для отыскания минимума функции n пе­ре­менных. Находится некоторое начальное приближение ⁽⁰⁾ точки минимума функции. Затем выбирается направление спуска парал­лель­но оси 0х₁ и решается задача одномерной минимизации функции. Величина ₀ определяется из условия

.

Определяется первое приближение точки минимума а все остальные координаты остаются без изменения. При следующем уточнении точки минимума спуск производится вдоль линии, параллельной оси 0х₂. Величина ₁ определяется из условия

.

Затем определяется второе приближение точки минимума а все остальные координаты остают­ся без изменения. Аналогичным способом спуск продолжается в на­правлении следующих координат. После этого спуск снова на­чи­на­ется в направлении первой, второй и т. д. координаты. Про­цесс заканчивается при выполнении условия

grad f(^(k+1)) <  .

Пример. Найти минимум функции

f (x₁,x₂) = 2x₁ - 3x₂ + exp (x₁² + x₂⁴).

Решение. Задачу решим методом покоординатного спуска. Возь­мем  = 0,001. В качестве начального выберем вектор = (0;0). Тогда

grad f = + grad

 grad   3,60555.

Составим функцию которую нужно минимизировать по параметру . Для минимизации этой функции применим метод дробления шага. Результаты вычисле­ний занесены в табл. 6.

Можно считать, что минимум функции достига­ет­ся в точке =(- 0,547; 0,743) и равен -1,493638.

Таблица 6

k
0	(0; 0)	1	2	-3	3,605551
1	(-0,652918; 0,00000)	0,225747	0,000005	-3	3,000000
2	(-0,652918; 0,720492)	-1,462048	-0,618545	-0,000015	0,618545
3	(-0,558881; 0,720492)	-1,489943	-0,000007	-0,323116	0,323116
4	(-0,558881; 0,740601)	-1,493255	-0,063737	-0,000017	0,063737
5	(-0,548115; 0,740601)	-1,493597	-0,000004	-0,035558	0,035558
6	(-0,548115; 0,742701)	-1,493634	-0,006869	-0,000011	0,006869
7	(-0,546942; 0,742701)	-1,493638	0,000002	-0,003863	0,003863
8	(-0,546942; 0,742927)	-1,493638	0,000742	-0,000023	0,000742

Задание. Методом покоординатного спуска найти минимум функции где k — номер фамилии студента в журнале преподавателя. Значения х₁ и х₂, в которых функция достигает минимума, определить с точностью  = 0,0001. Начальное приближение найти методом случайного поиска.

Лабораторная работа № 29 Метод случайного поиска

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

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

Пример. Найти минимум функции

Решение. При решении этой задачи в области [(-1;0);(0;1)] при N = 32000 были получены следующие результаты: x₁ = -0,541633; x₂ = 0,742442; F = -1,493550. При повторном решении задачи при этих же условиях были получены результаты, отличающиеся в третьем знаке после запятой от приведенных выше, так как при повторном решении разыгрываются другие значения вектора и результаты решения задачи несколько изменяются.

Задание. Методом случайного поиска найти минимум функ­ции

где k — номер фамилии студента в журнале преподавателя. При вычислениях взять N = 10000. Запустить программу три раза. Сравнить полу­чен­ные результаты.