Смекни!
smekni.com

Разработка компьютерного лабораторного практикума "Теория оптимизации и численные методы" (стр. 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. Удачная система пробных точек

- если условие не выполняется, делается попытка построить новую удачную систему пробных точек. если при этом число неудачных попыток достигает некоторого заданного числа

, текущий радиус
уменьшается (автоматически или пользователем).