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

Величина шага в рекуррентном соотношении: для переменной i на j +1 итерации вычисляется с использованием градиента целевой функции R(x), т.е. . При этом шаг может определяться с использованием градиента в одной (текущей) или в двух (текущей и предыдущей) точках. На­правление градиента, как известно, показывает направления наискорейшего возрас­тания функции, а его модуль — скорость это­го возрастания. Поисковые методы оптимизации содержат субъ­ективно задаваемые па­раметры, которые су­щественно влияют на эффективность поиска, вследствие чего один и тот же метод может дать совершенно различные траектории поиска. Среди этих методов выделим метод сопряжённых градиентов и метод Ньютона.

3.9. Методы оптимизации 1-ого порядка

Из курса математики известно, что направление наибольшего возрастания функции характеризуется ее градиентом. Если критерий оптимизации задан уравнением: f(х1,…xn), то его градиент в некоторой точке О (из области определения функции ) определяется вектором:

(6)

Известно, что направление вектора градиента совпадает с направлением наибольшего возрастания функции f в данной точке. Противоположное направление - это направление наиболее крутого убывания. Если критерий оптимизации задан аналитически, то вычисление градиента не представляет принципиальных трудностей. Однако, при оптимизации химико-технологических систем критерий оптимизации, как правило задан в виде неявной функции.

В этом случае частные производные в точке O находят приближенными методами.

(7)

Δ. -бесконечно малое приращение (1 - 5% от значения i - ой переменной).

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

Метод градиента. Опишем принцип использования метода градиента на примере функции двух переменных f= f(Х1 , Х2 ). Этот принцип без изменения переносится на любое число переменных.

Рис.6.

Пусть в начальный момент значения X1 и Х2 соответствуют точке Мо (см. рис.6). Цикл расчета начинается с серии пробных шагов. Сначала величине X1 дается небольшое приращение > 0, причем в это время Х2 неизменно. Затем определяется полу

ченное при этом приращение Δf, величины f, которое можно считать пропорциональным значению величины частной производной. Далее производится приращение величины X2. В это время X1 - const. Получаемое при этом приращение величины f является мерой другой частной производной. После нахождения составляющих градиента делается рабочие шаги в направлении вектора градиента, если стоит задача определения максимума и в направлении противоположном, если решается задача поиска минимума.

, (8)

, i=1,2 , k=0,1,2,...,.

.

Таким образом определяются новые значения X1 и Х2 , соответствующие точке М1. После каждого рабочего шага оценивается приращение Δf величины f. Если Δf >0 при поиске максимума или Δf<0 при поиске минимума, то движение происходит в правильном направлении, иначе необходимо уменьшить величину шага. В качестве примера рассмотрим задачу поиска минимума функции: f(X)=X1**2+25*X2**2.

Примем величину шага h =1, Δ X1 = Δ X2 = 0.05. В качестве исходной точки поиска возьмём точкуX0 =(2,2). Поиск минимума осуществляем следующими этапами (см. таблицу1):

Таблица1.

Шаг	X1		Х2								S1k		S2k		f
1	2		2	4.050		101.25			101.250		-0.040		-0.999		104.00
1	1.960		1.001	3.970		51.30			51.453		-0.077		-0.997		28.89
1	1.883		0.004	3.816		1.45			4.082		-0.035		-0.355		3.55
1	0.948		-0.351	1.94		-16.30			16.416		-0.119		0.993		3.98
Величина Δf>0,поэтому уменьшаем шаг вдвое.
0.5		1.416			-0.174		2.882	-7.45		7.988		-.0180		0.466		2.76
0.5		1.236			0.292		2.552	15.85		16.049		-0.079		0.494		3.66
Величина Δf>0,поэтому уменьшаем шаг вдвое.
0.25		1.326			0.059		2.702	4.20		4.994		-0.135		-0.21		1.84

Метод Коши (наискорейшего спуска или крутого восхождения). При использовании градиентного метода в задачах оптимизации основной объем вычислении приходится обычно на вычисление градиента целевой функции в каждой точке траектории спуска. Поэтому целесообразно уменьшить количество таких точек без ущерба для самого решения. Это достигается в методе Коши ( наискорейшего спуска). Согласно этому методу, после определения направления поиска оптимума в начальной точке, в этом направлении делают не один шаг, а двигаются до тех пор пока происходит улучшение функции, достигая таким образом, экстремума в не которой точке. В этой точке вновь определяют направление поиска (с помощью градиента) и ищут новую точку оптимума целевой функции и т.д. (см. рис.7 ). В этом методе поиск происходит более крупными шагами, и градиент функции вычисляется в меньшем числе точек ( рис.7). Заметим, что метод наискорейшего спуска сводит многомерную задачу оптимизации к последовательности одномерных задач оптимизации, которые могут решаться, например, методом золотого сечения или половинного деления.

а) б)

Рис. 7. Метод наискорейшего спуска.

а) Поиск максимума с выбором оптимального шага.

б) Сравнение с методом градиента.

Величину шага h можно определить из условия минимума f(Xk+hk*Sk):

(9)

Пример. В качестве примера рассмотрим задачу поиска минимума функции:

f(X)=X1**2+25*X2**2.

Таблица 2.

Этап	Шаг hk	X1	Х2			f
0		2	2	4.050	101.25	104.00
1	2.003	1.92	-0.003	3.84	-0.15	3.19
2	1.85	0.07	0.07	0.14	3.5	0.13
3	0.07	0.07	-0.000			0.0049

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

(или менее), если шаги предпринимаются в так называемых сопряжённых направлениях. Вектор S1 называют сопряжённым вектору S0 ,если

, (9)

где

Пример. Пусть f(X)=X12+X22-4 , X0=(4,4). Пусть

Обозначим координаты вектора S1(S11,S12). Тогда

или

Отсюда S11+√3*S12=0. Добавим условие, чтобы длина вектора была равна 1: . Отсюда находим: . Вычислим градиент функции в исходной точке - . По формуле (9) находим:

, , h=-5.86

Тогда

Метод вторых производных. Метод Ньютона. В соответствие с этим методом:

, (10)

матрица обратная матрице Гессе. Матрица Гессе

. (11)

Пример. Найти минимум функции Розенброка:

. В качестве исходной точки поиска примем X=[-0.5 0.5}T. f(X)=8.5

f(x)=2.33