Методы первого порядка icon

Методы первого порядка



НазваниеМетоды первого порядка
Дата конвертации29.09.2012
Размер51.27 Kb.
ТипДокументы
1. /ЛЕКЦИИ_МО/Двойственность задач ЛП.doc
2. /ЛЕКЦИИ_МО/Линейное программирование.doc
3. /ЛЕКЦИИ_МО/Метод Пауэлла и сопряженные направления.doc
4. /ЛЕКЦИИ_МО/Методы второго порядка.doc
5. /ЛЕКЦИИ_МО/Методы перв_порядка.doc
6. /ЛЕКЦИИ_МО/Методы переменной метрики.doc
7. /ЛЕКЦИИ_МО/Методы штрафных функций.doc
8. /ЛЕКЦИИ_МО/Параметрическое программирование_Р1.doc
9. /ЛЕКЦИИ_МО/Прямые методы.doc
10. /ЛЕКЦИИ_МО/Статистические методы поиска.doc
11. /ЛЕКЦИИ_МО/Трансп. задача с огр..doc
12. /ЛЕКЦИИ_МО/Транспортная задача.doc
Двойственность задачи линейного программирования
Линейное программирование Основные определения и теоремы
Метод Пауэлла и сопряженные направления
Методы второго порядка
Методы первого порядка
Методы переменной метрики
Методы штрафных функций
Параметрическое линейное программирование
Прямые методы
Статистические методы поиска
Транспортная задача с ограничениями на пропускные способности
Методы решения транспортной задачи

Методы первого порядка


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


Алгоритм наискорейшего спуска


Градиент функции в любой точке показывает направление наибольшего локального увеличения . Поэтому при поиске минимума , следует двигаться в направлении противоположном направлению градиента gif" name="object3" align=absmiddle width=57 height=19> в данной точке, то есть в направлении наискорейшего спуска.

Итерационная формула процесса наискорейшего спуска имеет вид

,

или

.

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

,

р
ешая одномерную задачу минимизации с использованием некоторого одномерного метода. В этом случае получаем алгоритм наискорейшего спуска.

Рис.


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

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

Эффективность алгоритма зависит от вида минимизируемой функции. Алгоритм наискорейшего спуска сойдется за одну итерацию при любом начальном приближении для функции , но схо­димость будет очень медленной, например, в случае функции вида . В тех ситуациях, когда линии уровня минимизируемой функции представляет собой прямолинейный или, хуже того, криволинейный "овраг" эффективность алгоритма оказывается очень низкой. Очевидно, что хорошие результаты может давать пред­варительное масштаби­рование функций.

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


Метод сопряженных градиентов


В алгоритме наискорейшего спуска на каждом этапе поиска используется только текущая информация о функции и градиенте . В алгоритмах сопряженных градиентов используется информация о поиске на предыдущих этапах спуска.

Направление поиска на текущем шаге строится как линейная комбинация наискорейшего спуска на данном шаге и направлений спуска на предыдущих шагах . Веса в линейной комбинации выбираются таким образом, чтобы сделать эти направления сопряженными. В этом случае квадратичная функция будет минимизироваться за шаг алгоритма.

При выборе весов используется только текущий градиент и градиент в предыдущей точке.

В начальной точке направление спуска :

, (1)

где выбирается из соображений минимальности целевой функции в данном направлении . Новое направление поиска

, (2)

где выбирается так, чтобы сделать направления и сопряженными по отношению к матрице :

. (3)

Для квадратичной функции справедливы соотношения:

,

где ,

.

Если положить , тогда и

. (4)

Воспользуемся (4), чтобы исключить из уравнения (3). Для квадратичной функции , поэтому

.

Следовательно, для сопряженности и

.

Вследствие изложенных ранее свойств сопряженности все перекрестные члены исчезают. Учитывая, что , получим для следующее соотно­шение:

. (5)

Направление поиска строится в виде линейной комбинации векторов , , , причем так, чтобы оно было сопряженным с . Если распространить сделанные выкладки на , опуская их содержание и учитывая, что приводит к , можно получить общее выражение для :

. (6)

Все весовые коэффициенты, предшествующие , что особенно интересно, оказываются нулевыми.

