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


 

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

25079. Біоетика – нормативне знання 56 KB
  Прикладом такого розуміння евтаназії є введення летальної дози препарату термінальному хворому з метою полегшення тяжких страждань. Ще одна відмінність дуже важлива в дискусії з приводу евтаназії. Можливість такої евтаназії розглядається у пацієнтів не здатних приймати самостійні рішення наприклад душевнохворі. Якщо розглядати в сукупності випадки добровільної недобровільної евтаназії з випадками активної пасивної евтаназії можна виділити чотири різновиди евтаназії: 1 добровільна активна; 2 недобровільна активна; 3 добровільна пасивна;...
25080. Біоетика та евтаназія 33.5 KB
  Моральне добро – найбільш узагальнене імперативнооціночне поняття моралі і категорія етики яка виражає позитивне моральне значення явищ суспільного життя в їх співвіднесенні з етичним ідеалом. Добро – це все позитивно оцінюване моральною свідомістю при співвіднесенні з гуманістичними принципами тобто те що сприяє розвитку в людині і суспільстві людяності взаєморозуміння і згоди. Добро є виконання вимог моралі слідування моральному обов’язку.
25081. Поняття добра і зла 35 KB
  Це – вузлові пункти людського пізнання. Добро і зло нерідко розглядають як синонімів понять моральної і аморальне а на саму етику – як вчення про добро і зло. Зло категорія етики за змістом протилежна добру узагальнено якою виражено уявлення про безнравственном що суперечить вимогам моралі заслуживающем осуду. Іммануїл Кант вважав зло необхідним наслідком чуттєвої природи людини.
25082. Смертна кара 36 KB
  Майже всі суспільства людства на певній стадії свого розвитку застосовували смертну кару до кримінальних і політичних злочинців. Деякі країни скасували смертну кару за винятком особливих обставин таких як наприклад зраду під час військових дій. Такі держави як Китай США та інші зберегли смертну кару за злочини окремо визначені законодавством. У країнах які практикують смертну кару метод страти визначається законодавчо.
25083. Глобалізація загострила таку проблему як тероризм 36.5 KB
  Глобальні проблеми групуються навколо трьох фундаментальних напрямків розвитку людства: людинатехніка людинаприрода людина культура. Людинатехніка – використання атомної енергії а також через непрогнозованність наслідків роботи машин що працюють на принципах самовдосконалення і самонавчання. Людинакультура – тенденція до втрати культурних національних рис. Людинаприрода – погіршення екологічної ситуації зростають природні катаклізми та техногенни катастрофи.
25084. Благодійність 33 KB
  Існують різні погляди на благодійність: 1 благодійність немає сенсу і є аморальною тому що а це різновид бізнесу; б інструмент ідеологічного і політичного впливу; в засіб розваги для багатих бо велика помпезність потребує великих грошей і вони більші ніж ті що йдуть для бідних. 2 благодійність має тісний зв’язок з владою а саме з владою церкви яка говорить про милосердя. 3 благодійність і милосердя існують для того щоб мати похвалу від сучасників та залишитись у пам’яті нащадків. 5 благодійність направлена на послаблення...
25085. Етикет 37.5 KB
  Іноді достатньо одного погляду на людину щоб оцінити її смак і манеру вбиратися. Одяг підкреслює гарний смак одних і несмак інших. У здоровому цивілізованому суспільстві панує здоровий естетичний смак. Смак володар моди.
25087. Толерантність 35.5 KB
  Толерантність є необхідною умовою людського співжиття. Толерантність вимагає від людей примирення досягнення компромісу. Толерантність не є насиллям над людською волею позаяк це не людська кара. Приклади толерантності: батьки миряться з певною поведінкою своїх дітей; людина терпить слабкості іншої людини; людина терпить толерантність; монарх терпить інакомислення; релігійна течія терпимо ставиться до гомосексуалів; держава визнає релігійні меншини; суспільство терпимо ставиться до певних форм девіантної поведінки.