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

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

(3.39)

Геометрическая иллюстрация этих процедур для пространства E ₂ приведена на рис. 3.5 и 3.6. Так как величина a Î (0; 1), то выбор точек z¹ и z² соответствует сжатию симплекса; b» 1, поэтому выбор точки z³ соответствует отражению, а g > 1 и выбор точки z⁴ приводит к рас­тяжению симплекса. Численные эксперименты показывают, что этот

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

, (3.40)

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

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

Рис. 3.5. Пробные точки z¹,z²,z³,z⁴ для перехода к новому симплексу

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

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

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

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

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

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

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

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

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

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

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

(3.31): x ^k+\ = x ^k +a _kp^k. В зависимости от способа выбора направления p^k и шага a _k получаются различные алгоритмы минимизации.