Cтраница 1
Симплексный поиск обладает тем свойством, что изменение длины шага в направлении псевдоградиента - у однозначно связано с изменением интервала варьирования, или длины пробного шага aft. Отсюда следует, что условие (3.2) не выполняется, и поэтому теорема 3.1 неприменима. По-видимому, при наличии случайных ошибок измерений и при достаточно общих предположениях о функции регрессии симплексный метод не обладает гарантированным свойством сходимости. [1]
Алгоритм последовательного симплексного поиска состоит в следующем. [2]
При симплексном поиске не всегда удается определить положение истинного экстремума, а лишь попасть в околоэкстремальную область или на гребень функции. [3]
Основу метода Диксона составляет симплексный поиск. Далее оценивается дальнейшее продвижение вдоль исследуемого направления: если F ( х ( г) F ( х ( п), то в точке 2xW - х действительно вычисляется значение F. Тогда по трем точкам 2хМ - х, хг, хп строится одномерная квадратичная аппроксимация функции F и по ней отыскивается точка минимума хт. [4]
Как и в процедуре безусловного симплексного поиска, на каждой итерации заменяется самая плохая вершина комплекса. При этом она отражается относительно центра тяжести его остальных вершин. [5]
Отметим, что ограничения типа неравенств при проведении симплексного поиска учитываются очень просто: вершины, не удовлетворяющие ограничениям, отбрасываются. [6]
Среди прямых методов безусловной оптимизации один из наиболее эффективных - симплексный поиск, первоначально предложенный Спендли, Хекстом и Химсвортом. Основу метода составляет правило замены наихудшей вершины симплекса, которое заключается в следующем. В данном симплексе определяется вершина с наибольшим значением целевой функции. Она симметрично отображается относительно центра тяжести остальных п вершин. С полученным симплексом повторяется та же операция. Нелдер и Мид улучшили этот метод, дав иное правило определения новой вершины симплекса: вдоль прямой, проходящей через наихудшую вершину исходного симплекса и центр тяжести остальных вершин, кроме отражения, делаются дополнительные пробные шаги растяжения и сжатия для определения точки с меньшим значением целевой функции. [7]
Рассмотрим одну из возможных реализаций на ЭВМ СПМ - алгоритм адаптивного симплексного поиска. [8]
Рассматриваемый в этом разделе метод принадлежит Диксону ( 1973) и основан на комбинации техники симплексного поиска со специальными приемами для ускорения счета. [9]
При решении задач с ограничениями Спендли, Хекст и Хим-сворт, а также Нелдер и Мид предлагали добавлять к значению целевой функции в недопустимых точках большое положительное число - тогда симплексный поиск не будет нарушать границы допустимой области. Однако, как установил Бокс ( 1965), этот метод приводит к тому, что симплекс сплющивается и поиск минимума продолжается в некотором подпространстве переменных. [10]
Метод деформируемого многогранника, также относящейся к прямым методам оптимизации, является несколько более сложным по сравнению с рассмотренным методом покоординатного спуска, но весьма эффективным и легко осуществляемым на ЭВМ. Он основан на симплексном поиске. [11]
В остальных случаях точка хг берется в качестве новой вершины симплекса. Итак, определена итерация симплексного поиска. [12]
В этом методе ограничения общего вида заменяются соответствующими штрафами, в результате чего исходная задача преобразуется в задачу с простыми ограничениями. При решении видоизмененной задачи, кроме симплексного поиска, применяется модификация сеточного поиска, рассмотренная в разд. [13]
Для минимизации негладких функций применяют так называемые методы прямого поиска. К сожалению, лучшие из них, такие, как, например, симплексный поиск ( Спендли, Хекст и Химсворт ( 1962)), нереализуемы в многомерных случаях, поскольку требуют слишком много памяти, причем независимо от структуры задачи. Однако среди них есть и экономные в этом смысле методы. И те и другие читатель найдет в гл. [14]
Сеточный поиск может окончиться и раньше, если величина пробных шагов станет слишком малой. Если сеточный поиск закончился, а в симплексном множестве не появились новые переменные, то задача считается решенной. В противном случае те переменные, которые при сеточном поиске покинули е-окрестности своих границ, переводятся из сеточного в симплексное множество. Затем выполняется следующий симплексный поиск. Напомним, что ограничения общего вида учитываются штрафами. Поэтому как в сеточной, так и в симплексной фазе алгоритм минимизирует функцию вида (7.8.1) при оставшихся простых ограничениях. [15]