Разработка компьютерного лабораторного практикума "Теория оптимизации и численные методы"
-
шаг вычисляется
из условия
наибольшего
убывания функции
в точках
последовательности:
![]()
Геометрическая интерпретация метода

Рисунок 3.1. Геометрическая интерпретация метода
Основной
критерий окончания
метода:
![]()
Начальные
параметры
метода:
.
Изменяемые
параметры
метода: отрезок
для уточнения
шага
.
Особенности
реализации
алгоритма. Задача
о поиске оптимального
шага
(задача
)
решается численно
методом дихотомии
на отрезке
с заданной
точностью
.
Вопрос о границах
отрезка
на каждой итерации
решается
пользователем.
Направление
проекции градиента
меняется циклически:
сначала спуск
в направлении
оси абсцисс,
затем – ординат
и т.д.
Рекомендации
по выбору параметров
метода. Отрезок
задается из
тех же соображений,
что и в методе
наискорейшего
спуска.
Метод сопряженных градиентов
Алгоритм метода:
![]()
здесь:
![]()
![]()
![]()
-
шаг вычисляется
из условия
наибольшего
убывания функции
в точках
последовательности:
![]()
Геометрическая интерпретация метода

Рисунок 3.1. Геометрическая интерпретация метода
Согласно алгоритму, первая итерация метода сопряженных градиентов совпадает с первой итерацией метода наискорейшего спуска.
Вычисление
величины
по
формуле (5.4) обеспечивает
для квадратичных
функций построение
последовательности
H-сопряженных
направлений
,
для которых
.
При этом в точках
последовательности
градиенты
функции
взаимно
перпендикулярны,
т.е.
![]()
Основной критерий окончания метода:
![]()
Начальные параметры метода:
![]()
Изменяемые
параметры
метода: отрезок
для уточнения
шага
.
Особенности
реализации
алгоритма. Задача
о поиске оптимального
шага
(задача
)
решается численно
методом дихотомии
на отрезке
с заданной
точностью
.
Вопрос о границах
отрезка
на каждой итерации
решается
пользователем.
Замечание. Т.к.
шаг
на каждой итерации
вычисляется
численно с
точностью
,
за счет накопления
ошибки, метод
сопряженных
градиентов
в отдельных
случаях может
сходиться для
квадратичной
функции за
число итераций,
превышающее
число переменных.
Рекомендации по выбору параметров метода.
Отрезок
задается из
тех же соображений,
что и в методе
наискорейшего
спуска.
Метод Ньютона
Алгоритм метода:
![]()
здесь:
- направление
спуска
![]()
Особенностью
метода Ньютона
является то,
что при
метод позволяет
отыскать минимум
квадратичной
функции за одну
итерацию.
Геометрическая интерпретация метода для квадратичной функции:

Рисунок 3.1. Геометрическая интерпретация метода
Для
неквадратичной
функции метод
Ньютона предполагает
построение
последовательности
минимумов
аппроксимирующих
квадратичных
функций
.

Рисунок 3.1. Последовательность минимумов
Основной
критерий окончания
метода:
![]()
Начальные
параметры
метода:
![]()
Метод Ньютона-Рафсона
Алгоритм метода:
![]()
здесь:
- направление
спуска
-
шаг выбирается
из условия
убывания функции
в точках
последовательности:
.
Геометрическая интерпретация метода для квадратичной функции:

Рисунок 3.1. Геометрическая интерпретация метода
Основной
критерий окончания
метода:
![]()
Начальные
параметры
метода:
.
Изменяемый
параметр метода:
величина шага
![]()
Метод Марквардта
Метод Марквардта (метод Ньютона с переменной матрицей), повторяет метод Ньютона. Отличие заключается в том, что точки строятся по закону:
![]()
где
-
последовательность
чисел (>0), обеспечивающих
положительную
определенность
матрицы
.
Обычно
назначается
как минимум
на порядок
больше, чем
самый большой
элемент матрицы
.
Метод Нелдера-Мида (деформируемого многогранника)
Алгоритм метода:
1) Задается
начальная
система точек
(многогранник),
включающая
в себя
точку:
![]()
для функции 2-х переменных задается три начальные точки:
![]()
2) Вычисляется значение функции во всех точках многогранника и выбирается:
лучшая точка
:
(здесь
- номер итерации,
-
номер точки)
худшая точка
:
![]()
Далее
заданная система
из
точки перестраивается,
для этого:
3) Строится центр тяжести системы заданных точек за исключением худшей:
![]()
(для функции
2-х переменных
точка
- середина отрезка,
соединяющего
точки за исключением
худшей)
4) Выполняется операция отражение худшей точки через центр тяжести:
![]()
здесь
-
параметр отражения
(рекомендуемое
значение
).

Рисунок 3.1. Отражение
5)
Формируется
новая система
точек (многогранник).
Для этого в
точке
вычисляется
значение функции,
полученное
значение сравнивается
с
:
если
выполняется
операция растяжение:
![]()

Рисунок 3.1. Растяжение
здесь
-
параметр растяжения
(рекомендованное
значение
)
При этом если
,
то в новой системе
точек точка
будет
заменена на
,
если же
,
то в новой системе
точек точка
будет
заменена на
![]()
если
выполняется
операция сжатие:
![]()

Рисунок 3.1. Сжатие
здесь
-
параметр сжатия
(рекомендованное
значение
).
При этом если
,
то в новой системе
точек точка
будет
заменена на
,
если же
,
то в новой системе
точек точка
будет
заменена на
.
если
выполняется
операция редукции:
при этом формируется
новый многогранник,
содержащий
точку
с
уменьшенными
вдвое сторонами:
![]()

Рисунок 3.1. Редукция
Т.о.
в результате
выполнения
этого пункта
алгоритма
формируется
новая система
точек (многогранник),
причем в случае
возникновения
операций растяжения
и сжатия перестраивается
только одна
точка -
,
в случае возникновения
операции редукции
– все точки, за
исключением
.
6) Процедура 2)-5) повторяется до выполнения критерия окончания счета.
Основной критерий окончания метода:

Дополнительные критерии окончания метода:
при выполнении предельного числа итераций:
![]()
при однократном или двукратном одновременном выполнении двух условий:
,
где