Пример 3.10. Метод Дэвидона — Флетчера — Пауэлла
С помощью метода Дэвидона — Флетчера — Пауэлла найти точку минимума функции
f(х) = 4x 
+ 3x 
– 4x 
x 
+ x ,
если х(0) = [0, 0] 
.
Решение
Шаг 1.Положим s(0) = – 
f(х(0)) = – [1, 0] .
Шаг 2.Поиск вдоль прямой приводит к результату, полученному в примере 3.9, x(1)=[ –⅛. 0] .
Шаг 3.k = l, А(1) =A(0) + A 
,
A = 
– 
,
∆x 
= [–⅛, 0] – [0, 0] = [–⅛, 0] ,
∆g = [0, ½] – [1, 0] = [–1, ½] ,
s(1) = –А(1) f(х(1)) = [– 
, 
] .
Шаг 4.Поиск вдоль прямой:
x(2) = x(1) + α(1)s(1) → α(1) = 
,
x(2) = [– 
, 0] – [ , ] = [– 
,– ]
что совпадает с полученным ранее решением.
Интересно отметить, что в примерах 3.9 и 3.10 методы Флетчера — Ривса и Дэвидона — Флетчера — Пауэлла порождают одни и те же направления поиска, которые оказываются H-сопряженными:
Заметим также, что матрица A 
стремится к Н-1:
Таким образом, А(2) = Н-1(х*). После опубликования работы Дэвидона [43] были разработаны другие методы переменной метрики, отличающиеся выбором β, у и z в (3.83). Общая трудность реализации методов такого типа связана с тем, что матрица A 
в ряде случаев становится плохо обусловленной (определение плохо обусловленной матрицы см. в приложении А) и возникает необходимость возврата к начальной итерации с пересмотренной метрикой.
Другой метод, предложенный Бройденом [45], Флетчером [46] и Шэнно [47], получил широкую известность благодаря рекомендациям Пауэлла [48]. Метод Бройдена — Флетчера — Шэнно (БФШ) реализуется в соответствии с рекуррентной формулой
|
|
|
A = 
A + 
. (3.89)
К числу главных преимуществ этого метода следует отнести всегда обязательную необходимость возврата к начальной итерации алгоритма и относительно слабую зависимость от точности вычислений при проведении одномерного поиска.
Улучшение методов переменной метрики и методов сопряжённых градиентов в настоящее время осуществляется весьма близкими путями. Следовательно, все замечания, сделанные выше по поводу методов сопряженных градиентов, в некоторой степей справедливы для методов переменной метрики. Отметим, что Дэвидон [49] предложил ряд модифицированных процедур, в которых не требуются точные вычисления при проведении поисков вдоль прямой. Позже Пауэлл [50] установил свойство квадратичной сходимости этих методов при отсутствии одномерных поисков. По-видимому, метод переменной метрики в условиях квадратичной сходимости и отсутствия трудоемких операций одномерного поиска может отличаться как устойчивостью, так и быстродействием при решении задач с целевыми функциями общего вида. Эти вопросы были также рассмотрены Голдфарбом [51]. Вообще, возврат к начальной итерации метода Дэвидона — Флетчера — Пауэлла (при А = I) обычно осуществляется после реализации N шагов алгоритма. Как правило, такие действия носят профилактический характер, поскольку в ряде случаев можно сделать большее число шагов до возврата. Необходимость возврата к начальной итерации можно обосновать путем анализа обусловленности получаемых матриц. Однако следует иметь в виду, что наряду с повышением степени надежности (или устойчивости) алгоритмов переменной метрики возвраты чаще всего замедляют процесс приближения к точке оптимума, так как не позволяют использовать имеющиеся оценки производных второго порядка.
|
|
|
В работах [40, 52, 53] проведены обширные исследования связи между методами сопряженных градиентов и методами переменной метрики. Шэнно рассматривает методы сопряженных градиентов как методы переменной метрики с отсутствием «памяти». Большинство авторов придерживается той точки зрения, что эти два класса методов обладают гораздо более существенным сходством, чем это представлялось ранее. Кроме того, ясно, что многие варианты метода переменной метрики отличаются рядом общих особенностей при решении практических задач [54, 55], наличие которых заставляет проводить оценку трудоемкости дополнительных вычислений, связанных с реализацией более сложных методов. Шэнио и Фуа [56, 57] представили обширные числовые результаты, которые свидетельствуют в пользу относительно простой рекуррентной формулы Бройдена — Флетчера — Шэнно.
|
|
|
Описание программной реализации на Фортране некоторых наиболее полезных методов дано в работах [53, 58]. Следует отметить, что методы переменной метрики широко используются при разработке методов решения задач условной оптимизации. В работе [59] предложен алгоритм, объединяющий метод обобщенного приведенного градиента1) и метод Дэвидона — Флетчера — Пауэлла, тогда как Рут [60] применил метод Дэвидона — Флетчера Пауэлла при расчетах по методу множителей Лагранжа. В работах Хена [61] и Пауэлла [62] исследуются вопросы эффективности методов переменной метрики при решении задач с ограничениями.
Наконец, значительное количество работ посвящено вопросам применения методов переменной метрики к решению задач большой размерности. Как было отмечено выше, в настоящее время наилучшим средством решения таких задач являются методы сопряженных градиентов. Достигнуты определенные успехи при решении задач, в которых матрица Гессе разрежена [63—66]. Одна из трудностей использования методов переменной метрики связана с тем обстоятельством, что часто известна лишь степень разреженности некоторой оценки матрицы Н-1, а не матрицы Н.
|
|
|
Дата добавления: 2018-06-01; просмотров: 2126; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!