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

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

положить dj = - Djf(yj) и взять в качестве lj оптимальное решение задачи минимизации f(yj + ldj) при l ³ 0. Положить yj+1 = yj + ljdj. Если j < 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)2. Результаты вычислений методом Дэвидона -