Реферат по предмету "Программирование"


Метод Дэвидона-Флетчера-Пауэлла

Министерствонауки, высшей школы и техническойполитикиРоссийской Федерации. НовосибирскийГосударственныйТехническийУ ниверситет.Рефератпо исследованию операций на тему Метод Дэвидона - Флетчера- Пауэлла . Вариант 2. Группа АС-513.Студент Бойко Константин Анатольевич.

Преподаватель Ренин Сергей Васильевич.Дата 19 октября 1997 года. НовосибирскВведение.Первоначально метод был предложен Дэвидоном Davidon 1959 , а затем развит Флетчером и Пауэллом Fletcher, Powell 1963 . Метод Дэвидона - Флетчера -Пауэлла называют также и методом переменной метрики.

Он попадает в общийкласс квазиньютоновских процедур, в которых направления поиска задаются в виде-Djf y . Направление градиентаявляется, таким образом, отклоненным в результате умножения на -Dj , где Dj - положительно определенная симметрическая матрицапорядка n ? n, аппроксимирующая обратную матрицу Гессе. Наследующем шаге матрица Dj 1 представляется в видесуммы Dj и двух симметрических матриц ранга один каждая.

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

направлений. Начальный этап. Пусть gt 0- константа для остановки. Выбрать точку х1 и начальнуюсимметрическую положительно определенную матрицу D1. Положить y1 x1, k j 1 иперейти к основному этапу. Основной этап.Шаг 1.Если f yj lt e, то остановиться в противномслучае положить dj - Djf yj и взять вкачестве ljоптимальное решение задачи минимизации f yj ldj при l sup3 0.

Положить yj 1 yj ljdj. Если j lt n, то перейти к шагу 2. Если j n, то положить y1 xk 1 yn 1,заменить k на k 1, положить j 1 и повторить шаг 1. Шаг 2. Построить Dj 1следующим образом , 1 где pj ljdj, 2 qj f yj 1 - f yj . 3 Заменитьj на j 1 и перейтик шагу 1. Пример. Рассмотрим следующую задачу минимизировать x1 -

2 4 x1- 2x2.Результаты вычислений методом Дэвидона - Флетчера -Пауэлла приведены в таблице 1. Таблица 1. Результаты вычислений по методу Дэвидона - Флетчера -Пауэлла. k xk f xk j yj f yj f yj f yj D dj lj yj 1 1 0.00, 3.00 52.00 1 2 0.00, 3.00 52.00 2.70, 1.51 0.34 -44.00, 24.00 0.73, 1.28 50.12 1.47 44.00, -24.00 -0.67, -1.31 0.062 0.22 2.70, 1.51 2.55, 1.22 2 2.55, 1.22 0.1036 1 2 2.55, 1.22 0.1036 2.45, 1.27 0.0490 0.89,

-0.44 0.18, 0.36 0.99 0.40 -0.89, 0.44 -0.28, -0.25 0.11 0.64 2.45, 1.27 2.27, 1.11 3 2.27, 1.11 0.008 1 2 2.27, 1.11 0.008 2.25, 1.13 0.004 0.18, -0.20 0.04, 0.04 0.27 0.06 -0.18, 0.20 -0.05, -0.03 0.10 2.64 2.25, 1.13 2.12, 1.05 4 2.12, 1.05 0.0005 1 2 2.12, 1.05 0.0005 2.115, 1.058 0.0002 0.05, -0.08 0.004, 0.004 0.09 0.006 -0.05, 0.08 0.10 2.115, 1.058 На каждой итерации вектор dj для j 1, 2определяется в виде Djf yj , где D1 единичная матрица, а D2 вычисляется по формулам 1 -

3 . Приk 1 имеем p1 2.7, -1.49 T, q1 44.73, -22,72 T. На второйитерацииp1 -0.1, 0.05 T, q1 -0.7, 0.8 T и, наконец, на третьей итерацииp1 -0.02, 0.02 T, q1 -0.14, 0.24 T. Точка yj 1 вычисляется оптимизацией вдоль направления dj при начальной точке yj для j 1, 2.Процедура остановлена в точкеy2 2.115, 8 T начетвертой итерации, так как норма f y2 0.006 достаточно мала.

Траектория движения,полученная методом, показана на рисунке 1.Рисунок 1. Лемма 1 показывает, что каждая матрица Dj положительно определена и dj является направлением спуска.Для доказательства леммы нам понадобится Теорема 1. Пусть S - непустое множество в Еn, точка x cl S. Конусом возможных направлений в точке x называется

