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

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

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

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ограничения

Алгоритм Левенберга-Марквардта поддерживает оптимизацию с простыми ограничениями, т.е. ограничениями вида l≤x≤u. Простые ограничения устанавливаются при помощи функции minlmsetbc. Эти ограничения обрабатываются очень эффективно - N ограничений требует всего лишь O(N) дополнительных операций при каждом вычислении функции. Наконец, эти ограничения всегда выполняются в точности. Мы не вычисляем функцию в точках, координаты которых лежат за пределами интервала, задаваемого ограничениями. Результат оптимизации также всегда строго удовлетворяет ограничениям (находится либо во внутренней области, либо на границе).

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

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

Примеры

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

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

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

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

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

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

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

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

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

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.