Оптимизация методом ожидаемого улучшения и экспоненциальная интерполяция: строгие результаты для аналитических функций

Алгоритмы, основанные на максимизации «ожидаемого улучшения» — популярный в инженерных приложениях способ оптимизации «черных ящиков». Я расскажу о некоторых строгих результатах по этой теме. Основной акцент будет сделан на случае аналитических ядер и функций одной переменной, в котором удается установить достаточно полную картину поведения алгоритма. В частности, оказывается, что при оптимизации с гауссовским ядром алгоритм сходится экспоненциально быстро к глобальному оптимуму, если целевая функция аналитична, но может не сходиться совсем, если она лишь бесконечно дифференцируема.
Доказательства существенно используют некоторые новые результаты из теории интерполяции, имеющие самостоятельный интерес. В частности, я расскажу об интегральных формулах для ошибок интерполяции гауссовскими ядрами и экспоненциальными функциями в 1D, полученных с помощью интеграла Хариша–Чандры–Ициксона–Зубера и обобщающих классическую формулу Эрмита–Геноччи для ошибки полиномиальной интерполяции.
Доклад основан на материале препринтов arXiv: 1109.1320 и arXiv: 1205.5961.