Введение
Для математической оптимизации, многоуровневый поиск координат (MCS) является эффективным алгоритмом глобальной оптимизации с ограничениями на область определения, использующим только значения функции. Для этого n-мерное пространство поиска представляется набором непересекающихся гиперкубов (параллелепипедов). Затем эти параллелепипеды итеративно разделяются по плоскости, параллельной одной из осей, в соответствии со значением функции в представительной точке параллелепипеда (и его соседних точек) и размером параллелепипеда. Эти два критерия разделения объединяются для осуществления глобального поиска путем разделения больших параллелепипедов и локального поиска путем разделения областей с благоприятными значениями функции. Дополнительно, для повышения эффективности алгоритма (MCS с локальным поиском) может использоваться локальный поиск, сочетающий (многомерный) квадратичный интерполянт функции и поиск по прямой; в этом случае обычный MCS используется для генерации начальных точек. Информация, полученная в результате локального поиска (локальные минимумы целевой функции), затем передается обратно оптимизатору и влияет на критерии разделения, что приводит к уменьшению скопления точек выборки вблизи локальных минимумов, более быстрой сходимости и более высокой точности.
Упрощенный рабочий процесс
Рабочий процесс MCS визуализирован на рисунках 1 и 2. Каждый шаг алгоритма можно разделить на четыре этапа: выявление потенциального кандидата для разделения (пурпурный, толстый). Определение оптимального направления разделения и ожидаемого оптимального положения точки разделения (зеленый). Оценка целевой функции в точке разделения или восстановление ее из уже вычисленного набора; последнее применяется, если текущая точка разделения уже была достигнута при разделении соседнего блока. Создание новых блоков (пурпурный, тонкий) на основе значений целевой функции в точке разделения. На каждом этапе зеленая точка с временным желтым ореолом является уникальной базовой точкой блока; каждый блок имеет связанное значение целевой функции, а именно ее значение в базовой точке блока. Для определения, будет ли блок разделен, используются два отдельных критерия разделения. Первый – разделение по рангу, который гарантирует, что большие блоки, которые не были разделены слишком часто, в конечном итоге будут разделены. Если это применимо, то точка разделения легко определяется на фиксированной доле длины разделяемой стороны. Второй – разделение по ожидаемому выигрышу, который использует локальную одномерную параболическую квадратичную модель (суррогат) вдоль одной координаты. В этом случае точка разделения определяется как минимум суррогата вдоль отрезка прямой, и блок разделяется только в том случае, если значение интерполянта (служащее прокси для истинного значения целевой функции) ниже текущего наилучшего значения функции, полученного при выборке.
Identify a potential candidate for splitting (magenta, thick). Identify the optimal splitting direction and the expected optimal position of the splitting point (green). Evaluate the objective function at the splitting point or recover it from the already computed set; the latter applies if the current splitting point has already been reached when splitting a neighboring box. Generate new boxes (magenta, thin) based on the values of the objective function at the splitting point. At each step the green point with the temporary yellow halo is the unique base point of the box; each box has an associated value of the objective, namely its value at the box's base point. In order to determine if a box will be split two separate splitting criteria are used. The first one, splitting by rank, ensures that large boxes that have not been split too often will be split eventually. If it applies then the splitting point is easily determined at a fixed fraction of the length of the side being split. The second one, splitting by expected gain, employs a local one dimensional parabolic quadratic model (surrogate) along a single coordinate. In this case the splitting point is defined as the minimum of the surrogate along a line segment and the box is split only if the interpolant value (serving as a proxy for the true value of the objective) is lower than the current best sampled function value.
Сближение
Алгоритм гарантированно сходится к глобальному минимуму в конечном итоге (то есть при произвольно большом числе вычислений значений функции и глубине поиска), если целевая функция непрерывна в окрестности глобального минимизатора. Это следует из того, что любая область в конечном итоге станет произвольно малой, следовательно, расстояние между точками выборки стремится к нулю при стремлении числа вычислений значений функции к бесконечности.
Рекурсивная реализация
MCS разработан для эффективной рекурсивной реализации с использованием деревьев. Такой подход позволяет сделать объем требуемой памяти независимым от размерности задачи, поскольку точки выборки не хранятся в явном виде. Вместо этого сохраняется только одна координата каждой выборки, а остальные координаты могут быть восстановлены путем прослеживания истории ячейки обратно к корню (начальной ячейке). Этот метод был предложен авторами и использовался в их исходной реализации.