множество D d d sup1 0, x ld S при всех l 0, d для некоторого d gt 0 .Определение. Пусть x и y - векторы изЕn и xTy - абсолютное значение скалярного произведения xTy. Тогда выполняется следующее неравенство, называемоенеравенством Шварца xTy x y . Лемма 1. Пусть y1 Еn, а D1 начальная положительно определенная симметрическаяматрица. Для j 1, n положим yj 1 yj ljdj, где dj Djf yj , а lj является оптимальным решением задачи минимизации

f yj ldj при l sup0. Пусть, кроме того, дляj 1, n 1 матрица Dj 1 определяется по формулам 1 - 3 . Если f yj sup1 0 дляj 1, n, то матрицы D1, Dn симметрические и положительно определенные, так что d1 dn направления спуска. Доказательство. Проведемдоказательство по индукции. При j 1 матрицаD1 симметрическая и положительно определенная поусловию леммы.

Кроме того, f y1 Td1 f y1 TD1f y1 lt 0, так как D1 положительно определена. Тогда по теореме 1 вектор d1 определяет направление спуска. Предположим, чтоутверждение леммы справедливо для некоторого j n 1, ипокажем, что оно справедливо для j 1.Пусть x ненулевой вектор из En, тогда из 1 имеем 4 Так как Dj симметрическая положительно определенная матрица, то существуетположительно определенная

матрица Dj1 2, такая, что Dj Dj1 2Dj2. Пустьa Dj1 2x и b Dj1 2qj. Тогда xTDjx aTa, qjTDjqj bTb и xTDjqj aTb.Подставляя эти выражения в 4 , получаем 5 По неравенству Шварца имеем aTa bTb sup3 aTb 2. Такимобразом, чтобы доказать, что xTDj 1x sup3 0, достаточнопоказать, что pjTqj gt 0 и bTb gt 0. Из 2 и 3 следует, чтоpjTqj ljdjT f yj 1 f yj .

6 По предположениюf yj sup1 0, и Dj положительно определена, так чтоf yj TDjf yj gt 0. Кроме того, dj направление спуска, и, следовательно, lj gt 0. Тогда из 6 следует, что pjTqj gt 0. Кроме того, qj sup1 0, и , следовательно, bTb qjTDjqj gt 0. Покажем теперь,что xTDj 1x gt 0. Предположим, что xTDj 1x 0. Это возможно только в том случае,если aTa bTb aTb 2и pjTx 0.

Прежде всего заметим, что aTa bTb aTb 2только при a lb, т.е. Dj1 2x lDj1 2qj. Таким образом, x lqj. Так как x sup1 0, то l sup1 0. Далее, 0 pjTx l pjTqj противоречит тому, что pjTqj gt 0 иl sup1 0. Следовательно, xTDj 1x gt 0, т.е. матрица Dj 1 положительно определена. Поскольку f yj 1 sup1 0 и Dj 1положительно определена, имеемf yj 1

Tdj 1 f yj 1 T Dj 1f yj 1 lt 0. Отсюда по теореме 1 следует, что dj 1 направление спуска.Лемма доказана. Квадратичный случай. В дальнейшем нам понадобиться Теорема 2. Пусть f x cTx 1 xTHx, где Н - симметрическая матрица порядка n x n. Рассмотрим Н - сопряженные векторы d1, ,dn и произвольную точку x1. Пусть lk для k 1, , n - оптимальное решение задачи минимизацииf xk ldk при l

Е1 и xk 1 xk ldk. Тогда для k 1, , n справедливы следующие утверждения 1. f xk 1 Tdj 0, j 1, , k 2. f x1 Tdk f xk Tdk 3. xk 1 является оптимальным решением задачи минимизации f x при условииx - x1 L d1, , dk ,где L d1, , dk линейное подпространство, натянутое на векторы d1, ,dk, то есть В частности, xn 1 точка минимума функции f на Еn. Если целевая функция f квадратичная, то в соответствии со сформулированнойниже теоремой 3 направления

d1, , dn, генерируемые методом Дэвидона - Флетчера - Пауэлла,являются сопряженными. Следовательно, в соответствии с утверждением 3теоремы 2 метод останавливается после завершения одной итерации воптимальной точке. Кроме того, матрица Dn 1, полученная в конце итерации, совпадает с обратной кматрице Гессе Н.Теорема 3. Пусть Н симметричная положительно определенная матрица порядка n x n.

Рассмотрим задачу минимизации f x cTx 1 xTHxпри условии x En. Предположим, что задача решена методом Дэвидона -Флетчера - Пауэлла при начальной точке y1 и начальной положительно определенной матрице D1. В частности, пусть lj, j 1, , n, оптимальное решение задачи минимизации f yj ldj при l sup3 0 и yj 1 yj ljdj, где dj -Djf yj , а Dj определяется по формулам 1 3 .

