Численные методы решения задач НЛП

В качестве r(x^k) используется направление, в котором наиболее сильно возрастает целевая функция. Это направление задается градиентом функции ÑF(x^k). Суть метода состоит в последовательном приближении к оптимальному решению x^* на основе проведения ряда итераций вида

x^k+1 = x^k + h_k ÑF(x^k), k = 0,1,.... (1)

Алгоритмы, построенные на основе градиентного метода, носят итерационный характер; итерация состоит в выполнении ряда шагов.

0. Исходное состояние. Задается начальная точка x^o, некоторое малое
e ≥ 0; k = 0.

1. Рассчитывается градиент в точке x^k; ÑF(x^k).

2. Задается шаг h_k.

3. Находится x^k+1 = x^k + h_k ÑF(x^k).

4. Проверяется условие ║x^k+1 - x^k║ ≤ e, или ║ÑF(x^k)║ ≤ e.

Если данное условие выполняется, то счет окончен; если нет, то k = k+1 и производится переход на шаг 2.

В пункте 2 задается шаг, обеспечивающий смещение решения в направлении градиента (возрастания целевой функции). Шаг h_k следует выбирать таким, чтобы обеспечивалось приращение целевой функции в направлении ÑF(x^k), т.е. должно выполняться условие F(x^k+1) > F(x^k). Вместе с тем, если h_k очень велик, то возможны ситуации, когда F(x^k+1) < F(x^k); если же h_k очень мал, то процесс долго сходится (см. рис.3.3.1).

Рис. 3.3.1.

 

В зависимости от способа выбора h_k на каждой итерации выделяют различные модификации алгоритма.