2. МНОГОМЕРНЫЙ ПОИСК.

НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ.

МЕТОДЫ БЕЗУСЛОВНОЙ МИНИМИЗАЦИИ [l,2,6 - 8]

 

2.3.2. Градиентные методы

Градиентные методы связаны с поиском по направлению гра­диента или антиградиента оптимизируемой функции. Градиент функции  обозначается  и определяется как вектор-столбец из первых частных производных этой функции:

(16)

В каждой точке градиент ортогонален линии уровня f(x1, x2,…, xn)=const ,  проходящей через эту точку,  и направлен в сторону наискорейшего возрастания функции.

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

Процедура вычисления производных целевой функции весьма трудоёмка. На практике их часто приходится вычислять, приближенно,   пользуясь разностными соотношениями.  Например, для функции двух переменных  разностные формулы  имеют  вид:

(17а)

(17б)

 

где  Δx1, Δx2 - некоторые малые приращения аргументов.

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

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

(18)

 

Числа λk выбираются согласно 2.2. В частности, можно для опре­деления λ на (k+1)-ом шаге использовать косинус угла αk между последовательными векторами переходов в процессе спуска от точ­ки Ak+1 до Аk:

(19)

Тогда

(20)

 

В качестве αmin и αmax можно принять, например, углы в 30° и 90°, соответственно.

 

Модификации  градиентных методов.

В зависимости от выбора матриц Нk градиентные методы делят­ся на метод наискорейшего спуска, метод изменения масштабов, ме­тод сопряженных направлений, метод Ньютона, метод Давидона-Флетчера-Пауэлла и другие. Рассмотрим две модификации - наискорейший спуск и метод сопряженных направлений.