Метод многомерной нелинейной оптимизации – метод наискорейшего спуска

лабораторная работа

1. Теоретические основы метода

В этом методе из некоторой начальной точки движение осуществляется вдоль направления градиента до тех пор, пока производная по этому направлению не будет равна нулю. Далее из этой точки определяем новый градиент и т.д. Отличие здесь в том, что длина шага из точки Xk определяется из условия, чтобы обеспечить [2]:

Эту вспомогательную задачу одномерной оптимизации можно решать на основе рассмотренных методов прямого поиска (дихотомии и т.д.)

Наискорейший и покоординатный методы называют методами с длинным шагом. Кроме этого существуют методы, использующие вторую производную для определения длины шага, например, метод Ньютона [2]:

Xk+1=Xk+ [F” (Xk)] - 1g (Xk)

где [F” (Xk)] - 1 - обратная матрица вторых производных в точке Xk.

Рассмотрим нахождение минимума функции двух переменных

.

Задаемся исходной точкой (x0; y0).

1. Сначала найдём частные производные по x и y:

.

нелинейная оптимизация наискорейший спуск

2. Если обе производные в точке (x0; y0) равны нулю, то задача решена, и минимум функции находится в этой точке. В противном случае необходимо определить координаты новой точки (x1; y1):

,

.

3. Теперь полученные значения принимаем за исходные (x1=x0; y1=y0) и возвращаемся к пункту 2.

Шаг t находится из условия минимума функции: . То есть необходимо найти такое значение t, при котором функция имеет минимум. В нашем случае:

;

Минимум этой функции находится из равенства первой ее производной по t к нулю:

Отсюда находим t:

.

Для некоторых нелинейных функций этот процесс не позволяет найти такие значения x и y, при которых производная равнялась бы нулю. Поэтому для обеспечения конечности числа итераций в этом случае вводим точность Е, тогда вычисления прекращаются либо когда производная в точке становится равной нулю (в этом случае значение Е задается равным нулю), либо когда |xk-1 - xk| будет меньше наперед заданной точности Е.

Делись добром ;)