Задача оптимизации/нахождении экстремумов функции

[B@R5uk]

Меня интересуют методы поиска глобального экстремума или нахождения списка всех локальных экстремумов функции.

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

Мне приходят в голову следующие соображения. Если от функции $f(x)$ потребовать ограниченность по модулю второй производной, константой равной, например, $M$ ($f''(x)\leqslant M, \forall x\in\mathbb{R}$), то можно утверждать, что функция на любом отрезке заключена между двумя параболами, проведёнными через значения функции на концах этого отрезка и выгнутыми, соответственно вверх и вниз. Тогда, например, если в процессе поиска глобального максимума оказалось, что значение $A$ в пике гипотетической параболы на каком-то отрезке $[\varsigma_n,\xi_n]$ (рассчитанное по двум значениям функции на краях этого отрезка) меньше, чем значение функции в какой-то точке $\chi_m$, то можно быть на 100% уверенным, что на отрезке $[\varsigma_n,\xi_n]$ глобального максимума нет. Так же кажется разумным другое соображение (верное в рамках ограниченности второй производной): если в двух близких точках значения функции отличаются сильно (на сколько сильно — можно рассчитать), то на этом отрезке, а так же на определённом расстоянии от него (каком именно — тоже можно рассчитать) функция не может иметь экстремума.

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

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

[B@R5uk]

Тут такая мысль ещё появилась. Хотелось бы взять некий отрезок. Выбрать на нём некоторое количество точек и посчитать значения функции в этих точках. Затем МНК аппроксимировать эти значения полиномом второй или третьей степени (степень гораздо меньше количества точек). Затем оценить стандартное отклонение и по нему судить о том, как хорошо функция аппроксимируется полиномом. Если хорошо, то тогда количество особенностей (экстремумов/точек перегиба) у функции и полинома совпадают на этом отрезке и их положения (для функции и для полинома) близки. Если нет, то можно разбить отрезок на два или три пересекающихся и повторить процедуру с более частым выбором точек. Таким образом можно исследовать функцию на всём целевом отрезке, найдя все минимумы и максимумы.

Остаётся решить два вопроса (фактически это один вопрос): каков точно критерий качества аппроксимации функции полиномом (какое число должно быть меньше/больше какого)? А так же каким дополнительным условиям целевая функция должна удовлетворять, чтобы этим критерием можно было пользоваться?

Если кто-то видел статьи/книги с решением такой или подобных проблем, подскажите, пожалуйста, названия/авторов. Или хотя бы пару идей в какую сторону копать.