Документация

Контекст

patternsearch находит последовательность точек, x0x1 x2 ..., тот подход оптимальная точка. Значение целевой функции или уменьшается или остается то же самое от каждой точки в последовательности к следующему. Этот раздел объясняет, как поиск шаблона работает на функцию, описанную в, Оптимизируют Используя Алгоритм GPS.

Чтобы упростить объяснение, этот раздел описывает, как обобщенный поиск шаблона (GPS) работает с помощью максимального положительного основания по умолчанию 2 Н с ScaleMesh набор опции к false.

Этот раздел не показывает как patternsearch алгоритм работает с границами или линейными ограничениями. Для границ и линейных ограничений, patternsearch изменяет точки опроса, чтобы быть выполнимым в каждой итерации, означая удовлетворять всем границам и линейным ограничениям.

Этот раздел не охватывает нелинейные ограничения. Понять как patternsearch работает с нелинейными ограничениями, смотрите Нелинейный Ограничительный Алгоритм решателя.

Успешные опросы

Поиск шаблона начинает в начальной точке x0 то, что вы обеспечиваете. В этом примере,    x0 = [2.1 1.7].

[1 0] + x0 = [3.1 1.7]
[0 1] + x0 = [2.1 2.7]
[-1 0] + x0 = [1.1 1.7]
[0 -1] + x0 = [2.1 0.7]

x1 = [1.1 1.7]

2*[1 0] + x1 = [3.1 1.7]
2*[0 1] + x1 = [1.1 3.7]
2*[-1 0] + x1 = [-0.9 1.7]
2*[0 -1] + x1 = [1.1 -0.3]

x2 = [-0.9 1.7]

Неудачный опрос

Четвертой итерацией текущая точка

x3 = [-4.9 1.7]

и размер mesh равняется 8, таким образом, mesh состоит из точек

8*[1 0] + x3 = [3.1 1.7]
8*[0 1] + x3 = [-4.9 9.7]
8*[-1 0] + x3 = [-12.9 1.7]
8*[0 -1] + x3 = [-4.9 -1.3]

Следующий рисунок показывает точки mesh и их значения целевой функции.

В этой итерации ни одна из точек mesh не имеет меньшее значение целевой функции, чем значение в x3, таким образом, опрос неудачен. В этом случае алгоритм не изменяет текущую точку в следующей итерации. Таким образом,

x4 = x3;

В следующей итерации алгоритм умножает текущий размер mesh на 0,5, значение по умолчанию MeshContractionFactor опция, так, чтобы размер mesh в следующей итерации равнялся 4. Алгоритм затем опрашивает с меньшим размером mesh.

Успешные и неудачные опросы в MADS

Установка PollMethod опция к 'MADSPositiveBasis2N' или 'MADSPositiveBasisNp1' причины patternsearch использовать и различный тип опроса и реагировать на опрос по-другому, чем другие алгоритмы опроса.

Опрос MADS использование недавно сгенерировал псевдослучайные векторы mesh в каждой итерации. Векторы являются случайным образом переставленными компонентами из столбцов случайной нижней треугольной матрицы. Компоненты матрицы имеют целочисленные размеры до 1/$$\sqrt{\text{mesh size}}$$. В опросе векторы mesh умножаются на размер mesh, таким образом, точки опроса могут составить $$\sqrt{\text{mesh size}}$$ от текущей точки.

Неудачные опросы сокращают mesh на коэффициент 4, игнорирование MeshContractionFactor опция. Точно так же успешные опросы расширяют mesh на коэффициент 4, игнорирование MeshExpansionFactor опция. Максимальным размером mesh является 1, несмотря на любую установку MaxMeshSize опция.

Кроме того, когда существует успешный опрос, patternsearch запускается в успешной точке и опросах снова. Этот дополнительный опрос использует те же векторы mesh, расширенные на коэффициент 4 при пребывании ниже размера 1. Дополнительный опрос смотрит снова вдоль тех же направлений, которые были только успешны.

Отображение результатов в каждой итерации

Можно отобразить результаты поиска шаблона в каждой итерации путем установки Display опция к 'iter'. Это позволяет вам оценить прогресс поиска шаблона и внести изменения в options при необходимости.

С этой установкой шаблон ищет информацию об отображениях о каждой итерации в командной строке. Первые четыре итерации

Iter     f-count          f(x)      MeshSize     Method
    0        1        4.63474             1      
    1        4        4.51464             2     Successful Poll
    2        7           3.25             4     Successful Poll
    3       10      -0.264905             8     Successful Poll
    4       14      -0.264905             4     Refine Mesh

