Поиск точки min-ма по деформируемому симплексу

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

А именно, положение новой вершины х^ вместо вершины х, соответствующей наибольшему значению функции, находится сравнением и выбором наименьшего среди значений целевой функции в точках:

z= x-(x-x), 0<<1;

z= x+(x-x), 0<<1; (1)

z= x+(x-x), ≈1;

z= x+(x-x), >1.

Геометрическая иллюстрация этих процедур для пространства Е;

z, z, z, z- пробные точки, для перехода к новому симплексу.

Так как величина Є(0;1), то выбор точек zи zсоответствует сжатию симплекса; ≈1, поэтому выбор точки zсоответствует отражению, а >1 и выбор точки zприводит к растяжению симплекса.

Например:

Численные эксперименты показывают, что этот алгоритм хорошо работает в пространстве Еn для n6.

Отметим, что при деформациях утрачивается свойство правильного исходного симплекса. Поэтому не стремясь к правильности начального симплекса, его строят из произвольной базовой точки хЄЕn по формулам:

х=х+е (2)

где е-iй базисный вектор; -параметр симплекса.

На практике часто применяется следующий набор параметров ,и для выбора пробных точек zв формулах (1):

=1/2; =1 и =2

Опишем алгоритм поиска точки min-ма функции по деформирующему симплексу:

ШАГ 0:

Выбрать параметр точности , параметры ,и , базовую точку х, параметр а и построить симплекс по формулам (1) или (2). Вычислить f(х).

ШАГ1:

Вычислить значение функции в вершинах симплекса х,…,х.

ШАГ2:

Упорядочить вершины х,…,хтак, чтобы f(х)…f(х)/

ШАГ3:

Проверить достижение заданной точности (условие: ). Если оно выполняется, то вычисления завершить, полагая х*≈х, f*≈f(Х). Иначе перейти к шагу4.

ШАГ4:

Найти x=и пробные точки z, k=1,…,4 по формулам (1).

Найти f(z)=min f(z). Если f(z)<f(х), то положить х=zи перейти к шагу2. Иначе перейти к шагу5.

ШАГ5:

Уменьшить симплекс, полагая х=(х+х)/2, i=1,…,n и перейти к шагу 1.

Замечание:

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

Дата добавления: 2014-01-07