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

Контекст

patternsearch находит последовательность точек, x0, x1, x2,..., что приближается к оптимальной точке. Значение целевой функции либо уменьшается, либо остается неизменным от каждой точки в последовательности до следующей. В этом разделе объясняется, как работает поиск шаблона для функции, описанной в Optimize Using the GPS Algorithm.

Чтобы упростить объяснение, в этом разделе описывается, как работает обобщенный поиск шаблона (GPS), используя максимальный положительный базис 2N по умолчанию, с 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]

и размер сетки 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;

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

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

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

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

Неудачные опросы сокращают mesh в множитель 4, игнорируя MeshContractionFactor опция. Точно так же успешные опросы расширяют mesh в множитель 4, игнорируя MeshExpansionFactor опция. Максимальный размер сетки 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, чтобы увидеть, есть ли та, чье значение функции меньше, чем значение функции в текущей точке. Как работает Pattern Search Polling предоставляет пример опроса. Можно задать шаблон, который задает mesh PollMethod опция. Шаблон по умолчанию, 'GPSPositiveBasis2N', состоит из следующих 2N направлений, где N - количество независимых переменных для целевой функции.

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

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

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

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

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

Полный опрос

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

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

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

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

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

Алгоритм MADS использует дополнительный параметр, называемый параметром poll, и p в критерии остановки размера сетки:

где И m - размер сетки. Критерий остановки MADS:

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

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

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