Новая вершина - симплекс
Cтраница 1
 |
Итерация метода Диксона вблизи линейной границы. [1] |
Новая вершина симплекса ищется вдоль наилучшего направления. [2]
Новую вершину симплекса обозначают той же латинской буквой, что и прежнюю, но со знаком штрих или звездочкой; если какая-либо из вершин несколько раз подвергалась переносу то ставят, соответственно, несколько штрихов или звездочек. [3]
Операцию определения координат новой вершины симплекса называют отражением относительно центра тяжести. При минимизации целевой функции отражению подлежит вершина, в которой целевая функция имеет наибольшее значение. [4]
В остальных случаях точка хг берется в качестве новой вершины симплекса. Итак, определена итерация симплексного поиска. [5]
Эту формулу можно выразить словами: для определения i-той координаты новой вершины симплекса нужно удвоенную сумму всех L - 4HX координат остальных ( неподвижных) вершин разделить на число факторов и вычесть с-тую координату прежней вершины. [6]
Метод окончания поиска может определяться по зацикливанию, которое проявляется в том, что новая вершина симплекса опять оказывается наихудшей и подлежит исключению. [7]
 |
Итерация метода Диксона вблизи линейной границы. [8] |
Рассмотрим работу алгоритма вблизи границы. Пусть при построении точки хг или при пробном шаге ( сжатии), направленном из хг к центру тяжести остальных вершин, нарушается какое-нибудь ограничение задачи. В этом случае направление поиска новой вершины симплекса меняется. Она ищется вдоль одного из ребер, проходящих через наихудшую вершину симплекса. [9]
 |
Движение в методе Диксона вдоль нелинейной границы. [10] |
Тогда при помощи интерполяций или перемещений по направлению к наихудшей вершине симплекса отыскивается новая допустимая точка. Если эта точка не хуже всех остальных вершин симплекса, она и берется в качестве новой вершины. В противном случае вдоль исследуемого направления строится квадратичная аппроксимация целевой функции, по которой определяется минимум. Лучшая из пробных точек берется в качестве новой вершины симплекса. Предположим, что точка хс принадлежит допустимой области и есть надежда уменьшить F при дальнейшем продвижении вдоль выбранного направления. Тогда функции ограничений задачи аппроксимируются параболами, с помощью которых находится максимально возможный шаг вдоль исследуемого направления. Если при этом также получается хорошая допустимая точка, то она и точка хс выбираются в качестве новых вершин симплекса. Они заменяют две старые вершины, лежащие на рассматриваемом направлении. [11]
Среди прямых методов безусловной оптимизации один из наиболее эффективных - симплексный поиск, первоначально предложенный Спендли, Хекстом и Химсвортом. Основу метода составляет правило замены наихудшей вершины симплекса, которое заключается в следующем. В данном симплексе определяется вершина с наибольшим значением целевой функции. Она симметрично отображается относительно центра тяжести остальных п вершин. С полученным симплексом повторяется та же операция. Нелдер и Мид улучшили этот метод, дав иное правило определения новой вершины симплекса: вдоль прямой, проходящей через наихудшую вершину исходного симплекса и центр тяжести остальных вершин, кроме отражения, делаются дополнительные пробные шаги растяжения и сжатия для определения точки с меньшим значением целевой функции. [12]
Тогда при помощи интерполяций или перемещений по направлению к наихудшей вершине симплекса отыскивается новая допустимая точка. Если эта точка не хуже всех остальных вершин симплекса, она и берется в качестве новой вершины. В противном случае вдоль исследуемого направления строится квадратичная аппроксимация целевой функции, по которой определяется минимум. Лучшая из пробных точек берется в качестве новой вершины симплекса. Предположим, что точка хс принадлежит допустимой области и есть надежда уменьшить F при дальнейшем продвижении вдоль выбранного направления. Тогда функции ограничений задачи аппроксимируются параболами, с помощью которых находится максимально возможный шаг вдоль исследуемого направления. Если при этом также получается хорошая допустимая точка, то она и точка хс выбираются в качестве новых вершин симплекса. Они заменяют две старые вершины, лежащие на рассматриваемом направлении. [13]
Страницы: 1