2018-02-14
544Лабораторная работа №2. Методы многомерной безусловной минимизации. Градиентные методы
Градиентные методы (методы первого порядка) используют точные или приближенные значения первых частных производных целевой функции.
Оптимальный градиентный метод (метод наискорейшего спуска)
Метод строит последовательность приближений 
к точке минимума 
по правилу:
Называемое длиной шага (шагом) число 
определяется из условия
,
что гарантирует сильную и монотонную сходимость последовательности приближений к точке минимума .
Рис. 5
Рассмотрим алгоритм обобщенного градиентного метода.
Наряду с начальной точкой 
, алгоритм метода требует априорного задания параметра точности поиска 
.
Алгоритм 2.2.1
Шаг 1. Положить 
.
Шаг 2. Вычислить градиент 
.
Шаг 3. Проверить выполнение критерия останова:
если 
, то перейти на шаг 7.
Шаг 4. Методом одномерной минимизации оценить шаг поиска
Шаг 5. Вычислить 
.
Шаг 6. Положить 
и перейти на шаг 2.
Шаг 7. Положить 
и закончить поиск.
|
|
|
Метод сопряженных градиентов (метод Флетчера-Ривса)
В основе метода лежит построение направлений поиска минимума 
, являющихся линейными комбинациями градиента 
и предыдущих направлений поиска 
. При этом весовые коэффициенты 
выбираются так, чтобы сделать направления сопряженными относительно матрицы Гессе 
. Для повышения скорости сходимости метода, в случае неквадратичной 
используется рестарт: через каждые 
циклов направление поиска 
заменяется на 
).
Наряду с начальной точкой 
и вектором положительных приращений координат 
, алгоритм метода требует априорного задания параметра точности поиска .
Алгоритм 2.2.2
Шаг 1. Положить .
Шаг 2. Вычислить градиент .
Шаг 3. Проверить выполнение критерия останова:
если 
, то перейти на шаг 10.
Шаг 4. Если или 
кратно , то положить 
и
перейти на шаг 6.
Шаг 5. Вычислить весовой коэффициент
.
Шаг 6. Вычислить сопряжённое направлению 
направление поиска
.
Шаг 7. Методом одномерной минимизации оценить шаг поиска
.
Шаг 8. Вычислить 
.
Шаг 9. Положить и перейти на шаг 2.
Шаг 10. Положить и закончить поиск.
Задачи численной многомерной безусловной минимизации
Тестовая задача
Минимизировать функцию Химмельблау №1 
. (3D графики функции с различными углами вращения и наклона осей переменных приведены на рис. 6).
Начальные данные: 
и 
, шаги (для методов прямого поиска) 
.
Ожидаемый результат: 
(приближенное решение).
Рис. 6
Учебные задачи
2.1.1. Минимизировать функцию Химмельблау №2 (рис. 7)
.
– одна из точек локального минимума.
Рис. 7
2.1.2. Минимизировать функцию Вуда
|
|
|
.
Имеет квазистационарную точку 
, 
.
Начальные точки: 
, 
Точное решение: 
, 
.
3D графики функции для фиксированных значений 
и 
приведены на рис. 8 – случаи а) и б) соответственно.
а) 
б)
Рис. 8
2.1.3. Минимизировать функцию Пауэлла
.
Особенность – вырожденность матрицы Гессе в точке минимума.
Начальные точки: 
, 
Точное решение: 
, .
3D графики функции для фиксированных значений 
и 
приведены на рис. 9 – случаи а) и б) соответственно.
а) 
б)
Рис. 9
Список использованной литературы
1. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация – М.: Мир, 1985. – 509с., ил.
2. Дэннис Дж., Шнабель Р. Численные методы безусловной оптимизации и решения нелинейных уравнений. – М.: Мир, 1988. – 440с., ил.
3. Камаев В.А. Методы нелинейного программирования в транспортном машиностроении. Учебное пособие. – Волгоград: Изд-во Волгоградского политехнического института, 1984. – 102 с., ил.
4. Камаев В.А. Введение в экстремальные задачи транспортного машиностроения. Учебное пособие. – Волгоград: Изд-во Волгоградского политехнического института, 1984. –102с., ил.
5. Пантелеев А.В., Летова Т.А. Методы оптимизации в примерах и задачах. – М.: Высш. шк., 2002. – 544с.: ил.
6. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. - М.: ФИЗМАТЛИТ, 2005. – 368с.
7. Яновский Т., Яновский А. Прикладная квазиньютоновская оптимизация высокой точности, LAP LAMBERT Academic Publishing, Саарбрюккен, 2011. – 292с.: ил.
