Разработка компьютерного лабораторного практикума "Теория оптимизации и численные методы"
- шаг вычисляется из условия наибольшего убывания функции в точках последовательности:
Геометрическая интерпретация метода
Рисунок 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) повторяется до выполнения критерия окончания счета.
Основной критерий окончания метода:
Дополнительные критерии окончания метода:
при выполнении предельного числа итераций:
при однократном или двукратном одновременном выполнении двух условий:
,
где