42799

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

Курсовая

Физика

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

Русский

2015-08-30

3.14 MB

57 чел.

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

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

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

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

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

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

Выполнил:

студент 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


 

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

5594. Сравнительные исследования и анализ нововременных концепций времени 95 KB
  Что такое время. Этот вопрос с давних пор волновал человека. Ибо время постоянно присутствует в нашей жизни, определяет ее ход. На вопрос: что такое время? - мыслители разных эпох отвечали по-разному. В одну эпоху господствовала одна т...
5595. Яйца и яичные продукты. Технологические характеристики и химический состав яиц 120 KB
  Вводная часть. Яйца содержат большинство известных питательных веществ и являются низкокалорийным продуктом (2 яйца - 180 калорий). В яйцах содержится полноценный и легкоусвояемый набор белков, поэтому они полезны в качестве гарнира. Можно пода...
5596. Сенсорная алалия как лексико-грамматическое нарушение речи 78 KB
  Алалия относится к разряду органических речевых нарушений центрального характера. В настоящее время термином алалия принято обозначать тяжелое нарушение речи, обусловленное недоразвитием или поражением речевых областей в левом доминантном...
5597. Обеспечение качества воздушной среды. Защита от вредных веществ и обеспечение параметров микроклимата 193.5 KB
  Обеспечение качества воздушной среды. Защита от вредных веществ и обеспечение параметров микроклимата. Причины и характер загрязнения воздушной среды. Действие вредных веществ загрязнителей воздушной среды на человека. Нормирование...
5598. Международная торговля и торговая политика. Перспективы их развития 196 KB
  Почему государства торгуют? Что составляет основу торговли между странами? В общем виде международная торговля является средством, с помощью которого страны могут развивать специализацию, повышать производительность своих ресурсов и таким о...
5599. Особенности проведения аудита на предприятиях. Курс лекций 519.5 KB
  Аудит в системе финансового контроля Российской Федерации. Понятие аудиторской деятельности Виды аудита Цели и задачи аудита Виды сопутствующих аудиту услуг Понятие аудиторской деятельности С возникновением...
5600. Законы Ньютона 27.5 KB
  Законы Ньютона. Кинематика устанавливает законы движения материальной точки, но не указывает причины вызвавшие это движение, а также факторы, влияющие на вариации кинематических параметров движения. Законы Ньютона, сформулированные более 300 лет наз...
5601. Введение потребителей в заблуждение 96 KB
  Введение потребителей в заблуждение Другой формой недобросовестной конкуренции является: введение потребителей в заблуждение относительно характера, способа и места изготовления, потребительских свойств, качества товаров. Введение потребителей в з...
5602. Кинематика. Механическое движение 55.5 KB
  Кинематика Механическим движением называется изменение положения предмета относительно заданной системы отсчета. Понятие системы отсчета включает в себя тело отсчета и систему координат. Для большинства задач нашего курса достаточно ограничиться пря...