Основы теории оптимизации (стр. 96 )

ALGLIB User Guide - Одномерная и многомерная оптимизация - Метод Левенберга-Марквардта

Метод Левенберга-Марквардта

Метод Левенберга-Марквардта – хороший выбор, если вам требуется минимизировать функцию вида F=f1 2(x1 ,...,xn )+ ... +fm 2(x1 ,...,xn ). Алгоритм удачно сочетает в себе метод наискорейшего спуска (т. е. минимизации вдоль градиента) и метод Ньютона (т. е. использование квадратичной модели для ускорения поиска минимума функции). От метода наискорейшего спуска алгоритм позаимствовал стабильность работы, от метода Ньютона – ускоренную сходимость в окрестностях минимума. Ниже приведено обсуждение стандартной реализации алгоритма Левенберга-Марквардта, её недостатков, и улучшенной версии алгоритма, входящей в пакет ALGLIB. Перед чтением этого раздела рекомендуется ознакомиться с описанием алгоритма в Википедии или в Numerical Recipes. Далее мы предполагаем, что читающий понимает общие принципы работы алгоритма Левенберга-Марквардта.

Применение метода Левенберга-Марквардта

Солвер для нелинейного МНК

Наиболее часто встречающееся применение метода Левенберга-Марквардта - решение задач нелинейной регрессии. В принципе, ничто не мешает вам использовать для этого интерфейс, представляемый субпакетом minlm, и рассмотренный ниже. Однако в пакете ALGLIB существует специальный интерфейс для решения таких задач, входящий в состав субпакета lsfit. Использование специализированного интерфейса обычно более удобно, чем работа с методом оптимизации напрямую.

Оптимизатор функции, представленной в виде суммы квадратов

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

Хотя минимум такой F(x) может быть найден с использованием алгоритмов для функций общего вида (нелинейный CG или L-BFGS), метод Левенберга-Марквардта позволяет использовать знание внутренней структуры для более быстрой сходимости к минимуму.

Оптимизатор функции обшего вида

Последним, менее известным применением метода Левенберга-Марквардта является оптимизация функций общего вида, т. е. функций, которые не разлагаются на сумму квадратов более простых функций. Метод Левенберга-Марквардта имеет смысл применять, если нам доступен Гессиан функции F(x) и мы хотим использовать его для оптимизации.

Начало работы с методом Левенберга-Марквардта

Выбор режима оптимизации

В зависимости от того, какая информация о функции доступна, алгоритм может использоваться в следующих вариантах:

V (function vector). Функция F(x) представлена, как сумма квадратов. Доступен только вектор функций f. Якобиан вычисляется с использованием численного дифференцирования и метода секущих. VJ (vector+Jacobian). Функция F(x) представлена, как сумма квадратов. Доступны вектор функций f и Якобиан J. FGH (function+gradient+Hessian). Функция F(x) имеет общий вид. Нам доступны значение F(x), градиент G и Гессиан H.

Буквы в названии схемы являются суффиксом, который дописывается к имени подпрограммы minlmcreate, использующейся для создания оптимизатора. Так, пользователям ALGLIB доступны следующие подпрограммы: minlmcreatev, minlmcreatevj, minlmcreatefgh.

Замечание
Также доступен дополнительный вариант алгоритма, который можно использовать для задач с разреженным Якобианом - VGJ (vector+gradient+Jacobian). В этом режиме алгоритм использует вектор функций, Якобиан, а также градиент функции F(x), равный произведению f TJ. Этот режим имеет смысл использовать в сочетании со второй стратегией ускорения сходимости (см. ниже).

Какую же схему следует выбрать? Для быстрого старта мы рекомендуем начать со схемы V (подпрограмма minlmcreatev), потому что она наиболее проста в использовании. От вас требуется только вектор функций f, и не требуется Якобиан. Вы просто пишете код, вычисляющий значение функции, а пакет ALGLIB берет на себя вопросы, связанные с численным дифференцированием.

Следующий шаг. Итак, вы убедились, что пакет ALGLIB (и ваш код для вычисления функции) работают нормально. Как мы уже говорили, оптимизация без использования Якобиана очень проста в реализации, но не очень эффективна. Кроме того, численное дифференцирование не позволяет найти минимум с точностью, существенно превышающей шаг дифференцирования. Если вам требуется хорошее быстродействие (или высокая точность), то имеет смысл реализовать вычисление аналитического Якобиана и перейти к схеме VJ.

