Фреймворк для тестирования однородных алгоритмов / Homogeneous algorithms testing framework

Оптимизация черных ящиков

В природе часто встречаются функции, о которых практически ничего неизвестно (ни графика, ни области значений), за исключением правила. Традиционно такие функции называются черным ящиком. Для оптимизации таких функций используются алгоритмы, которые на каждой итерации строят модель функции $m(x)$, и меру неопределенности $s(x)$. На эти функции накладываются следующие условия.

$m(x)$ представляет собой интерполянт, который совпадает с целевой функцией в точках испытаний, он Липшицев и инвариантен при вертикальных сдвигах целевой функции.

$$m(x_i) = f(x_i) \forall i \in \overline{1,k}$$ $$m(x) \in Lip(L_m)$$ $$m(x_i | x_1, f(x_1) + c, ..., x_k, f(x_k) + c) = m(x_i | x_1, f(x_1), ..., x_k, f(x_k)) + c$$

$s(x)$ есть мера неопределенности, которая равна 0 в точках в испытаний и положительна между ними.

$$s(x_i) = 0$$ $$s(x) \geq 0$$ $$s(x) \in Lip(L_s)$$ $$s(x | x_1, f(x_1) + c, ..., x_k, f(x_k) + c) = s(x | x_1, f(x_1), ..., x_k, f(x_k))$$

В фреймворке сравниваются следующие алгоритмы

Однородные алгоритмы

• NL¹
• CubicSplineGrad: критерий выбора следующей точки испытания есть разность кубического сплайна и меры неопределенности, заданной кусочно.
• GradNL: Модификация NL, использующая производные кубического сплайна для локальной оценки константы Липшица
• QradNL: Модификация NL, использует квадратичные миноранты как критерий поиска + производные как в GradNL

Для CubicSplineGrad, GradNL и QradNL используется сглаживающая функция, учитывающая значения производных интерполянта.

Footnotes

1. Сергеев, Ярослав Дмитриевич. Диагональные методы глобальной оптимизации / Я. Д. Сергеев, Д. Е. Квасов. ↩