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

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

Геометрическая иллюстрация этих процедур для пространства E2 приведена на рис.4.3 и 4.4. Так как величина то выбор точек z¹ и z² соответствует сжатию симплекса; =1, поэтому выбор точки z³ соответствует отражению, а >1 и выбор точки z⁴ приводит к растяжению симплекса. Численные эксперименты показывают, что этот алгоритм хорошо работает в пространстве En для n 6. Отметим, что при деформациях утрачивается свойство параллельности исходного симплекса. Поэтому, не стремясь к правильности начального симплекса, его строят из произвольной базовой точки En по формулам

(4.3)

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

На практике хорошо зарекомендовал себя следующий набор параметров и для выбора пробных точек: = 0,5, = 1, = 2.

Рисунок 4.4 - Новые симплексы, полученные в результате процедур сжатия (а, б);

отражения (в); растяжения (г)

Опишем алгоритм метода поиска точки минимума функции по деформируемому симплексу.

Шаг 0. Выбрать параметр точности , параметры и , базовую точку x0, параметр а и построить начальный симплекс по формулам (4.1) или (4.3), вычислить значение f(x⁰).

Шаг 1. Вычислить значение функции в вершинах функции x¹,..., xⁿ.

Шаг 2. Упорядочить вершины x°,..., xⁿ так, чтобы

Шаг 3. Проверить достижение заданной точности (условие (4.2)). Если оно

выполняется, то вычисление завершить, полагая . Иначе -

перейти к шагу 4.

Шаг 4. Найти и пробные точки z^k, k = 1,...,4. Найти .

Если то положить xⁿ = x^* и перейти к шагу 2. Иначе - перейти к шагу 5.

Шаг 5. Уменьшить симплекс полагая и перейти к шагу 1. Замечание:

Для того чтобы избежать сильной деформации симплекса, алгоритм иногда дополняют процедурой обновления. Например, после N шагов алгоритма из точки снова строят симплекс по формулам (4.1) или (4.3), полагая a = || x° — x ⁿ ||.

С теоретической точки зрения, описанные методы минимизации слабо исследованы, однако практика показывает их работоспособность.

Перейдем теперь к описанию вычислительных процедур вида . В зависимости от способа выбора направления p^k и шага a_k получается различные алгоритмы минимизации.