42799

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

Курсовая

Физика

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

Русский

2015-08-30

3.14 MB

55 чел.

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

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

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

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

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

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

Выполнил:

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


 

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

81393. Основные этапы институциализации социальной работы 37.22 KB
  На начальном этапе институты социальной работы решали лишь конкретные задачи текущего момента. Затем появляется необходимость передачи накопленного опыта решения конкретных задач и образуется потребность в оформлении первичных теоретических представлений на сложившуюся практику социальной работы. Таким образом сформировалось специфическое образовательное пространство и были заложены основы теоретических обобщений практики социальной работы.
81394. Принципы и методы социальной работы 34.07 KB
  Принципы и методы социальной работы как социального института можно обозначить как сложившиеся правовые и моральные обычаи традиции нормы взаимоотношений между объектами и субъектами социальной работы получившими отражение законодательное и практическое в управлении этим институтом общества. К числу принципов социальной работы относят: гуманизм альтруизма эмпатия сочувствие доверие дифференцированный подход посредничество соблюдение конфиденциальности в работе адресность Система методов социальной работы сложна и многообразна....
81395. Теоретико-категориальный аппарат социальной работы. Понятия «социальная помощь», «социальная защита», «социальная реабилитация», «социальные гарантии» 33.49 KB
  Теоретикокатегориальный аппарат социальной работы. Под социальной защитой можно понимать систему мероприятий осуществляемых обществом и его различными структурами по обеспечению гарантированных минимально достаточных условий жизни поддержанию жизнеобеспечения и деятельного существования человека. Социальная помощь система социальных мер в виде содействия поддержки и услуг оказываемых отдельным лицам или группам населения социальной службой для преодоления или смягчения жизненных трудностей поддержания их социального статуса и...
81396. Антидискриминационная направленность социальной работы. Эйджизм, сексизм и инвалидизм в современном обществе 39.68 KB
  С точки зрения феминистской теории сексизм это проявление патриархата то есть такого устройства общества при котором мужчины как социальная группа обладают властью над женщинами как социальной группой. Для оправдания идеологии сексизма как правило используются эссенциалистские утверждения объясняющие социальное неравенство мужчин и женщин их природными различиями. Исторически женщины были а в некоторых странах остаются ущемлены в гражданских правах по сравнению с мужчинами например лишены избирательных прав. Она может выражаться в...
81397. Явление стигматизации в современном обществе. Виды стигматизации. Приведите примеры проявления 39.99 KB
  В отличие от слова клеймение слово стигматизация может обозначать навешивания социальных ярлыков. В этом смысле стигматизация ассоциация какоголибо качества как правило отрицательного с конкретным человеком или группой людей хотя эта связь отсутствует или не доказана. Стигматизация является составной частью многих стереотипов. Виды социальной стигматизации можно классифицировать следующим образом: Культурная стигматизация социальные ярлыки укоренившиеся в культуре государства либо мировой культуре чукчи недогадливы.
81398. Виктимизация и криминализация как социальное явление 37.5 KB
  Виктимизация это процесс превращения человека в жертву преступления и результат этого процесса как в единичном так и в массовом порядке. Виктимизация Обстоятельства тормозящие нормальное развитие личности человека: Общество и его культура; Низкий уровень жизни; Безработица обычаи и традиции народа; Особенности семейного воспитания; Плохие экологические условия на месте проживания; Слабая социальная поддержка государства Все эти факторы могут превращать в жертву социализации. Виктимизация процесс превращения человека в...
81399. Пенсионеры как объект социальной работы и социологического анализа 38.97 KB
  Роуз согласно которой культура становится стержнем объединяющим людей пожилого возраста создает особую близость между ними и в то же время обосабливает их от других возрастных когорт. Эта теория предполагает возрастную дифференциацию наряду с социальной разделяя людей на группы по их образу жизни и материальному положению. Терапевтические модели образующие фундамент практической работы с пожилыми людьми должны использовать 3 принципа: Изучение индивида в его социальной среде Понимание психосоциологического становления и развития...
81400. Социально-демографическая категория пожилых людей. Основные подходы к рассмотрению процесса ресоциализации пожилых людей 39.08 KB
  Основные подходы к рассмотрению процесса ресоциализации пожилых людей. У людей избравших в старости цель сохранения себя как личности важным является сохранение системы социальных связей и передача своего жизненного опыта. Рассматривая данную стратегию старения ученые отмечают что психика пожилых людей в этом случае отличается ориентировкой на настоящее и отсутствием депрессивной проекции на прошедшее.
81401. Принципы социальной работы с пожилыми людьми и основные аспекты социальной поддержки пожилых людей 39.62 KB
  Принципы социальной работы в отношении пожилых граждан следующие: принцип независимости подразумевает что пожилые люди должны иметь: доступ к основным благам и обслуживанию; возможность работать или заниматься какимилибо видами деятельности приносящей доход; участвовать в определении сроков прекращения трудовой деятельности; сохранять возможность участия в программах образования и профессиональной подготовки; жить в безопасных условиях с учетом личных наклонностей и изменяющегося состояния; получать содействие в проживании в домашних...