Лекции Дудорова(Оптимизация.) / lection_dudarov / Лекция 12

Лекция 12

Градиентные методы оптимизации функции нескольких переменных

В основе группы градиентных методов лежит вычисление и анализ производных целевой функции (R).

Для случаев функции одной переменной рассматривается отношение

Для случаев функции нескольких переменных рассматривается система отношений

К данной группе методов относятся:

• метод релаксации;

• метод градиента;

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

Алгоритм метода релаксации сводится к отысканию осевого направления, вдоль которого целевая функция уменьшается (для случая решения задач минимизации) наиболее сильно.

1. Задаётся начальная точка поиска (x₀) и определяются значения частных производных в этой точке.

2. Направление наискорейшего убывания функции определяется по абсолютной величине (максимальной) производной и её знаку. Если знак отрицательный, функция убывает в направлении оси.

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

4. В найденной промежуточной точке минимума целевой функции (x^(p)) вновь определяются значения производных по всем переменным, кроме изменявшейся на предыдущем этапе, и выбирается новое направление, поиск в котором продолжается с п. 3.

5. Условие окончания поиска:

(1)

При возникновении зацикливания и невыполнении условия (1) шаг поиска точки минимума уменьшается вдвое, после чего процедура возобновляется с п. 2.

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

Возможная проблема метода – остановка «на дне» овражных функций.

Задание 1. Найти минимум функции методом поочерёдного изменения переменных с начальной точкой (0, 0), точностью 0,1 и начальным шагом изменения переменных 0,8.

x1	x2	R	dR/dx1	dR/dx2
0	0	8	4	-6
0	0,8	6,4	7,2	2
-0,8	0,8	1,92	4	-1,2
-1,6	0,8	0	0,8	-4,4
-1,6	1,6	-0,32	4	3,6
-2,4	1,6	-2,24	0,8	0,4
-3,2	1,6			-2,8
-2,8	1,6			-1,2
-2,6	1,6	-2,32	0	-0,4
-2,6	1,8			1,6
-2,6	1,7			0,6
-2,6	1,65	-2,3275	0,2	0,1
-2,65	1,65	-2,3325	0	-0,1
-2,65	1,7			0,4

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

Алгоритм метода следующий.

1. Задаётся начальная точка поиска (x₀) и определяются значения частных производных в этой точке.

2. Выполняется шаг в направлении, обратном направлению градиента:

(2)

Направление наискорейшего убывания функции рассчитывается по соотношению:

(3)

Шаг поиска оптимума переменный и определяется углом поворота градиента на предыдущем этапе вычислений:

где _min, _max – допустимые углы поворота градиента, ^(k) – угол поворота градиента на текущем шаге, определяемый из выражения:

3. Процедура заканчивается при выполнении условия (1).

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

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

Главное преимущество данного метода по сравнению с методом градиента заключается в значительном сокращении объёма вычислений за счёт отсутствия необходимости считать на каждом шаге градиент целевой функции.

Алгоритм метода следующий.

1. Задаются начальный шаг поиска и начальная точка поиска (x₀) и вычисляются значения частных производных в этой точке.

2. По формуле (3) рассчитывается направление наискорейшего убывания функции.

3. В полученном направлении выполняется последовательность шагов (2) до тех пор, пока целевая функция убывает. По достижении промежуточного оптимума шаг поиска уменьшается вдвое.

4. Процедура п./п. 2, 3 повторяется до выполнения одного из условий окончания (1), (4).

(4)

Задание 2. Найти минимум функции методом наискорейшего спуска с начальной точкой (0, 0), точностью 0,1 и начальным шагом изменения переменных 0,8.

x1	x2	b1	b2	h	R	dR/dx1	dR/dx2	e
0	0	0,5547	-0,83205	0,8	8	4	-6	10
-0,44376	0,66564	0,974794	-0,22311	0,8	3,65881	4,88752	-1,11864	6,006159
-1,2236	0,844126	0,71125	-0,70294	0,8	0,466503	2,482123	-2,45312	4,935243
-1,7926	1,406477	0,939612	0,342241	0,8	-1,37654	2,455528	0,894393	3,349921
-2,54429	1,132685				-1,13909
-2,16844	1,269581	0,200388	-0,97972	0,4	-1,83984	0,404563	-1,97795	2,382514
-2,2486	1,661468	0,713816	0,700333	0,4	-1,99233	1,651489	1,620295	3,271785
-2,53412	1,381334	-0,25441	-0,9671	0,4	-2,0424	-0,61115	-2,32314	2,934293
-2,43236	1,768173	0,566832	0,823833	0,4	-2,07688	1,343265	1,952301	3,295566
-2,65909	1,438639	-0,36489	-0,93105	0,4	-2,08015	-0,8818	-2,24996	3,131763
-2,51313	1,811059	0,501099	0,86539	0,4	-2,09326	1,19171	2,058063	3,249772
-2,71357	1,464903				-2,08754
-2,61335	1,637981	0,80114	-0,59848	0,2	-2,32965	0,098518	-0,0736	0,172115
-2,77358	1,757676				-2,30798
-2,69347	1,697829	0,085069	0,996375	0,1	-2,33038	0,017454	0,204425	0,221879
-2,66156	1,684349	0,419505	0,907753	0,0125	-2,33136	0,091156	0,19725	0,288406
-2,67035	1,675458	0,269052	0,963126	0,0125	-2,33305	0,020447	0,073193	0,09364