рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

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

Работа сделанна в 1997 году

Метод Дэвидона-Флетчера-Пауэлла - Реферат, раздел Программирование, - 1997 год - Министерствонауки, Высшей Школы И Техническойполитикироссийской Федерации.но...

Министерствонауки, высшей школы и техническойполитикиРоссийской Федерации.НовосибирскийГосударственныйТехническийУ ниверситет.Рефератпо исследованию операций на тему Метод Дэвидона - Флетчера- Пауэлла . Вариант 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.

– Конец работы –

Используемые теги: метод, Дэвидона-Флетчера-Пауэлла0.057

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Метод Дэвидона-Флетчера-Пауэлла

Что будем делать с полученным материалом:

Если этот материал оказался полезным для Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Еще рефераты, курсовые, дипломные работы на эту тему:

Статистические показатели себестоимости продукции: Метод группировок. Метод средних и относительных величин. Графический метод
Укрупненно можно выделить следующие группы издержек, обеспечивающих выпуск продукции: - предметов труда (сырья, материалов и т.д.); - средств труда… Себестоимость является экономической формой возмещения потребляемых факторов… Такие показатели рассчитываются по данным сметы затрат на производство. Например, себестоимость выпущенной продукции,…

Методы решения жестких краевых задач, включая новые методы и программы на С++ для реализации приведенных методов
Стр. 8. Второй алгоритм для начала счета методом прогонки С.К.Годунова.Стр. 9. Замена метода численного интегрирования Рунге-Кутта в методе прогонки… Стр. 10. Метод половины констант. Стр. 11. Применяемые формулы… Стр. 62. 18. Вычисление вектора частного решения неоднородной системы дифференциальных уравнений. Стр. 19. Авторство.…

Сравнение эффективности методов сортировки массивов: Метод прямого выбора и метод сортировки с помощью дерева
При прямом включении на каждом шаге рассматриваются только один очередной элемент исходной последовательности и все элементы готовой… Полностью алгоритм прямого выбора приводится в прогр. 3. Таблица 2. Пример… Можно сказать, что в этом смысле поведение этого метода менее естественно, чем поведение прямого включения.Для С имеем…

Методы, применяемые на эмпирическом и теоретическом уровнях познания. Развитие методов познания
За тысячелетия своего развития оно прошло длительный и тернистый путь познания от примитивного и ограниченного ко все более глубокому и… В своей работе я буду рассматривать понятие и классификацию методов научного… Это система принципов, приемов, правил, требований, которыми необходимо руководствоваться в процессе познания.…

Метод конечных разностей или метод сеток
Суть метода состоит в следующем. Область непрерывного изменения аргументов, заменяется дискретным множеством точек узлов, которое называется сеткой… Такие системы часто называют разностными схемами. И эти схемы решаются… По нашей области G построим равномерные сетки Wx и Wy с шагами hx и hy соответственно . Wx xiihx, i0,1 N, hxNa Wy…

Метод конечных разностей или метод сеток
Суть метода состоит в следующем. Область непрерывного изменения аргументов, заменяется дискретным множеством точек (узлов), которое называется… И эти схемы решаются относительно неизвестной сеточной функции. Далее мы будем… Для решения будем использовать итерационный метод Зейделя для решения сеточных задач.По нашей области G построим…

Решение систем линейных алгебраических уравнений методом простых итераций и методом Зейделя
При использовании итерационных процессов, сверх того, добавляется погрешность метода. Заметим, что эффективное применение итерационных методов существенно зависит… Сейчас разберем несколько определений которые будем использовать в этой работе.Система линейных уравнений с n…

Методы системного анализа. Метод анализа иерархий
украЇнсЬка Інженерно педагогІчНА академІя... Тарасенко О П...

Метод контурных токов, метод узловых потенциалов
При пользовании методом сначала выбирают и обозначают независимые контурные токи (по любой ветви должен протекать хотя бы один выбранный ток). -… Расчёт установившегося режима в цепи переменного тока комплексным методом… МЕТОД УЗЛОВЫХ ПОТЕНЦИАЛОВ Метод позволяет уменьшить количество уравнений системы до числа , где Ny – число узлов…

Інтерференція світлових хвиль. Когерентність світлових хвиль, Методи спостереження інтерференції світла. Метод графічного додавання амплітуд світлових хвиль
Інтерференція світла це складання полів світлових хвиль від двох або декількох порівняно невеликого числа джерел У загальному випадку...

0.039
Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • По категориям
  • По работам