Разработка компьютерного лабораторного практикума "Теория оптимизации и численные методы" (стр. 4 из 12)
1.1.9 Метод Марквардта
Метод Марквардта (метод Ньютона с переменной матрицей), повторяет метод Ньютона. Отличие заключается в том, что точки строятся по закону:
где
- последовательность чисел (>0), обеспечивающих положительную определенность матрицы 
. Обычно назначается как минимум на порядок больше, чем самый большой элемент матрицы 
.1.1.10 Метод Нелдера-Мида (деформируемого многогранника)
Алгоритм метода:
1) Задается начальная система точек (многогранник), включающая в себя
точку: 
для функции 2-х переменных задается три начальные точки:
2) Вычисляется значение функции во всех точках многогранника и выбирается:
лучшая точка
: 
(здесь 
- номер итерации, 
- номер точки) худшая точка 
: Далее заданная система из
точки перестраивается, для этого:3) Строится центр тяжести системы заданных точек за исключением худшей:
(для функции 2-х переменных точка
- середина отрезка, соединяющего точки за исключением худшей)4) Выполняется операция отражение худшей точки через центр тяжести:
здесь
- параметр отражения (рекомендуемое значение 
). 
Рисунок 1.11. Отражение
5) Формируется новая система точек (многогранник). Для этого в точке
вычисляется значение функции, полученное значение сравнивается с 
:если
выполняется операция растяжение: 
Рисунок 1.12. Растяжение
здесь
- параметр растяжения (рекомендованное значение 
)При этом если
, то в новой системе точек точка будет заменена на 
, если же 
, то в новой системе точек точка 
будет заменена на 
- если
выполняется операция сжатие: 
Рисунок 1.13. Сжатие
здесь
- параметр сжатия (рекомендованное значение 
).При этом если
, то в новой системе точек точка 
будет заменена на 
, если же 
, то в новой системе точек точка будет заменена на .- если
выполняется операция редукции: при этом формируется новый многогранник, содержащий точку 
с уменьшенными вдвое сторонами: 
Рисунок 1.14. Редукция
Т.о. в результате выполнения этого пункта алгоритма формируется новая система точек (многогранник), причем в случае возникновения операций растяжения и сжатия перестраивается только одна точка -
, в случае возникновения операции редукции – все точки, за исключением 
.6) Процедура 2)-5) повторяется до выполнения критерия окончания счета.
Основной критерий окончания метода:
Дополнительные критерии окончания метода:
- при выполнении предельного числа итераций:
при однократном или двукратном одновременном выполнении двух условий:
,где
- малое положительное число.Алгоритм работы метода Нелдера-Мида схематически изображен на рис. 1.15
Рисунок 1.15. Диаграмма работы метода Нелдера-Мида
1.1.11 Метод случайного поиска (адаптивный метод случайного спуска)
Алгоритм метода:
1) Задается начальная точка
и начальное значение параметра 
2) Строится система пробных точек (обычно 5-10 точек):
здесь
- номер итерации, 
- случайный вектор единичной длины, - номер пробной точки.Построенные пробные точки оказываются лежащими на гиперсфере радиуса
(в случае двух переменных – на окружности радиуса 
).3) Для каждой пробной точки вычисляется значение функции
и выбирается наилучшая , для которой 
. Выбор может осуществляться как автоматически, так и при участии пользователя.4) Проверяется условие:
· если условие выполнено, то система пробных точек считается удачной, далее возможно два продолжения алгоритма:
4.1)
4.2) в направлении, соединяющем точки
и 
делается ускоряющий шаг: 
в этом случае, если оказывается, что
, принимается 
Рисунок 1.16. Удачная система пробных точек
- если условие не выполняется, делается попытка построить новую удачную систему пробных точек. если при этом число неудачных попыток достигает некоторого заданного числа
, текущий радиус 
уменьшается (автоматически или пользователем).