432dgdfgd

  • 30 авг. 2012 г.
  • 3212 Слова
Содержание

Введение 7
1. Метод градиентного спуска 8
1.1 Введение в метод………………………………………………………8
1.2 Метод градиентного спуска ………………………………………….8
1.2.1 Идея метода……….…………………………………………….9
1.2.2 Алгоритм………………………………………………………..9
1.2.3 Критерий останова……………………………………………..9
1.2.4 Сходимость градиентного спуска с постоянным шагом…..101.2.5 Выбор оптимального шага…………………………………..11
1.2.6 Градиентный метод с дроблением шага…………………….12
1.2.7 Метод наискорейшего спуска………………………………..13
1.3 Числовые примеры …………………………………………………14
1.3.1 Метод градиентного спуска с постоянным шагом…………14
1.3.2 Градиентный метод с дроблением шага………………...…..15
1.3.3 Методнаискорейшего спуска………………………………..16
1.4 Рекомендации при программировании……………………………16
2. Метод сопряжённых градиентов 18
2.1 Введение в метод…………………………………………………….18
2.2 Постановка задачи оптимизации……………………………..........18
2.3 Метод сопряжённых градиентов для квадратичного функционала.18
2.3.1 Изложение метода…………………………………………….18
2.3.2 Анализ метода ………………………………………………...202.3.2.1 Сходимость метода…………………………………....20
2.3.2.2 Вычислительная сложность…………………………..21
2.3.3 Численный пример……………………………………………21
2.3.4 Заключение…………………………………………………….21
2.4 Метод сопряжённых градиентов в общем случае ……………….22
2.4.1 Анализ метода ………………………………..........................23
2.4.1.1Сходимость метода……………………………………23
2.4.1.2 Вычислительная сложность…………….....................24
2.4.2 Числовой пример……………………………………………...25
2.5 Рекомендации при программировании…………………...............26
Заключение 27
Список литературы: 28
Приложение 29







Введение
Используя градиентные методы, можно найти решение любой задачинелинейного программирования. Однако в общем случае применение этих методов позволяет найти точку локального экстремума. Поэтому более целесообразно использовать градиентные методы для нахождения решения задач программирования, в которых всякий локальный экстремум является одновременно и глобальным. Процесс нахождения решения задачи с помощью градиентных методов состоит в том, что начиная снекоторой точки X(k) осуществляется последовательный переход к некоторым другим точкам, до тех пор, пока не выявляется приемлемое решение исходной задачи.




















Введение в метод

В работе рассматривается задача поиска минимума функции [pic], записываемая в виде:
(1)
[pic]
Пусть функция [pic]такова, что можно вычислить ее градиент. Тогда можно применить методградиентного спуска, описанный в данной статье.
В статье приведены теоремы сходимости метода градиентного спуска, а также рассмотрена его варианты:
• Метод градиентного спуска с постоянным шагом
• Метод градиентного спуска с дроблением шага
• Метод наискорейшего спуска

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

[pic]
[pic]
Рис.1 Геометрическая интерпретация метода градиентного спуска спостоянным шагом. На каждом шаге мы сдвигаемся по вектору антиградиента, "уменьшенному в [pic]раз".

Идея метода

Основная идея метода заключается в том, чтобы осуществлять оптимизацию в направлении наискорейшего спуска, а это направление задаётся антиградиентом [pic]:
[pic]
где [pic]выбирается
• постоянной, в этом случае метод может расходиться;
• дробным шагом, т.е. длина шага в процессеспуска делится на некое число;
• наискорейшим спуском: [pic]

Алгоритм

Вход: функция [pic]
Выход: найденная точка оптимума [pic]
1. Повторять:
2. [pic], где [pic]выбирается одним из описанных выше способов
3. если выполен критерий останова, то возвращаем текущее значение [pic]

Критерий останова

Критерии остановки процесса...
tracking img