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

Министерствонауки, высшей школы и технической

политикиРоссийской Федерации.

НовосибирскийГосударственный

ТехническийУниверситет.

Рефератпо исследованию операций на тему

«

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

Вариант№2.

Факультет:

АВТ.

Кафедра:

АСУ.

Группа:

АС-513.

Студент:

БойкоКонстантин Анатольевич.

Преподаватель:

РенинСергей Васильевич.

Дата:

19октября 1997 года.

Новосибирск

Введение.

Первоначальнометод был предложен Дэвидоном

(Davidon [1959]), а затем развит Флетчером и Пауэллом (Fletcher, Powell [1963] ). МетодДэвидона — Флетчера — Пауэлла называют также и методом переменной метрики. Он попадает в общий классквазиньютоновских процедур, в которых направления поиска задаются в виде -Dj<img src="/cache/referats/1177/image004.gif" v:shapes="_x0000_i1026">f(y).Направление градиента является, таким образом, отклоненным в результатеумножения на -Dj, где Dj- положительно определенная симметрическая матрица порядка n хn, аппроксимирующая обратную матрицу Гессе. На следующем шагематрица Dj+1представляется в виде суммы Djи двух симметрических матриц ранга один каждая. В связи с этим схема иногданазывается схемой коррекции ранга два.

АлгоритмДэвидона — Флетчера — Пауэлла.

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

Начальный этап.

Пусть<img src="/cache/referats/1177/image006.gif" v:shapes="_x0000_i1027">

>0- константа для остановки. Выбрать точку х1 и начальную симметрическуюположительно определенную матрицу D1. Положить y1 = x1, k = j = 1 и перейти к основному этапу.

Основной этап

.

Шаг 1.

Если çê<img src="/cache/referats/1177/image004.gif" v:shapes="_x0000_i1028">f(yj)çê< e, то остановиться; в противном случаеположить dj =-Dj<img src="/cache/referats/1177/image004.gif" v:shapes="_x0000_i1029">f(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. Построить

(1)

где

pj = ljdj, (2)

qj= <img src="/cache/referats/1177/image004.gif" v:shapes="_x0000_i1031">f(yj+1)- <img src="/cache/referats/1177/image004.gif" v:shapes="_x0000_i1032">f(yj). (3)

Заменить

j на j + 1 и перейти к шагу 1.

Пример.

Рассмотримследующую задачу :

минимизировать

(x1 — 2)4 + (x1 — 2x2)2.

Результатывычислений методом Дэвидона — Флетчера — Пауэлла приведены в таблице 1.

Таблица 1.

Результаты вычислений по методу Дэвидона — Флетчера — Пауэлла.

k

xk

f(xk)

j

yj

f(yj)

<img src="/cache/referats/1177/image004.gif" v:shapes="_x0000_i1033">f(yj)

çê<img src="/cache/referats/1177/image004.gif" v:shapes="_x0000_i1034">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 определяется ввиде
–Dj<img src="/cache/referats/1177/image004.gif" v:shapes="_x0000_i1042">f(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, 1.058)Tначетвертой итерации, так как норма çêf(y2) çê=0.006 достаточно мала. Траектория движения, полученная методом, показана нарисунке 1.

Рисунок 1.

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

Лемма1 показывает, что каждая матрица

Dj положительно определена и dj является направлением спуска.

Длядоказательства леммы нам понадобится :

Теорема 1

.Пусть S- непустое множество в Еn,точка x Î cl S. Конусом возможных направлений в точке x называется множество D = {d: d ¹ 0, x + ld Î S при всех l Î (0, d) для некоторого d> 0}.

Определение.

Пусть x и y - векторы из Еn и |xTy| — абсолютноезначение скалярного произведения xTy. Тогда выполняется следующеенеравенство, называемое неравенствомШварца: |xTy|£||x|| ||y||.

Лемма1.

Пусть

y1ÎЕn, а D1 – начальная положительно определеннаясимметрическая матрица. Для j = 1, ..., nположим yj+1= yj + ljdj, где dj = –Dj<img src="/cache/referats/1177/image004.gif" v:shapes="_x0000_i1044">f(yj),аlj является оптимальным решением задачи минимизации f(yj + ldj) при l ³ 0. Пусть, кроме того, для
j = 1, ..., n – 1 матрицаDj+1 определяетсяпо формулам (1) — (3).Если <img src="/cache/referats/1177/image004.gif" v:shapes="_x0000_i1045">f(yj)¹0 для
j = 1, ..., n, томатрицы D1,..., Dn симметрическиеи положительно определенные, так что d1, ..., dn – направленияспуска.

Доказательство.

Проведем доказательство по индукции. При

j = 1 матрица D1 симметрическая и положительноопределенная по условию леммы. Кроме того,
<img src="/cache/referats/1177/image004.gif" v:shapes="_x0000_i1046">f(y1)Td1= –<img src="/cache/referats/1177/image004.gif" v:shapes="_x0000_i1047">f(y1)TD1<img src="/cache/referats/1177/image004.gif" v:shapes="_x0000_i1048">f(y1)< 0,так как D1положительно определена. Тогда по теореме 1 вектор d1 определяет направление спуска.Предположим, что утверждение леммы справедливо для некоторого j £ n – 1, и покажем, что оно справедливо для j+1. Пусть x – ненулевой вектор из En, тогда из (1) имеем

еще рефераты

Еще работы по программированию, базе данных

Реферат по программированию, базе данных

Метод деформируемого многогранника

29 Августа 2013

Реферат по программированию, базе данных

Защита информации от несанкционированного доступа методом криптопреобразования ГОСТ

29 Августа 2013

Реферат по программированию, базе данных

Концепция создания и функционирования в России автоматизированной базы правовой информации

29 Августа 2013

Реферат по программированию, базе данных

Речевые технологии

29 Августа 2013