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

Контекст

patternsearch находит последовательность точек, x0, x1, 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 умножаются на размер mesh, таким образом, точки опроса могут составить $$\sqrt{\text{поймайте в сети размер}}$$ от текущей точки.

Неудачные опросы сокращают 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 терпит функциональные оценки, приводящие к NaN, Inf или комплексным числам. Когда целевая функция при начальной точке, x0 является действительным, конечным значением, отказы точки опроса обработок patternsearch, как будто значения целевой функции являются большими, и игнорируют их.

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