Метод градиентного спуска

2. Метод градиентного спуска.

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

Пусть, нам нужно найти . Рассмотрим некоторую точку  и вычислим в этой точке градиент функции :

(14)

где  - ортонормированный базис в пространстве . Если , то полагаем:

(15)

где , а  выбирается из условия сходимости итерационного процесса:

(16)

где , а  выбираются из условия сходимости. Формулу (16) можно расписать в виде:

 первое приближение; (17)

 второе приближение; (18)

………………………..

 m-тое приближение; (19)

Здесь m – число итераций. Процесс итерации останавливается, когда достигается требуемая предельная погрешность, т.е. когда выполнены условия остановки итерации:

(20)

Пример 6: Найти минимум функции

Решение: возьмём начальную точку . Из (14) имеем:

(21)

(22)

Составляем итерационную формулу (16):

(23)

Имеем:

(24)

(25)

(26)

Ясно, что если h выбрать так, чтобы , т.е. , то итерация (26) сходится и (27)

Иначе говоря:

(28)

Пример 7: Найти точку минимума функции .

Решение: возьмём начальное приближение , ясно, что . Поэтому, из (16) получаем итерационную формулу:

(29)

Понятно, что

(30)

поэтому:

(31)

(32)

Далее, если , получаем, что , т.е.:

(33)

Пример 8: Найти точки минимума функции .

Решение: выбираем начальную точку (1,1). Составляем итерационную формулу:

(34)

Распишем подробнее:

(35)

(36)

Если перейти к пределу в (36), при и :

(37)

то получим точку минимума (1,-2).

(38)

3. Метод Монте-Карло.

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

В методе Монте-Карло зададим функцию . Выбираем область поиска решения задачи:

(39)

а) Производим случайные броски, т.е. выбираем значения , для каждой переменной  по формуле:

, где (40)

б) Сравниваем значения функции:

(41)

если это неравенство выполняется, то

(42)

если (41) не выполняется, то

(43)

в) Процесс случайных бросков продолжается до достижения заданной точности ; число случайных бросков m удовлетворяет условию:

(44)

Где

(45)

(46)