Если f yj sup1 0 для всех j, тонаправленияd1 dn являются Н -сопряженными и Dn 1 H-1. Крометого, yn 1является оптимальным решением задачи.Доказательство.Прежде всего покажем, что для j, такого, что 1 j n, справедливыследующие утверждения 1. d1, ,dj линейно независимы.2. djTHdk 0 для i sup1 k i, k j.3. Dj 1Hpk,или, что эквивалентно, Dj 1Hdk dk для 1 k j, pk lkdk.

Проведем доказательство по индукции. Для j 1 утверждения 1 и 2 очевидны. Чтобы доказатьутверждение 3, заметим прежде всего, что для любого k справедливы равенстваHpk H lkdk H yk 1 -yk f yk 1 f yk qk. 7 В частности, Hp1 q1.Таким образом, полагая j 1 в 1 , получаем, т.е. утверждение 3 справедливо при j 1. Теперь предположим, что утверждения1, 2 и 3 справедливы для j n 1. Покажем, что они также справедливы и для j 1.

Напомним, что по утверждению 1 теоремы 2 diTf yj 1 0 дляi j. Поиндуктивному предположению di Dj 1Hdi, i j. Такимобразом, для i j имеем0 diTf yj 1 diTHDj 1f yj 1 diTHdj 1. Ввиду предположения индукции это равенствопоказывает, что утверждение 2 также справедливо для j 1. Теперь покажем, что утверждение 3справедливо для j 1. Полагая k j 1, имеем. 8 Учитывая 7 и полагая k j 1 в 8 , получим, что

Dj 2Hpj 1 pj 1. Теперь пусть k j. Так как утверждение2 справедливо для j 1, тоpj 1THpk lklj 1dj 1THdk 0. 9 По предположениюиндукции из 7 и вследствие того, что утверждение 2 справедливо для j 1, получаем . 10 Подставляя 9 и 10 в 8 иучитывая предположение индукции, получаем .Такимобразом, утверждение 3 справедливо для j 1. Осталось показать, что утверждение 1справедливо для j 1. Предположим, что . Умножая это равенство на и учитывая, что утверждение 2 справедливо для j 1,

получаем, что . По условию теоремы , а по лемме 1 матрица положительно определена,так что . Так как H положительноопределена, то и, следовательно Отсюда следует, что , и так как d1, , dj линейно независимы по предположению индукции, то для i 1, , j. Таким образом, d1, , dj 1линейно независимы и утверждение 1 справедливо для j 1. Следовательно, утверждения 1, 2 и 3 выполняются. Вчастности сопряж нность d1, , dn следует из утверждений 1

и 2, если положить j n. Пусть теперь j n в утверждении 3. Тогда для k 1, , n. Если в качестве D взять матрицу, столбцами которой являются векторы d1, ,dn, то . Так как D имеетобратную, то , что возможно только в том случае, если . Наконец, является оптимальнымрешением по теореме 2.Теорема доказана. Списоклитературы.1. Базара М Шетти К. Нелинейное программирование.

Теорияи алгоритмы . М 1982.2. Химмельблау Д. Прикладное нелинейноепрограммирование . М 1975.



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

Поделись с друзьями, за репост + 100 мильонов к студенческой карме :

Пишем реферат самостоятельно:
! Как писать рефераты
Практические рекомендации по написанию студенческих рефератов.
! План реферата Краткий список разделов, отражающий структура и порядок работы над будующим рефератом.
! Введение реферата Вводная часть работы, в которой отражается цель и обозначается список задач.
! Заключение реферата В заключении подводятся итоги, описывается была ли достигнута поставленная цель, каковы результаты.
! Оформление рефератов Методические рекомендации по грамотному оформлению работы по ГОСТ.

Читайте также:
Виды рефератов Какими бывают рефераты по своему назначению и структуре.

Сейчас смотрят :

Реферат 1. Здравствуйте. На прошлом уроке мы познакомились с графическим режимом среды Turbo Pascal
Реферат Финансовый рынок 2 Сущность признаки
Реферат Кредитные кооперативы Германии их создание деятельность и развитие
Реферат Реформы в период 1556 - 1560 гг
Реферат Cоциология культуры
Реферат Авторская позиция и средства ее выражения в романе Ивана Тургенева Отцы и дети 2
Реферат Путь Пьера Безухова к счастью
Реферат Познавательные процессы в младшем школьном возрасте 2
Реферат Творча діяльність Панаса Мирного
Реферат Individualism And Fascicm Essay Research Paper IndividualismModern
Реферат Расчет вальцовых механизмов подач деревообрабатывающих станков
Реферат Правові засади виконання дохідної частини бюджету
Реферат Характеристика стада как устойчивого объединения животных
Реферат Творчество М. Зощенко в контексте русской литературы
Реферат Исследование и обоснование направлений увеличения прибыли "УП Витебсклифт"