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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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