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

Контекст

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

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

Этот раздел не показывает как 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, значение по умолчанию Contraction factor в панели опций Mesh, так, чтобы размер 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. Дополнительный опрос смотрит снова вдоль тех же направлений, которые были только успешны.

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

Можно отобразить результаты поиска шаблона в каждой итерации установкой Level of display к Iterative в опциях Display to command window. Это позволяет вам оценить прогресс поиска шаблона и внести изменения в 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 опцией Poll method. Шаблон по умолчанию, GPS Positive basis 2N, состоит из следующих направлений на 2 Н, где N является количеством независимых переменных для целевой функции.

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

В качестве альтернативы можно установить Poll method на GPS Positive basis NP1, шаблон, состоящий из следующего N + 1 направление.

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

Поиск шаблона будет иногда запускать более быстрое использование GPS Positive basis Np1 вместо GPS Positive basis 2N как Poll method, потому что алгоритм ищет меньше точек в каждой итерации. Несмотря на то, что не будучи обращенным в этом примере, то же самое верно при использовании MADS Positive basis Np1 по MADS Positive basis 2N, и так же для GSS. Например, если вы запускаете поиск шаблона на примере, описанном в Линейно Ограниченной проблеме, алгоритм выполняет 1 588 вычислений функции с GPS Positive basis 2N, Poll method по умолчанию, но только 877 вычислений функции с помощью GPS Positive basis Np1. Для большего количества детали смотрите, Сравнивают КПД Опций Опроса.

Однако, если целевая функция имеет много локальных минимумов, с помощью GPS Positive basis 2N когда Poll method может постараться не находить локальный минимум, который не является глобальным минимумом, потому что поиск исследует больше точек вокруг текущей точки в каждой итерации.

Полный опрос

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

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

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

Критерии остановки алгоритма поиска шаблона перечислены в разделе Stopping criteria приложения Оптимизации:

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

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

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

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

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

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

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