Комментарии 13
Тема замечательная, одна из моих любимых. С интересом освежил, спасибо. По этому поводу и написано много, что скрывать. И вот я бы сделал упор не на тех случаях, когда эти методы эффектно работают. А на тех, когда возникают трудности и алгоритм заходит "не туда". Иначе возникает ощущение, что вот есть функция, задвинем ее, скажем, в метод градиентного спуска - и готово дело. Пара слов была сказана: про невыпуклость, и про разброс СЗ. Но как-то вскользь. А есть еще овраги. Есть супер узкие воронки, где на конечной разрядной сетке можно вылететь с поверхности. И так далее.
Но я не спорю, что часто дело касается не самой математики, а реализации на практике. Даже теоретически хорошие функции в коде могут быть реализованы кривовато и/или давать существенную ошибку и препятствовать хорошей работе одномерного поиска, что вредит сходимости. Тут уж общих рецептов у меня нет.
Градиентные методы включая метод наискорейшего спуска и усеченного Ньютона не обеспечивают глобальной сходимости. Глобальную сходимость дают совершенно другие алгоритмы которые работают как правило через разбиение области поиска на регионы и поиск оценок минимума / максимума для функции валидных для всего региона. Опираются для этих оценок как правило на условие Липшица (ограниченность скорости роста функции) которые позволяют исходя из размеров региона и одной или нескольких точек в нем дать оценку максимума и минимума функции на всем регионе. Ну а дальше идет разбивка регионов на менее крупные и исключение из рассмотрения тех регионов (если брать минимизацию) где доказуемый минимум больше доказуемого максимума какого-то другого региона.
Спасибо за статью. Подскажите, пожалуйста, какими методами лучше искать минимум ошибки, если входные параметры вещественные, а функция ошибки - натуральные числа? Пробовал делать грубый перебор, но дальше болтанки между двумя соседними числами не продвинулся.
если f(x) дважды дифференцируема, то липшицева непрерывность гарантируется.
Если всюду дважды дифференцируема — возможно, да. А так есть, например, квадратный корень, который в окрестности нуля не липшиц-непрерывен. У меня вот лично в решаемой задаче появляется функция, которая около нуля ведёт себя как x ln(x) — если туда минимизатор залез, то уже не вылезает.
Недавно ещё узнал, что есть немонотонный поиск по направлению, где условия Вульфа выполняются только "в среднем за n итераций", что может для CG или L-BFGS ускорить сходимость (спрямляет путь через кривые овраги).
Если всюду дважды дифференцируема — возможно, да.Да, имеется в виду всюду или, по крайней мере, в зоне поиска. В контексте безусловной оптимизации это естественно.
Квадратный корень, как известно, определён не везде и имеют сингулярность в нуле.
У меня вот лично в решаемой задаче появляется функция, которая около нуля ведёт себя как x ln(x) — если туда минимизатор залез, то уже не вылезает.Не совсем понял проблему. Функция x*ln(x) около нуля ведёт себя вроде бы нормально, в бесконечности не уходит.
Хотелось бы посмотреть на поведение этих функций на монстре Вейштрасса. Если оно там может более-менее хорошо работать, то ей можно верить. Если нет - то придётся всё руками проверять.
поведение этих функций
Вы имели в виду «поведение этих методов»? Конечно же они не заточены под такие функции, как функция Вейерштрасса, хотя бы потому, что они предполагают их дифференцируемость, что неверно в случае последней.
то ей можно верить
Верить надо в рамках того контекста, в котором эти методы построены. Но даже более того, инженеры на практике не парятся и используют методы вне их рамок — с переменным, а не обязательно негативным результатом.
Обзор методов численной оптимизации. Безусловная оптимизация: метод линий