Метод Дэвидона-Флетчера-Пауэлла
Министерство науки, высшей школы и техническойполитики Российской Федерации.Новосибирский ГосударственныйТехнический Университет.Реферат по исследованию операций на тему«Метод Дэвидона - Флетчера - Пауэлла».Вариант №2.Факультет: АВТ.Кафедра: АСУ.Группа: АС-513.Студент: Бойко Константин Анатольевич.Преподаватель: Ренин Сергей Васильевич.Дата: 19 октября 1997 года.НовосибирскВведение.Первоначально метод был предложен Дэвидоном (Davidon [1959] ), а затем развит Флетчером и Пауэллом (Fletcher, Powell [1963] ). Метод Дэвидона - Флетчера - Пауэлла называют также и методом переменной метрики. Он попадает в общий класс квазиньютоновских процедур, в которых направления поиска задаются в виде -Djf(y). Направление градиента является, таким образом, отклоненным в результате умножения на -Dj , где Dj - положительно определенная симметрическая матрица порядка n n, аппроксимирующая обратную матрицу Гессе. На следующем шаге матрица Dj+1 представляется в виде суммы Dj и двух симметрических матриц ранга один каждая. В связи с этим схема иногда называется схемой коррекции ранга два.Алгоритм Дэвидона - Флетчера - Пауэлла. Рассмотрим алгоритм Дэвидона - Флетчера - Пауэлла минимизации дифференцируемой функции нескольких переменных. В частности, если функция квадратичная, то, как будет показано позднее, метод вырабатывает сопряженные направления и останавливается после выполнения одной итерации, т.е. после поиска вдоль каждого из сопряженных направлений.Начальный этап. Пусть 0 - константа для остановки. Выбрать точку х1 и начальную симметрическую положительно определенную матрицу D1. Положить y1 = x1, k = j = 1 и перейти к основному этапу.Основной этап.Шаг 1. Если f(yj) , то остановиться; в противном случае положить dj = - Djf(yj) и взять в качестве j оптимальное решение задачи минимизации f(yj + dj) при 0. Положить yj+1 = yj + jdj. Если j n, то перейти к шагу 2. Если j = n, то положить y1 = xk+1 = yn+1, заменить k на k+1, положить j=1 и повторить шаг 1.Шаг 2. Построить Dj+1 следующим образом :,(1)гдеpj = jdj,(2)qj = f(yj+1) - f(yj).(3)Заменить j на j + 1 и перейти к шагу 1.Пример.Рассмотрим следующую задачу :минимизировать(x1 - 2)4 + (x1 - 2x2)2.Результаты вычислений методом Дэвидона - Флетчера - Пауэлла приведены в таблице 1. Таблица 1. Результаты вычислений по методу Дэвидона - Флетчера - Пауэлла.
