Алгоритм. Пусть требуется найти безусловный минимум функции n переменных

Пусть требуется найти безусловный минимум функции n переменных . Предполагается, что серьёзных ограничений на область определения функции нет, то есть функция определена во всех встречающихся точках.

Параметрами метода являются:

· коэффициент отражения , обычно выбирается равным .

· коэффициент сжатия , обычно выбирается равным .

· коэффициент растяжения , обычно выбирается равным .

1) «Подготовка». Вначале выбирается точка , образующие симплекс n-мерного пространства. В этих точках вычисляются значения функции: .

2) «Сортировка». Из вершин симплекса выбираем три точки: с наибольшим (из выбранных) значением функции , со следующим по величине значением и с наименьшим значением функции . Целью дальнейших манипуляций будет уменьшение по крайней мере .

3) Найдём центр тяжести всех точек, за исключением

Вычислять не обязательно.

4) «Отражение». Отразим точку относительно с коэффициентом (при это будет центральная симметрия, в общем случае — гомотетия), получим точку и вычислим в ней функцию: . Координаты новой точки вычисляются по формуле:

.

5) Далее смотрим, насколько нам удалось уменьшить функцию, ищем место в ряду .

· Если , то направление выбрано удачное и можно попробовать увеличить шаг. Производим «растяжение». Новая точка и значение функции .

· Если , то можно расширить симплекс до этой точки: присваиваем точке значение и заканчиваем итерацию (на шаг 9).

· Если , то переместились слишком далеко: присваиваем точке значение и заканчиваем итерацию (на шаг 9).

· Если , то выбор точки неплохой (новая лучше двух прежних). Присваиваем точке значение и переходим на шаг 9.

· Если , то меняем местами значения и . Также нужно поменять местами значения и . После этого идём на шаг 6.

· Если , то просто идём на следующий шаг 6.

В результате (возможно, после переобозначения) .

6) «Сжатие». Строим точку и вычисляем в ней значение .

7) Если , то присваиваем точке значение и идём на шаг 9.

8) Если , то первоначальные точки оказались самыми удачными. Делаем «глобальное сжатие» симплекса — гомотетию к точке с наименьшим значением

: , .

9) Последний шаг — проверка сходимости. Может выполняться по-разному, например, оценкой дисперсии набора точек. Суть проверки заключается в том, чтобы проверить взаимную близость полученных вершин симплекса, что предполагает и близость их к искомому минимуму. Если требуемая точность ещё не достигнута, можно продолжить итерации с шага 2.

Дата добавления: 2015-04-24