Главная       Скачать       Коммерческая поддержка       FAQ       Forum       О нас       Английская версия

Оптимизация без ограничений: L-BFGS и CG

Содержание

    1 О алгоритмах
           L-BFGS алгоритм
           Нелинейный CG
           Сравнение L-BFGS и CG
    2 Быстродействие
           Сравнение алгоритмов
           Сравнение с другими пакетами
    3 Приступая к работе
           Выбор между аналитическим и численным градиентом
           Настройка параметров алгоритма
           Масштаб переменных
           Предобуславливатель
           Условия остановки
           Запуск алгоритма
    4 Примеры

О алгоритмах

Пакет ALGLIB содержит три алгоритма для оптимизации без ограничений: L-BFGS, CG и метод Левенберга-Марквардта. В этой статье рассмотрены первые два алгоритма, объединенные следующими признаками:

  1. они решают задачу общего вида (не предполагается наличие у функции особых свойств)
  2. они требуют только значение/градиент функции (Гессиан не требуется)
  3. оба алгоритма поддерживают численное дифференцирование в случае, когда градиент функции недоступен

L-BFGS алгоритм

В основе L-BFGS алгоритма лежит последовательное построение и уточнение квадратичной модели функции. Алгоритм запоминает M последних значений функции/градиента и использует их для построения положительно определенной аппроксимации Гессиана. Аппроксимация гессиана используется для совершения шага по методу Ньютона. Если этот шаг не приводит к достаточному уменьшению функции то мы осуществляем минимизацию функции вдоль направления, заданного шагом по методу Ньютона.

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

Второе важное свойство - использование только M последних значений функции/градиента (обычно M - небольшое число порядка 3-10, много меньшее размерности задачи). Благодаря этому трудоемкость итерации составляет всего лишь O(N·M) операций.

Нелинейный CG

В отличие от L-BFGS алгоритма, нелинейный метод сопряженных градиентов не строит квадратичную модель функции. Он также осуществляет поиск минимума функции вдоль прямой. Но направление, в котором ищется минимум, в этом методе выбирается, как линейная комбинация градиента в текущей точке и предыдущего направления поиска:

xk+1  = x + αd
dk+1  = -gk+1 d

Параметр α выбирается путем минимизации f(xd). Для выбора параметра β существует несколько формул, каждая из которых соответствует отдельному алгоритму из семейства алгоритмов, объединенных общим названием "метод сопряженных градиентов". Такой подход, несмотря на свою простоту, позволяет накапливать информацию о локальной кривизне функции - эта информация сохраняется в векторе, задающем направление поиска.

Сравнение L-BFGS и CG

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

Однако есть и отличия:

Быстродействие

Быстродействие методов оптимизации сравнивалось в следующих условиях:

Сравнение алгоритмов

В первой части эксперимента мы сравнили быстродействие метода сопряженных градиентов с быстродействием L-BFGS алгоритма (m=8), входящего в состав ALGLIB. Был получен следующий результат:

Исходя из этих графиков, можно сделать следующие выводы. С точки зрения количества вычислений значения функции метод сопряженных градиентов однозначно уступает L-BFGS алгоритму. Однако данное преимущество оказывается решающим, только если минимизируемая функция является сложновычислимой. Если функция и её градиент легко вычислимы, то использование метода сопряженных градиентов может оказаться предпочтительным с точки зрения быстродействия.

Сравнение с другими пакетами

Во второй части эксперимента мы сравнили метод сопряженных градиентов, реализованный в ALGLIB, с аналогичной реализацией из GNU Scientific Library (GSL). Для тестирования использовалась GSL 1.12 (версия, поставляемая с операционной системой). Из двух вариантов метода сопряженных градиентов, входящих в состав GSL, был выбран PR-вариант. На графиках ниже можно увидеть сравнительное быстродействие ALGLIB и GSL на этой проблеме.

