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

Цель работы: Приобретение практических способностей в разработке программ поиска бесспорного экстремума функций многих переменных способом наискорейшего спуска.

Работа производится с внедрением алгоритмических языков высочайшего уровня.

На работу отводится 8 часов.

Способ наискорейшего спуска - это процесс, на каждой итерации которого шаг выбирается из условия минимума функции в направлении движения:

При всем этом на Метод наискорейшего спуска. каждой итерации нужно решать задачку одномерной оптимизации (одномерного поиска экстремума).

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

Метод способа золотого сечения [3].

1. Ищется исходный отрезок , в каком находится экстремум:

от Метод наискорейшего спуска. точки делается поочередная серия растущих шагов в направлении поиска.

При всем этом запоминаются 3 последние точки.

Процесс производится до того времени, пока не будет больше, чем

Тогда разыскиваемый интервал равен

2. Уточняется область нахождения экстремума: k:=0;

2.1. Находятся точки

2.2. Рассчитывается значение функции

2.3. Переопределяется интервал и точки X1, X3:

если

если

если

то выбирается хоть какой Метод наискорейшего спуска. из рассмотренных выше вариантов

Процедура одномерного поиска длится до того времени, пока не будет достигнута данная точность, т.е. пока Dk не будет меньше D доп.

После определения величины a (в формуле 1) способом одномерного поиска, находится новое значение многомерной точки Xk+1, в какой вновь выделяется градиент функции Метод наискорейшего спуска.

Итерационный процесс длится до того времени, пока не будет достигнута требуемая точность вычисления экстремума, т.е. пока не выполнится условие :

При маленький размерности места En может быть найдено аналитическое выражение для рационального значения a. Для этого формула (1) записывается в очевидном виде как функция от a:

Потом берется производная от по a и Метод наискорейшего спуска. равняется нулю. В итоге решения приобретенного уравнения находится наилучшее значение a.

Если минимизируемая функция квадратичная, то наилучшее значение a на k - ой итерации может быть определено из векторного равенства [2]

(2)

где X1 - вектор - строчка X;

- нормированный антиградиент;

- норма вектора;

H - матрица вторых производных (матрица Гессе).

Рассмотренные выше способы подразумевают вычисление градиента Метод наискорейшего спуска. минимизируемой функции в аналитическом виде. Если мотивированная (минимизируемая) функция очень сложна, чтоб ее дифференцировать аналитически, то составляющие градиента, являющиеся личными производными по оптимизируемым переменным, аппроксимируются разностными соотношениями:

(3)

где di - малые отличия.

Для функции 2-ух переменных для численного вычисления градиента необходимо отыскивать значения функции всего в 3-х точках


metod-sociometricheskih-izmerenijsociogramma.html
metod-sopostavimih-rinkov.html
metod-sozdaniya-obfuskatora-s-redaktiruemim-algoritmom-obfuskacii-tezisi-dokladov.html