XIV Аттетков и др. Методы оптимизации (1081420), страница 37
Текст из файла (страница 37)
МЕТОДЫ ПЕРВОГО И ВТОРОГО ПОРЯДКОВ используют соотношение Ьх~(Ьх~) й-~-1 = ь — („, ь, „)— АьЬи~ь(Ьшь) Аь Ря где г ' = —, рь = (АьЬю ., Ьи~ ), ь Аььи3И Лхй ь ь ( л~хь 5 >ь) 1 в алгоритме метода Пауэлла , -ь~„, -ь)т Аьь1=Аь — ь, 9 ей. где Ьх~ = Ьх~+ АьЬю", й Е И, а в алгоритме метода Мак-Кор- мика -"- ь)т Аь 1 — — Аь — „, )с~1:1, причем, как и в случае ДФП-метода, обычно полагают А1 = 1„. Можно показать, что любой из рассмотренных способов „обновления" матрицы Аь~1 сохраняет ее свойство положительной определенности, а последовательность ~Аь) при й -+ оо сходится к Н '(х').
Пример 5.9. Сравним различные алгоритмы на примере минимизации функции Т" (хнхз) = (х~~ — хз)з+ (х1 — 1)з, рассмотренной в ряде предыдущих примеров. Выберем начальную точку хв = ( — 1, — 2), в которой Т" 1х") = 13 и параметр точности поиска ез = 10 з. Как и в примере 5.8, в применяемых алгоритмах не будем использовать,.обновление" через фиксированное число шагов. 252 о.
МЕТОДЫ ПЕРВОГО И ВТОРОГО ПОРЯДКОВ В табл. 5.9 приведены координаты точек х", .найденных при помощи трех алгоритмов квазиньютоновских мотодов. Траектории поиска точки минимума для этих алгоритмов показаны на рис. 5.11 (а — - БФШ-метод; 6 — метод Пауэлла; в — метод Мак-Кормика). У'аблаца 5 9 7к' БФШ-метод Метод Пауэлла Метод Мак-Кормика Сравнительный анализ результатов показывает, что для рассматриваемой функции наилучший результат по количеству итераций, требуемых для достижения заданной точности, дают ДФП-метод и БФШ-метод. Метод Мак-Кормика по этому критерию эффективности им заметно уступает.
Отметим, что сравнение эффективности алгоритмов минимизации принято проводить на специально сконструированных функциях. Графики этих функций имеют четко выраженную оврилсную сгяруктпуру. На рис. 5.12 представлены линии уровня унимодальной функции Розенброка у(, мхэ) = И0(хг — х1)э+ (1 — х1)2, (5.32) а на рис. 5.13 функции Химмельблау 1(хмхэ) = (х, + хз — 11)~ + (х1+ хз~ — 7)~, (5.33) 1 (0,379, — 1,483) 2 (0,158, — 0.,103) 3 (0,859, 0,557) 4 (0,871, 0,766) 5 (0.,994, 0,971) 6 (0,998, 0,996) 7 (0,999, 0,999) 8 9 10 (0,379, — 1,483) (0,158, -0,103) (0,859,.
0,557) (0,871, 0,766) (0,934, 0,871) (0.,998, .0,989) (0,999, 0,999) (0,999., 0,999) (0,379, — 1,483) ( — 0,030, .— 0,.394) ( — 0,011, 0,043) (0,726, 0,398) (0,966, 0,801) (0,921, 0,810) (0,932, .0,883) (0,995., 1,019) (0,995, 0,990) (0,999, 0,999) 254 5. МЕТОДЫ ПЕРВОГО И ВТОРОГО ПОРЯДКОВ имеющей четыре точки минимума. Для испытания алгоритмов используют также унимодальную функцию Пауэлла 1(х) = (х1+10хт) + 5(хз — х4) + (хз — 2тз) + 10(х1 — х4), (5.34) достигающую минимума в точке х* = (О, О, О, 0). Вопросы и задачи 5.1.
Покажите, что функция Розепброка (5.32) и функция Пауэлла (5.34) являются унимодальными. 5.2. Решите задачу хй Хз + х!хз х1+ 2хз — у п11П, ,д „г выбрав начальную точку (О, 0). Используйте алгоритмы метода сопряженных направлений и метода Давидона Флетчера Пауэлла. Покажите, что реализуемые алгоритмы приводят к одной и той же траектории поиска точки минимума, если в алгоритме ДФП-метода направление спуска из начальной точки совпадает с направлением антиградиента. Графически проиллюстрируйте полученные результаты.
5.3. Решите задачу ~(хмхз) = 10х~~ — 4х1хз + 7х~~ — 4~Г5(5х1 + хв) — 16 — > п1ш., выбрав в качестве начальной точку хе = (О, — ~/5) . Найдите уравнение линии уровня целевой функции, проходящей через точку хе. Ортогональным преобразованием приведите найденное уравнение к каноническому виду и постройте линию уровня в исходной системе координат. Проведите поиск минимума целевой функции из заданной начальной точки с точностью е = 0,01, применяя алгоритмы метода градиентного спуска, метода сопряженных направлений, метода Ньютона и метода Давидона — Флетчера — — Пауэлла. 255 Вопросы и задачи Сравните полученные результаты по количеству итераций, необходимых для достижения заданной точности, дайте графическую иллюстрацию процесса поиска точки минимума. Перечислите методы, гарантированно приводящие к точке минимума целевой функции за конечное число шагов при удачно выбранной начальной точке.
11вляется ли таковой точка (О, — Л)? 5.4. Решите задачу 3 з х1 + 2х~~+ с~1+'з -~ шш выбрав в качестве начальной точку (1, О) и параметр точности поиска с = 10 з. Проведите сравнительный анализ различных методов первого и второго порядков, дайте графическую иллюстрацию полученных результатов. 5.5. Решите задачу 10(х~1 — х2) + (х1 — 1) — + шш, выбрав в качестве начальной точку ( — 1, 1) и параметр точности поиска е = 10 з. Для решения задачи используйте метод Ньютона и его модификации, метод сопряженных направлений, один из квазиныотоновских методов.
В алгоритмах, включающих одномерную минимизацию для выбора шага исчерпывающего спуска, используйте различные методы одномерной минимизации: дихотомии, золотого сечения, квадратичной и кубической интерполяции. Установите, какой иэ использованных алгоритмов самый эффективный по количеству итераций. Дайте графическую иллюстрацию полученных результатов.
6. АЛГОРИТМЫ ПРЯМОГО ПОИСКА В методах прямого поиска минимума целевой функции (или методов нулевого порядка) используют информацию только о значениях этой функции. Многие из этих методов не имеют строгого теоретического обоснования и построены на основе эвристических соображений. Поэтому вопросы сходимости методов прямого поиска еще мало изучены, а оценки скорости сходимости обычно отсутству1от. Вместе с тем эти методы идейно связаны с методами первого и второго порядков, что в ряде случаев позволяет оценивать эффективность алгоритмов прямого поиска применительно к минимизации некоторых классов функций. Распространенным способом оценки эффективности методов прямого поиска являются вычислительные эксперименты и сравнительный анализ методов по результатам таких экспериментов.
Однако следует учитывать, что этот анализ не во всех случаях может приводить к однозначным выводам о преимуществах одного метода перед другим. Во-первых, это связано с тем, что сравнению обычно подвергаются не только методы, но и программные реализации соответствующих алгоритмов. Хороший метод можно „загубить" плохим программированием, неудачным выбором параметров алгоритма.
Во-вторых, методы могут вести себя по-разному на различных этапах процесса минимизации. Удовлетворительного способа преодоления указанных трудностей не существует. Единственное,что можно сделать в подобной ситуации., привести данные о результатах вычислений в развернутой форме, позволяющей сравнивать методы по различным критериям. Кроме того, не следует забывать, что поиск решения всегда 257 6.1. Особенности прямого поиска минимума остается искусством, которому можно научиться лишь путем проб и ошибок, применяя различные методы при решении конкретных задач. 6.1.
Особенности прямого поиска минимума Для применения методов прямоео поиска минимума целевой функции достаточно располагать лишь возможностью вычисления значения функции в любой точке ее области определения. Это обстоятельство существенно расширяет сферу практического применения таких методов. Опишем один из наиболее простых алгоритмов минимизации функции 1"(ж), определенной в яси.
Выберем в Кп точку ше, называемую обычно базовой. Вычислим в ней значение у'улу~) функции 1'(:в), а затем построим и;мерный куб с центром в этой точке и с ребрами длиной 1, параллельными ортам базиса. Множество вершин этого куба вместе с точкой хл составляют так называемый шаблон (или образец).
Вычислив значения функции в вершинах куба, выберем в качестве новой базовой точки ту из вершин, в которой значение функции меньше 1(,в ), и повторим описанную процедуру построения шаблона и выбора следующей базо- х, вой точки. Если же такой вершины не оказалось, то оставим прежнюю базовую точку яул и построим о х> шаблон с уменьшенной (например, вдвое) длиной ребер куба. Процесс поиска закончим, когда длина ребра куба станет меньше заданного числа е ) О.
Геометрическая иллюстрация описанного алгоритма, называемого обычно поиском при помощи шаблона (или образца), представлена на рис. 6.1 в двумерном случае. Рис. 6.1 258 6. АЛГОРИТМЫ ПРЯЫОГО ПОИСКА Основной недостаток поиска при помощи шаблона состоит в резком росте количества вычислений значений целевой функции при увеличении размерности и (порядка 2"), а главное преимущество — в простоте алгоритма.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
