42799

Метод Флетчера-Ривса

Курсовая

Физика

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

Русский

2015-08-30

3.14 MB

52 чел.

Государственное образовательное учреждение высшего профессионального образования «Пермский государственный университет»

Механико-математический факультет

Кафедра процессов управления и

информационной безопасности

Курсовая работа по методам оптимизиции

Метод Флетчера-Ривса

Выполнил:

студент III курса

очной формы обучения

группы

Научный руководитель:

к.ф.-м.н., доцент кафедры ПУиИБ

Лутманов Сергей Викторович


Введение

Пусть дана функция f(x), ограниченная снизу на множестве Rn и имеющая непрерывные частные производные во всех его точках. Требуется найти локальный минимум функции на множестве допустимых решений. В теории оптимизации f называется целевой функцией.

Все описываемые градиентные методы основаны на итерационной процедуре, реализуемой в соответствии с формулой

Где  - текущее приближение к решению  ; - параметр, характеризующий длину шага; - направление поиска управляемых переменных x.Способ определения  и  на каждой итерации связано с особенностями применяемого метода. Рассмотрим простейшие градиентные методы.

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

Второйметод наискорейшего градиентного спуска, где величина шага  определяется для каждого значения k из условия:

,  .

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

Более подробно рассмотрим метод Флетчера-Ривса. Относительно невысокий уровень требований к объему памяти ЭВМ делает метод Флетчера-Ривса и его модификации особенно полезным при решении задач большой размерности.

1. Градиентный метод Флетчера-Ривса

Постановка задачи

Пусть дана функция f(x), ограниченная снизу на множестве Rn и имеющая непрерывные частные производные во всех его точках.

Требуется найти локальный минимум функции f(x) на множестве допустимых решений X=Rn, т.е. найти такую точку , что f(x*)=min f(x).

Стратегия поиска

Стратегия метода Флетчера-Ривса состоит в построении последовательности точек {xk}, k=0,1,, таких, что f (xk+1)< f (xk), k=0,1,. Точки последовательности {xk} вычисляются по правилу:

x k + 1 = x k +t d k, k = 0,1,…;

d k =  +βk-1 d k -1;

d0 = ;

βk-1 = ;

Точка x0 задается пользователем, величину шага t выбираем постоянной.

Вычисление величины βk -1 обеспечивает для квадратичной формы построение последовательности Н-сопряженных направлений d0, d1,.., dk,. При этом в точках последовательности {xk} градиенты функции f(x) взаимно перпендикулярны.

Для квадратичных функций f(x) метод Флетчера-Ривса является конечным и сходится за число шагов, не превышающих размерность вектора x.

Алгоритм

Шаг 1. Задать x0, ε1>0, ε2>0, M –предельное число итераций, t - длина шага. Найти градиент ;

Шаг 2. Положить k = 0;

Шаг 3. Вычислить ;

Шаг 4. Проверить выполнение критерия окончания ;

Шаг 5. Проверить условие :

  1.  если неравенство выполняется, то расчет окончен и  ;

б) если нет, то при k = 0 перейти к шагу 6, а при  перейти к шагу 7.

Шаг 6. Определить 

Шаг 7. Определить .

Шаг 8. Определить 

Шаг 9. Вычислить 

Шаг 10. Проверить выполнение условий

,  :

а) в случае выполнения обоих условий в двух последовательных итерациях с номерами k и k - 1 расчет окончен, найдена точка  ;

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

Тестовый пример

Применим градиентный метод Флетчера-Ривса для нахождения локального минимума функции:

Задаем начальные условия:

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

,  .

Текст программы, выполненной в системе Wolfram Mathematica,

Тестовый пример:

Найти локальный минимум функции  .

Задача оптимизации

Исследовать величину скорости и ускорения точки С на минимум по параметрам a, b, t.


Скорость:

Ускорение:


Литература

1. Лутманов С.В. Курс лекций по методам оптимизацииРХД Ижевск, 2001.

2. Пантелеев А.В., Летова Т.А. Методы оптимизации в примерах и задачах. М: Высш. шк., 2005


 

А также другие работы, которые могут Вас заинтересовать

66174. Правила работы в микробиологической лаборатории. Иммерсионный микроскоп. Шаровидные бактерии. Простые методы окраски 108 KB
  Знание морфологии бактерий имеет большое значение для микроскопического метода лабораторной диагностики инфекционных заболеваний. Изучение морфологии бактерий осуществляется при микроскопии окрашенных микроскопических препаратов.
66175. Основные свойства вирусов и современные методы диагностики вирусных заболеваний 255.5 KB
  Вирусы - мельчайшие микробы («фильтрующиеся агенты»), не имеющие клеточного строения, белоксинтезирующей системы, содержащие один тип нуклеиновой кислоты (только ДНК или РНК). Вирусы, являясь облигатными внутриклеточными паразитами, репродуцируются в цитоплазме или ядре клетки.
66176. З’єднання однопроволочних проводів 2.4 MB
  Мета: Виконати з’єднання однопроволочних проводів різними способами та визначити переваги та недоліки запропонованих способів. Виконати з’єднання однопроволочних проводів за наступними схемами.
66177. Вивчення та заповнення форм технічної документації 181.5 KB
  В господарстві необхідно мати таку документацію: Журнал обліку електрообладнання Журнал обліку освітлювальних приладів і внутрішніх проводок Графік технічних обслуговувань на квартал Графік поточних ремонтів на рік...
66179. Лабораторная диагностика гриппа и ОРЗ 89 KB
  Выявлены в последние годы новые свойства возбудителя гриппа способность обмениваться генетической информацией с возбудителями гриппа животных и птиц длительное время сохраняться в организме человека...
66181. Розрахунок трудомісткості робіт експлуатації електрообладнання 259 KB
  Системою ПЗРЕсг установлюється періодичність технічного обслуговування і ремонту для всіх видів електрообладнання. В ній також указується і річні затрати праці для кожного типу обладнання і виду робіт в залежності від умов експлуатації.
66182. Вибрионы. Спирохеты. Жгутики у бактерий. Изучение подвижности 107.5 KB
  Актуальность темы. Знание морфологии вибрионов и спирохет имеет большое значение для микроскопического метода лабораторной диагностики инфекционных болезней. Изучение морфологии осуществляется как у окрашенных с помощью иммерсионного микроскопа...