Пакет ALGLIB оказался в 7-8 раз быстрее, чем GNU Scientific Library - и по микросекундам, и по количеству вычислений функции/градиента. Чем же объясняется такое различие? Важнейшим фактором является использование в ALGLIB более эффективного механизма минимизации вдоль прямой. Вторым фактором является использование современной версии сопряженного градиента (в GSL используются устаревшие FR и PR варианты).

Чтобы убедиться, что полученный результат не является ошибкой или особенностью GSL, проявляющейся при работе с конкретно этой функцией, мы провели дополнительные тесты. Использование другого алгоритма (FR-вариант из GSL) привело к ещё большему различию в быстродействии - пакет ALGLIB оказался в 15-20 раз быстрее. При использовании другой тестовой функции мы получили ту же картину. Наконец, мы попробовали установить более строгий критерий сходимости - |g|<10 -14 вместо |g|<10 -8. Алгоритм из GSL отказался сходиться - в то время как алгоритм из ALGLIB корректно нашел ответ с повышенной точностью.

Приступая к работе

Выбор между аналитическим и численным градиентом

Самый первый выбор, который вам предстоит сделать - это выбор между использованием численного дифференцирования и самостоятельным вычислением градиента.

Оба алгоритма - и L-BFGS, и CG - используют градиент функции. Например, если вы ищете минимум функции f(x,y)=x 2+exp(x+y)+y 2, то для работы алгоритма потребуются как значение функции в какой-то промежуточной точке, так и производные df/dx и df/dy. Откуда взять эти производные? Пользователям пакета ALGLIB доступно несколько вариантов:

  1. пользователь вычисляет производные самостоятельно, обычно путем аналитического дифференцирования функции (т.н. аналитический градиент). Этот вариант является предпочтительным по двум причинам. Во-первых, значение градиента вычисляется с минимальной погрешностью. Во-вторых, очень часто для вычисления всех N компонент градиента требуется лишь в несколько раз больше времени, чем на вычисление одного значения функции. Это связано с тем, что знание внутренней структуры дифференцируемой функции часто позволяет вычислять вектор производных параллельно с вычислением самой функции.
  2. градиент вычисляется пакетом ALGLIB путем численного дифференцирования, с использованием четырехточечной разностной формулы. При этом пользователь вычисляет только значение функции, оставляя вопросы, связанные с дифференцированием, на усмотрение пакета ALGLIB. Этот вариант удобнее предыдущего, потому что пользователю не надо тратить время на написание кода, вычисляющего производную функции. Это позволяет очень быстро создавать работающие прототипы. Однако, есть и недостатки. Во-первых, численный градиент менее точен, чем аналитический, что может замедлить скорость сходимости алгоритма. Во-вторых, численное дифференцирование требует 4*N вычислений функции для получения только одного значения градиента. В результате численное дифференцирование можно использовать только на задачах малой размерности (не более нескольких десятков). На задачах большей размерности алгоритм также будет работать, но очень, очень долго.
  3. пользователь вычисляет производные с использованием автоматического дифференцирования. В результате оптимизатор получает быстрый аналитический градиент, а пользователь освобождается от необходимости дифференцировать функцию вручную. Пакет ALGLIB не поддерживает автоматическое дифференцирование, но мы можем рекомендовать несколько пакетов, которые можно использовать для того, чтобы вычислить градиент и передать его в ALGLIB:
    • AutoDiff для программистов на C#
    • FuncDesigner для программистов на Python
    • FADBAD++ для программистов на C++

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

Если вы решили использовать численное дифференцирование, то вы:

Настройка параметров алгоритма

Алгоритм L-BFGS довольно-таки прост в настройке. Единственный настраиваемый параметр - число M, количество пар функция/градиент, использующихся для построения квадратичной модели. Этот параметр передается в функцию, создающую объект-оптимизатор. Увеличение этого параметра приводит к снижению количества итераций, требующихся для сходимости, но увеличивает накладные расходы, связанные с итерацией. Если задача хорошо обусловлена, M может быть небольшим числом в районе 3-10. Если функция меняется в одних направлениях более резко, чем в других, то имеет смысл поэкспериментировать с увеличением M.

