|
|
| Строка 1: |
Строка 1: |
|
| |
|
| == Постановка задачи ==
| |
| Рассмотрим задачу поиска минимума функции <math>f(x)\colon \mathbb{R}^n \to \mathbb{R}</math>
| |
| :<math>
| |
| \begin{align}
| |
| f(x) \rightarrow \min_{x \in \mathbb{R}^n}
| |
| \end{align}
| |
| </math>
| |
| Будем считать, что функция <math>f(x)</math> такова, что можно вычислить её градиент.
| |
|
| |
| === Общее описание алгоритма ===
| |
| Наискорейший спуск<ref>, Н. Н. Калиткин “Численные методы.” Москва <<Наука>>, 1978</ref> — это вариант градиентного спуска: метода нахождения локального экстремума функции с помощью движения вдоль направления градиента.
| |
|
| |
| ===Математическое описание алгоритма ===
| |
| Основная идея метода состоит в том, чтобы идти в направлении <math>-\nabla f</math>, то есть в направлении, в котором функция быстрее всего убывает при бесконечно малом движении из данной точки:
| |
| :<math>
| |
| \begin{align}
| |
| x^{k+1} = x^{k} - \lambda^{k}(\nabla f),
| |
| \end{align}
| |
| </math>
| |
| где выбирается <math>\lambda^{k} </math>по следующему правилу: <math>\lambda^{k} = \operatorname{arg}\min_{\lambda} f(x^{k} - \lambda^{k}(\nabla f))</math>.
| |
|
| |
| === Вычислительное ядро алгоритма ===
| |
|
| |
| === Макроструктура алгоритма ===
| |
|
| |
| === Схема реализации последовательного алгоритма ===
| |
|
| |
| === Последовательная сложность алгоритма ===
| |
|
| |
| === Информационный граф ===
| |
|
| |
| === Ресурс параллелизма алгоритма ===
| |
|
| |
| === Входные и выходные данные алгоритма ===
| |
|
| |
| === Свойства алгоритма ===
| |
|
| |
| == Программная реализация алгоритма ==
| |
| === Особенности реализации последовательного алгоритма ===
| |
|
| |
| === Локальность данных и вычислений ===
| |
|
| |
| === Возможные способы и особенности параллельной реализации алгоритма ===
| |
|
| |
| === Масштабируемость алгоритма и его реализации ===
| |
|
| |
| === Динамические характеристики и эффективность реализации алгоритма ===
| |
|
| |
| === Выводы для классов архитектур ===
| |
|
| |
| === Существующие реализации алгоритма ===
| |
|
| |
| == Литература ==
| |
| <references />
| |