Запись Successful Poll ниже Method указывает, что текущая итерация была успешна. Например, опрос в итерации 2 успешен. В результате значение целевой функции точки, вычисленной в итерации 2, отображенный ниже f(x), меньше значения в итерации 1.

В итерации 4, запись Refine Mesh говорит вам, что опрос неудачен. В результате значение функции в итерации 4 остается неизменным от итерации 3.

По умолчанию поиск шаблона удваивает размер mesh после каждого успешного опроса и половин это после каждого неудачного опроса.

Больше итераций

Поиск шаблона выполняет 60 итераций перед остановкой. Следующий график показывает точки в последовательности, вычисленной в первых 13 итерациях поиска шаблона.

Числа ниже точек указывают на первую итерацию, в которой алгоритм находит точку. График только показывает числа итерации, соответствующие успешным опросам, потому что лучшая точка не изменяется после неудачного опроса. Например, лучшая точка в итерациях 4 и 5 эквивалентна в итерации 3.

Опросите метод

В каждой итерации поиск шаблона опрашивает точки в текущей mesh — то есть, это вычисляет целевую функцию при точках mesh, чтобы видеть, существует ли тот, значение функции которого меньше значения функции в текущей точке. Как Поиск Шаблона Опрос работ обеспечивает пример опроса. Можно задать шаблон, который задает mesh PollMethod опция. Шаблон по умолчанию, 'GPSPositiveBasis2N', состоит из следующих направлений на 2 Н, где N является количеством независимых переменных для целевой функции.

Например, если целевая функция имеет три независимых переменные, GPS Positive basis 2N, состоит из следующих шести векторов.

В качестве альтернативы можно установить PollMethod опция к 'GPSPositiveBasisNp1', шаблон, состоящий из следующего N + 1 направление.

Например, если целевая функция имеет три независимых переменные, 'GPSPositiveBasisNp1' состоит из следующих четырех векторов.

Поиск шаблона будет иногда запускать более быстрое использование 'GPSPositiveBasisNp1' вместо 'GPSPositiveBasis2N' как PollMethod, потому что алгоритм ищет меньше точек в каждой итерации. Несмотря на то, что не будучи обращенным в этом примере, то же самое верно при использовании 'MADSPositiveBasisNp1' по 'MADSPositiveBasis2N', и так же для GSS. Например, если вы запускаете поиск шаблона на линейно ограниченном примере в Ограниченной Минимизации Используя patternsearch и Оптимизируете Live Editor Тэска, алгоритм выполняет 1 588 вычислений функции с 'GPSPositiveBasis2N', PollMethod по умолчанию, но только 877 вычислений функции с помощью 'GPSPositiveBasisNp1'. Для большего количества детали смотрите, Сравнивают КПД Опций Опроса.

Однако, если целевая функция имеет много локальных минимумов, с помощью 'GPSPositiveBasis2N' как PollMethod может постараться не находить локальный минимум, который не является глобальным минимумом, потому что поиск исследует больше точек вокруг текущей точки в каждой итерации.

Полный опрос

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

Для проблем, в которых существует несколько локальных минимумов, иногда предпочтительно заставить поиск шаблона опросить все точки mesh в каждой итерации и выбрать ту с лучшим значением целевой функции. Это позволяет поиску шаблона исследовать больше точек в каждой итерации и таким образом потенциально избежать локального минимума, который не является глобальным минимумом. Имейте опрос поиска шаблона целая mesh, устанавливающая UseCompletePoll опция к true.

Остановка условий для поиска шаблона

Алгоритм останавливается, когда любое из следующих условий происходит:

ConstraintTolerance опция не используется в качестве останавливающегося критерия. Это определяет выполнимость относительно нелинейных ограничений.

Использование алгоритма MADS дополнительный параметр вызвало параметр опроса, Δ_p, в критерии остановки размера mesh:

где Δ_m является размером mesh. MADS останавливающийся критерий:

Робастность поиска шаблона

Алгоритм поиска шаблона устойчив относительно отказов целевой функции. Это означает patternsearch терпит вычисления функции, приводящие к NaNInf, или комплексные числа. Когда целевая функция при начальной точке x0 действительное, конечное значение, patternsearch обработки опрашивают отказы точки, как будто значения целевой функции являются большими, и игнорирует их.

Например, если все точки в опросе оценивают к NaN, patternsearch считает опрос неудачным, уменьшает mesh и переоценивает. Если даже одна точка в опросе оценивает к меньшему значению, чем кто-либо замеченный уже, patternsearch считает опрос успешным, и расширяет mesh.