Полностью алгоритм описывается следующей последовательностью действий:

  1. В точке начального приближения вычисляется .

  2. На -м шаге с помощью одномерного поиска в направлении определяется минимум функции, то есть решается задача



и находится первое приближение .

  1. Вычисляется и .

  2. Определяется направление .

  3. Алгоритм заканчивается, если , где – заданная величина.

П
осле итераций (), если не произошел останов алгоритма, процедура циклически повторяется с заменой на и возвратом на первый пункт алгоритма. Если исходная функция является квадратичной, то ()-е приближение даст точку экстремума данной функции. Описанный алгоритм с построением по формулам (6) соответствует методу сопряженных градиентов Флетчера-Ривса.

Рис.


В модификации Полака-Рибьера (Пшеничного) метод сопряженных градиентов отличается только вычислением

. (7)

В случае квадратичных функций обе модификации примерно экви­ва­лент­ны, однако в модификации Полака-Рибьера алгоритм обычно оказывается не­сколь­ко эффективнее.


Многопараметрический поиск


Милем и Кентреллом предложен метод поиска, основанный на использовании двух подбираемых параметров для минимизации в каждом направлении поиска. В этом алгоритме последовательность действий определяется формулой:

, (1)

где .

На каждом шаге решается задача минимизации по двум параметрам:

.

После чего находится очередное приближение по формуле (1). При этом можно показать, что

, и .

На первом шаге , а должно быть задано. На -м шаге:

  1. Вычисляется , и .

  2. Пользуясь одним из эффективных методов, например, методом Ньютона находятся с требуемой точностью и .

  3. По уравнению (1) вычисляют и переходят к пункту 1.

  4. Каждый ()-й шаг начинается с .

  5. Процесс заканчивается, когда .

На квадратичных функциях алгоритм по эффективности близок к методу сопряженных градиентов.

Крэгг и Леви распространили данный метод на случай большего числа параметров. На каждом шаге при минимизации в заданном направлении решается задача вида

,

а очередное приближение



при .

Достоинства и недостатки такого подхода очевидны.



Похожие:

Методы первого порядка iconДокументы
1. /Камке Э. Справочник по дифференциальным уравнениям в частных производных первого порядка....
Методы первого порядка iconРаботы и биография Уоллеса Кантора статьи
Кантор У. Прямой эксперимент первого порядка по распространению света от движущегося источника // Журнал американского оптического...
Методы первого порядка iconСпециалистам технарям
Говорит цуп ядра зоны слияния матричных пространственных слияний всех форм материи СуперПространства первого порядка со сформирован­ными...
Методы первого порядка iconМетоды исследования белков
Определение первичной структуры белков сводится к выяснению порядка расположения аминокислот в полипептидной цепочке. Эту задачу...
Методы первого порядка iconЗако н вологодской области об установлении порядка и нормативов заготовки древесины, порядка заготовки и сбора недревесных лесных ресурсов, порядка заготовки
Лесных ресурсов, порядка заготовки пищевых лесных ресурсов и сбора лекарственных растений на
Методы первого порядка iconВ 1902 г. Релей повторил опыты Физо с отрицательным результатом [4]
Опыты первого порядка Физо 1858 г по повороту плоскости поляризации были одними из первых попыток определения величины и направления...
Методы первого порядка iconДокументы
1. /Info.txt
2. /Расчет дифференциального уравнения...

Методы первого порядка icon1. Определите длину волны для линии в дифракционном спектре второго порядка, совпадающей с изображением линии спектра третьего порядка, у которого длина волны равна 400 нм. А. 600 нм. Б. 800 нм. В. 200 нм. 2
...
Методы первого порядка iconА. Г. Баранов метод экспериментальной проверки независимости скорости света от скорости источника
Предложена схема прямой экспериментальной лабораторной проверки независимости скорости света от скорости источника, в которой измеряемый...
Методы первого порядка iconВопрос 19. Методы математической статистики в педагогических исследованиях
Появляясь, новые методы сразу привлекают к себе пристальное внимание специалистов
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©podelise.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы

Разработка сайта — Веб студия Адаманов