Лекция: ПОИСК ТОЧКИ МИНИМУМА ПО ДЕФОРМИРУЕМОМУ СИМПЛЕКСУ

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

(3.39)

Геометрическая иллюстрация этих процедур для пространства E2 приведена на рис. 3.5 и 3.6. Так как величина a Î (0; 1), то выбор точек z1 и z2 соответствует сжатию симплекса; b » 1, поэтому выбор точки z3 соответствует отражению, а g > 1 и выбор точки z4 приводит к рас­тяжению симплекса. Численные эксперименты показывают, что этот

алгоритм хорошо работает в пространстве En для п £ 6. Отметим, что при деформациях утрачивается свойство правильности исходного симплекса. Поэтому, не стремясь к правильности начального симплекса, его строят из произвольной базовой точки х0Î En, по формулам

, (3.40)

где e i — i-й базисный вектор; a— параметр симплекса. На практике хорошо зарекомендовал себя следующий набор параметров a, b и g для выбора пробных точек zi в формулах (3.39):

a = 1/2, b = 1 и g =2.

Рис. 3.5. Пробные точки z1,z2,z3,z4 для перехода к новому симплексу

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

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

Шаг 0. Выбрать параметр точности e, параметры a, b и g, базовую точку х0, параметр a и построить начальный симплекс по формулам (3.37) или (3.40). Вычислить f(х0).

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

Шаг 2. Упорядочить вершины х0,..., xn так, чтобы f(х0) £ … £ f(хn).

Шаг 3. Проверить достижение заданной точности (условие (3.38)). Если оно выполняется, то вычисления завершить, полагая х * » х0, f * » f(х0). Иначе — перейти к шагу 4.

Шаг 4. Найти и пробные точки zk, k=1, …, 4 пo формулам (3.39). Найти f(z*)= min f(zk). Если f(z*) < f(zn). то положить xn=z* и перейти к шагу 2. Иначе — перейти к шагу 5.

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

Замечание. Для того чтобы избежать сильной деформации симплекса, алгоритм иногда дополняют процедурой обновления. На­пример, после N шагов алгоритма из точки х0снова строят симплекс по формулам (3.37) или (3.40), полагая а = ||x0-xn||.

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

Перейдем теперь к описанию вычислительных процедур вида

(3.31): xk+\ = xk+akpk . В зависимости от способа выбора направления pk и шага ak получаются различные алгоритмы минимизации.