Замечание
Если вы осуществляете оптимизацию функции общего вида (с использованием Гессиана), то вам придется сразу начинать со схемы FGH и реализовать всё - функцию, градиент, Гессиан.

Выбор критериев остановки

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

после снижения градиента F(x) до заданной величины после совершения достаточно малого шага после достаточно малого изменения функции на последнем шаге по достижению предельного числа итераций

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

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

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

Запуск алгоритма и получение результатов

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

Примеры

ALGLIB Reference Manual содержит ряд примеров, посвященных оптимизации с использованием алгоритма Левенберга-Марквардта:

пример minlm_d_v, который демонстрирует оптимизацию без использования производных пример minlm_d_vj, который демонстрирует оптимизацию с использованием Якобиана пример minlm_d_fgh, который демонстрирует оптимизацию по схеме FGH пример minlm_d_restarts, который демонстрирует использование быстрых рестартов

В этих примерах рассмотрено несколько наиболее типичных способов использования оптимизатора. Вы можете скопировать код примера в свою среду разработки, запустить его, проанализировать результаты, попробовать внести свои изменения. Мы рекомендуем ознакомиться с этими примерами перед тем, как вы начнете писать свой код, использующий ALGLIB.

Улучшая быстродействие

Быстрый перезапуск

Если вы последовательно решаете ряд задач с одними и теми же характеристиками (размерность, параметры оптимизатора), то вы можете создавать новый объект-оптимизатор каждый раз, когда вы приступаете к решению новой задачи. Однако создание оптимизатора - трудоемкий процесс, в котором активно используется динамическое выделение памяти. Более эффективным решением является использование функции minlmrestartfrom, которая позволяет перезапустить уже созданный оптимизатор с новой позиции без повторного выделения памяти.

Ускорение сходимости

Оригинальный алгоритм Левенберга-Марквардта предполагает построение квадратичной модели функции и совершение шага, после чего модель отбрасывается и мы строим новую квадратичную модель. Именно такой алгоритм используется по умолчанию в схемах VJ и FGH. Однако построение квадратичной модели с нуля может быть очень трудоемким процессом, что приводит нас к первой стратегии ускорения сходимости.

Первая стратегия ускорения сходимости состоит в том, что после совершения шага мы не вычисляем Якобиан заново, а обновляем его по методу секущих, используя значения функций (не производных) в новой точке. Обновленный Якобиан менее точен, и качество следующего шага будет меньше, но он все же приведет к уменьшению значения функции. В итоге мы совершаем больше шагов (и решаем больше систем линейных уравнений), но меньшее количество раз вычисляем Якобиан. Очевидно, что такая стратегия хороша, если стоимость вычисления Якобиана размером MxN высока - существенно выше, чем стоимость разложения Холецкого матрицы размером NxN.

Эта стратегия включается вызовом minlmsetacctype(state,1) и может быть использована вместе с любой схемой оптимизации, включающей использование вектора значений функции (V, VJ, VGJ). Она включена по умолчанию при использовании схемы V. В этом случае Якобиан вычисляется с использованием численного дифференцирования, что является трудоемкой процедурой, и использование первой стратегии всегда оправдано. В прочих случаях эта стратегия должна быть явно включена функцией minlmsetacctype.

Вторая стратегия ускорения сходимости диаметрально противоположна первой. Вспомним, что стоимость шага по методу Левенберга-Марквардта складывается из двух составляющих: вычисления Якобиана и решения системы линейных уравнений (трудоемкость O(M·N 2)). Первая стратегия разработана для случая, когда вычисление Якобиана является дорогостоящей операцией - существенно более дорогой, чем решение системы линейных уравнений. Вторая стратегия разработана для противоположной ситуации - вычисление Якобиана является дешевой операцией с трудоемкостью O(N·M). В этом случае естественным является минимизировать количество систем линейных уравнений, которые нам надо решать, и повторно использовать квадратичную модель, даже если это приведет к дополнительным вычислениям Якобиана.