Что до нелинейного CG, то он не имеет настраиваемых параметров.

Масштаб переменных

Перед началом работы рекомендуется установить масштаб переменных при помощи функций minlbfgssetscale или mincgsetscale. Без установки масштаба можно обойтись, если ваша проблема хорошо отмасштабирована. Если величина некоторых переменных различается более чем в сто раз, рекомендуется установить масштаб. При более значительном различии (от тысячи раз) установка масштаба может быть необходимой для корректной работы оптимизатора.

Понятие масштаба переменных рассмотрено в отдельной статье, с которой мы настоятельно рекомендуем ознакомиться, если вы решаете что-то более сложное, чем простенькая тестовая задача.

Предобуславливатель

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

Предобуславливатель нужен:

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

Пакет ALGLIB поддерживает несколько типов предобуславливателей:

Условия остановки

Пакет ALGLIB предлагает пользователям четыре критерия остановки:

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

Мы настоятельно рекомендуем использовать первый критерий - малое значение градиента F(x). Этот критерий гарантирует, что алгоритм остановится только в достаточно хорошей точке, независимо от того, насколько медленно или быстро мы к ней приближаемся. Критерии, связанные с изменением шага или функции, менее надежны, так как в некоторых случаях алгоритм может совершать небольшие шаги даже вдали от минимума.

Замечание #1
В общем случае нельзя гарантировать, что сработает именно тот критерий остановки, который вы установили. Например, алгоритм может сделать шаг, который приведет нас точно в минимум функции, и тогда сработает критерий, связанный с нулевым значением градиента - независимо от того, какие критерии были установлены. Возможны и другие ситуации, когда срабатывает не тот критерий, который вы установили (например, из-за погрешностей операций с плавточкой).

Замечание #2
Некоторые критерии остановки используют масштаб переменных, который должен быть установлен при помощи вызова отдельной функции (см. предыдущую секцию).

Запуск алгоритма

После того, как объект-оптимизатор создан и настроен, вы можете запустить процесс оптимизации путем вызова функции minlbfgsoptimize (mincgoptimize). Аргументами функции являются оптимизатор и callbacks, вычисляющие оптимизируемую функцию/градиент. Результат работы может быть получен при помощи вызова minlbfgsresults (mincgresults).

Примеры

Для облегчения работы с алгоритмами оптимизации мы подготовили несколько примеров. Поскольку алгоритмы L-BFGS и CG обладают схожим интерфейсом, то для каждого из сценариев использования мы подготовили по два примера. Примеры отличаются только используемым алгоритмом, во всем остальном они идентичны.

Также мы рекомендуем прочитать статью 'Оптимизация - советы и приемы', которая обсуждает ряд типичных проблем, возникающих при оптимизации, и способы их решения.

This article is intended for personal use only.

Скачать ALGLIB

C#

Исходный код на C#

Downloads page

 

C++

Исходный код на C++

Downloads page

 

C++, арифметика высокой точности

Исходный код на C++, использующий библиотеки MPFR/GMP.

Исходный код GMP доступен на сайте gmplib.org. Исходный код MPFR доступен на сайте www.mpfr.org.

Downloads page

 

FreePascal

Исходный код на Free Pascal.

Downloads page

 

Delphi

Исходный код на Delphi.

Downloads page

 

VB.NET

Исходный код на VB.NET.

Downloads page

 

VBA

Исходный код на VBA.

Downloads page

 

Python

Исходный код на Python (CPython и IronPython).

Downloads page

 

 

ALGLIB® - numerical analysis library, 1999-2017.
ALGLIB is registered trademark of the ALGLIB Project.