Наихудшая вершина

Cтраница 1

Движение в методе Диксона вдоль нелинейной границы. [1]

Наихудшая вершина исключается из симплекса, что уменьшает его размерность, и поиск в общем случае ведется вдоль пересечения активных ограничений. Тогда после q итераций алгоритм автоматически увеличивает размерность симплекса снова до п, что препятствует локализации поиска на каком-либо многообразии. [2]

Движение в методе Диксона вдоль нелинейной границы. [3]

Тогда при помощи интерполяций или перемещений по направлению к наихудшей вершине симплекса отыскивается новая допустимая точка. Если эта точка не хуже всех остальных вершин симплекса, она и берется в качестве новой вершины. В противном случае вдоль исследуемого направления строится квадратичная аппроксимация целевой функции, по которой определяется минимум. Лучшая из пробных точек берется в качестве новой вершины симплекса. Предположим, что точка хс принадлежит допустимой области и есть надежда уменьшить F при дальнейшем продвижении вдоль выбранного направления. Тогда функции ограничений задачи аппроксимируются параболами, с помощью которых находится максимально возможный шаг вдоль исследуемого направления. Если при этом также получается хорошая допустимая точка, то она и точка хс выбираются в качестве новых вершин симплекса. Они заменяют две старые вершины, лежащие на рассматриваемом направлении. [4]

Построение новой ( правило отражения. [5]

Правило отражения, как уже указывалось, состоит в том, что наихудшая вершина симплекса отражается относительно противоположной грани симплекса. [6]

В случае (4.3) результатом отражения является новая точка, которая, если ею заменить наихудшую вершину xn ( k), сама станет наихудшей вершиной. В этом случае производится сжатие симплекса. [7]

Среди прямых методов безусловной оптимизации один из наиболее эффективных - симплексный поиск, первоначально предложенный Спендли, Хекстом и Химсвортом. Основу метода составляет правило замены наихудшей вершины симплекса, которое заключается в следующем. В данном симплексе определяется вершина с наибольшим значением целевой функции. Она симметрично отображается относительно центра тяжести остальных п вершин. С полученным симплексом повторяется та же операция. Нелдер и Мид улучшили этот метод, дав иное правило определения новой вершины симплекса: вдоль прямой, проходящей через наихудшую вершину исходного симплекса и центр тяжести остальных вершин, кроме отражения, делаются дополнительные пробные шаги растяжения и сжатия для определения точки с меньшим значением целевой функции. [9]

После проведения первой серии опытов результаты их сравнивают между собой и выбирается опыт ( вершина симплекса), где результат наихудший. Затем вычисляются координаты точки, симметричной наихудшей вершине симплекса по отношению к оставшейся после ее отбрасывания грани. Эта новая точка совместно с оставшимися образует новый симплекс. [10]

Гани в своем варианте комплексного поиска применил технику Нелдера и Мида с дополнительными пробными шагами ( растяжение и сжатие) для определения новых вершин. Основу его процедуры составляет, как и у Бокса, отражение наихудшей вершины комплекса относительно центра тяжести остальных вершин. Если при этом нарушаются ограничения задачи, то известным образом проводится поиск допустимой точки. Тогда вдоль направления отражения пытаются устроить растяжение. [11]

Итерация метода Диксона вблизи линейной границы. [12]

Прежде всего вдоль этого направления делается пробный шаг, выбранный на основе линейных аппроксимаций функций ограничений задачи. Если эти функции сами линейные, то полученная пробная точка хс принадлежит границе. Если хс по-прежнему является наихудшей вершиной симплекса, то вдоль исследуемого направления строится квадратичная аппроксимация целевой функции, и точка минимума соответствующей параболы принимается за новую вершину. Если же точка хс выбирается в качестве новой вершины, то поиск в общем случае будет продолжаться вдоль границы. Причем далее в процессе счета любое активное ограничение может стать неактивным. [13]

Итерация метода Диксона вблизи линейной границы. [14]

Рассмотрим работу алгоритма вблизи границы. Пусть при построении точки хг или при пробном шаге ( сжатии), направленном из хг к центру тяжести остальных вершин, нарушается какое-нибудь ограничение задачи. В этом случае направление поиска новой вершины симплекса меняется. Она ищется вдоль одного из ребер, проходящих через наихудшую вершину симплекса. [15]

Страницы: 1 2