6.3. Многомерная оптимизация.

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

Рассмотрим задачу вида:

Метод покоординатного спуска (градиента) формирует шаг по переменным как функцию от градиента R(x) в текущей точки последовательности. Градиент – это вектор из частных производных, который показывает направление и скорость возрастания функции.

Алгоритм поиска minR(x) в векторной форме записывается в виде: , или в скалярном виде: , где h – величина рабочего шага, i – номер шага. Поиск максимума можно производить в обратном направлении градиента, т.е. или заменить на поиск минимума противоположной функции.

Выбор величины рабочего шага в направлении градиента зависит от величины градиента и сильно влияет на эффективность метода. Существует ряд алгоритмов коррекции величины h. Остановимся на выборе постоянного рабочего шага.

Для оценки частных производных можно применить алгоритм с парными пробами:

, где g_j – пробный шаг по j-й переменной, выбираемый достаточно малым.

Условием окончания поиска может являться , где

Основным недостатком метода является необходимость частого вычисления производных.

Метод наискорейшего спуска сочетает в себе метод градиента и методы одномерной оптимизации.

Алгоритм метода:

1. Выбирается начальная точка.

2. В текущей точке вычисляется градиент.

3. В направлении вычисленного градиента ищется любым методом одномерной оптимизации. Наиболее часто используется сканирование до первого локального минимума. Полученная точка локального минимума считается следующей точкой последовательности.

4. Повторяются пункты 2 и 3 до выполнения условия окончания

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

ЗАДАЧА 6.2.

Требуется найти минимум функции

1. Рассмотрим метод покоординатного спуска.

Выберем ; h=0,1; g=0,01; ε=0,01

Делаем рабочий шаг и получаем:

Результаты дальнейших шагов сведем в таблицу:

№	х1	х2	dR/d х1	dR/d х2	/gradR/	R
2	0,002	0,280	-2,78	-4,8	5,547	1,375
3	0,302	0,568	-2,7258	-1,7280	3,2274	-2,5060
4	0,575	0,741	-2,0085	-1,0368	2,2603	-,34002
…
14	1,000	0,998	-0,005	-0,0063	0,0063	-4,0000

Получили grad R(x)=0,0063<0,01, следовательно, поиск можно прекратить.

x₁=1; x₂=0,998; R(x)=-4

2. При тех же начальных значениях рассмотрим метод наискорейшего спуска.

№	х1	х2	dR/d х1	dR/d х2	/gradR/	R
1	-0,5	-1	-2,25	-8	8,31	7,375
1	-0,5-0,1(-2,25)= -0,275	-1-0,1(-8)=-0,2	-2,25	-8	8,31	1,6842
1	-0,050	0,6	-2,25	-8	8,31	-1,5301
1	0,175	1,4	-2,25	-8	8,31	-2,1996

В следующей точке (0,4; 0,2) значение R(x)=-0,256>-2,196. Поэтому в найденной точке снова вычисляем градиент и по нему совершаем шаги до тех пор, пока не найдем наилучшую точку.

№	х1	х2	dR/d х1	dR/d х2	/gradR/	R
2	0,175	1,4	-2,9081	1,6	3,3192	-2,1996
2	0,466	1,24	-2,9081	1,6	3,3192	-3,1811
2	0,757	1,08	-2,9081	1,6	3,3192	-3,8239
2	1,047	0,92	-2,9081	1,6	3,3192	-3,9804

ПРИМЕЧАНИЕ. Если начальная точка выбрана вдали от локального экстремума, то метод спуска может привести к неограниченному убыванию функции.

Задание 6.2.

Закончить поиск минимума по методу наискорейшего спуска.