Выбор алгоритма

В первую очередь необходимо выбрать порядок метода. Методы нулевого порядка не имеют информации о градиенте и очень медленно сходятся, особенно в высокой размерности. Методы первого порядка не имеют доступа к информации о кривизне и могут потребовать большого количества итераций для сходимости в плохо обусловленных задачах. Методы второго порядка могут сходиться очень быстро, как только оказываются вблизи минимизатора. Конечно, за такое повышение производительности приходится платить: целевая функция должна быть дифференцируемой, вы должны предоставить градиенты и гессианы, а для методов второго порядка необходимо решать линейную систему на каждом шаге.

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

Если у вас нет явного гессиана или размерность становится настолько большой, что линейное решение в методе Ньютона становится узким местом, следует сделать выбор в пользу методов первого порядка. BFGS представляет собой очень эффективный метод, но он также требует решения линейной системы. LBFGS обычно имеет производительность, очень близкую к производительности BFGS, и позволяет избежать решения линейных систем (параметр m можно настраивать: его увеличение может улучшить сходимость за счет памяти и времени, затрачиваемых на выполнение операций линейной алгебры). Метод сопряженного градиента обычно сходится быстрее, чем LBFGS, но требует меньше памяти. Градиентный спуск следует использовать только для тестирования. Методы ускорения носят экспериментальный характер.

Если целевая функция не дифференцируема или вы не хотите использовать градиенты, обратитесь к методам нулевого порядка. В настоящее время самым надежным является метод Нелдера-Мида.

Линейные отрезки используются во всех методах первого и второго порядка, кроме метода Ньютона с доверительной областью. Процедуры линейного поиска пытаются быстро найти приближенный минимизатор одномерной функции , где  — это направление спуска, вычисленное алгоритмом. Они различаются по степени точности минимизации. Следует отметить два хороших линейных поиска — поиск с возвратом и поиск методом Хагера-Жанга, первый из которых менее строгий, чем второй. Для хорошо обусловленных целевых функций и методов, в которых шаг обычно хорошо масштабируется (например, LBFGS или метод Ньютона), грубый линейный поиск, такой как поиск с возвратом, обычно является наиболее эффективным. Для нестабильных задач или когда требуется высокая точность (градиенты ниже квадратного корня из машинного эпсилона, примерно с Float64), более надежным будет метод Хагера-Жанга. Исключение составляет метод сопряженного градиента, для эффективной работы которого требуется точный линейный поиск. Кроме того, его нужно использовать вместе с линейным поиском по Хагеру-Жангу.

Итак, сделаем следующие выводы.

Для решения низкоразмерной задачи с аналитическими градиентами и гессианами используйте метод Ньютона с доверительной областью. Для больших задач или при отсутствии аналитического гессиана используйте LBFGS и при необходимости настройте параметр m. Если функция не дифференцируема, используйте метод Нелдера-Мида. Используйте линейный поиск методом Хагера-Жанга для надежности и поиск с возвратом для скорости.