- •Кафедра Информатики и компьютерных технологий
- •Математические методы в инженерии
- •Классификация задач оптимизации.
- •Оценка параметров и структуры математической модели.
- •2. Задача Штейнера.
- •3. Задача о рационе.
- •4. Транспортная задача.
- •Условная оптимизация
- •Методы одномерной оптимизации Методы поиска экстремума функции одной переменной.
- •5. Задачи о распределении ресурсов.
- •Безусловная оптимизация
- •Метод половинного деления (дихотомии)
- •Метод Золотого сечения.
- •Метод Фибоначчи.
- •Метод Пауэлла.
- •Метод секущих.
- •Метод Ньютона (метод касательных).
- •Методы многомерной оптимизации
- •Методы нулевого порядка Метод конфигураций Хука-Дживса.
- •Методы первого порядка
- •Метод наискорейшего спуска.
- •Метод Гаусса-Зейделя (наискорейшего покоординатного спуска).
- •Метод Флетчера-Ривса (Метод сопряженных градиентов).
- •Методы второго порядка Метод Ньютона.
- •Модификации метода Ньютона. Метод Ньютона-Рафсона.
- •Метод Левенберга — Марквардта.
Модификации метода Ньютона. Метод Ньютона-Рафсона.
Стратегия
поиска.Существенным
недостатком метода
Ньютона
является зависимость сходимости для
невыпуклых функций от начального
приближения
.
Если
находится
достаточно далеко от точки минимума,
то метод может расходиться, т. е. при
проведении итерации каждая следующая
точка будет более удаленной от точки
минимума, чем предыдущая. Для ослабления
влияния начальной точки
на сходимость метода используется метод
Ньютона-Рафсона. Стратегия метода
Ньютона-Рафсона состоит в построении
последовательности точек
,
k=0, 1, ... таких, что
,
k=0, 1, ...
Точки последовательности вычисляются по правилу:
где – задается пользователем, а направление спуска вычисляется по формуле:
Величина шага
выбирается из условия
,
как в методе наискорейшего спуска.
Алгоритм метода.
Начальный этап
Задать , .
Найти градиент функции в произвольной точке
и матрицу Гессе H(x)
Положить k=0.
Основной этап
Шаг 1. Вычислить
Шаг 2. Проверить выполнение критерия останова
а) если критерий выполнен, расчет окончен,
б) если критерий не выполнен, то перейти к шагу 3.
Шаг 3. Вычислить матрицу Гессе
Шаг 4. Найти обратную матрицу
Шаг 5. Проверить положительную определенность матрицы
Шаг 6. Найти
Шаг 7. Найти
величину шага из условия
Шаг 8. Вычислить
Шаг 9. Положить k= k +1 и перейти к шагу 1
Сходимость метода.
Теорема 5. Пусть функция f(x) дважды непрерывно дифференцируемая сильно выпуклая функция на , а ее матрица Гессе H(X) удовлетворяет условию Липшица
Тогда последовательность сходится независимо от выбора начальной точки к точке минимума с квадратичной скоростью
,
где m - оценка наименьшего собственного значения матрицы Гессе.
Пример.
Решение.
Начальный этап
Положим
Градиент функции есть:
Матрица Гессе
Положим k=0
Основной этап
Анализ точки . Функция является строго выпуклой функцией, так как ее матрица вторых производных
по критерию Сильвестра является положительно определенной. Действительно . Точка есть точка глобального минимума функции f(X).
Метод Левенберга — Марквардта.
Стратегия поиска. При использовании метода Ньютона или метода Ньютона-Рафсона вследствие накопления ошибок в процессе счета матрица Гессе на некоторой итерации может оказаться отрицательно определенной или ее нельзя будет обратить.
Для обеспечения положительной определенности матрицы Гессе в точ-ках последовательности используется метод Левенберга — Маркардта (метод Ньютона с регулировкой матрицы). В методе Левенберга — Маркардта точки строятся по закону:
где
-
последовательность положительных
чисел, обеспечивающих положи-тельную
определенность матрицы
.
Обычно
в качестве берется значение на порядок
больше наибольшего элемента матрицы
.
Так в ряде стандартных программ полагается
.
Если
то
,
в противном случае
Очевидно, что если
,
то метод Левенберга — Маркардта
представляет собой метод
Ньютона, а если
велико,
то поскольку
при больших
метод
Левенберга — Маркардта близок к
градиентному методу. Поэтому, подбирая
значения параметра
,
можно добиться, чтобы метод Левенберга
— Маркардта сходился.
Алгоритм метода.
Начальный этап
Задать , .
Найти градиент функции в произвольной точке
и матрицу Гессе H(x)
Положить
.
Основной этап
Шаг 1. Вычислить
Шаг 2. Проверить выполнение критерия останова
а) если критерий выполнен, расчет окончен,
б) если критерий не выполнен, то перейти к шагу 3.
Шаг 3. Вычислить матрицу Гессе
Шаг 4. Вычислить
Шаг 5. Найти
обратную матрицу
Шаг 6. Вычислить
Шаг 7. Найти
Шаг 8. Проверить выполнение условия :
а) если неравенство выполнено, то положить , k= k +1 и перейти к шагу 1;
б) если нет, то положить и перейти к шагу 4.
Пример.
Решение.
Начальный этап
Положим
Градиент функции есть:
Матрица Гессе
Положим
Основной этап
