levmar

levmar является реализация Левенберга-Марквардт нелинейных наименьших квадратов алгоритмов в C / C ++.
Процедура lmder от MINPACK, реализованный в начале 80-х в Аргоннской национальной лаборатории, является, пожалуй, наиболее широко используется свободная реализация алгоритма LM. lmder написано в FORTRAN77 и на протяжении многих лет зарекомендовала себя как надежный кусок программного обеспечения. Учитывая, что FORTRAN подпрограмм может быть вызвана из C / C ++, можно задаться вопросом о мотивации для написания версии LM в С. Ну, проблема в том, что, когда Фортран вызывается из C, программист должен быть в курсе (и соответствовать ) несколько правил, касающихся имя коверкая, передачи аргументов, многомерного распределение памяти массив, конвенций сцепления, и т.д., которые неестественно по сравнению с обычными правилами C. Вторая причина в том, что этот подход принимает как должное, что Фортран компилятор для окружающей среды цель программирования доступна, который, возможно, не обязательно быть так. Еще одна причина связана с неспособностью понять внутреннюю работу FORTRAN реализации: Иногда, когда это необходимо, чтобы точно понять, что Фортран код делает некоторые части его может показаться непонятным для программистов без знания Фортрана. Автоматическая Фортран для C переводчиков (например, f2c) не решает проблему, так как производится С-код довольно неразборчиво на «непосвященных» человека. Кроме того, документация, описывающая математику, на которых реализация на основе может быть неясным или недоступны. Последнее, но не менее, реализация кандидат Л.М. в C должны быть свободны и технически звук. Например, С вариант алгоритма LM представлены в "Численные рецепты" книги (т.е. mrqmin), не всегда является жизнеспособным выбором: Кроме того его авторским правом, то, как считают, не хватает надежности.
По указанным выше причинам, я разработал levmar пакет, который включает C реализаций LM ароматов, которые также можно использовать с C ++. levmar включает двухместные и одноместные реализации точность LM, как с аналитической и конечных разностей приближенно якобианам. Он предоставляется бесплатно, в соответствии с условиями GNU General Public License. Математическая теория позади безусловной levmar подробно описано в примечаниях, имеющих право лекционных методов для нелинейных задач наименьших квадратов, К. Мадсен, HB Нильсен и О. Tingleff, Технический Университет Дании; Matlab реализации алгоритмов, представленных в конспектов также доступны. Заметим, однако, что постановка задачи минимизации принятой здесь немного отличается от той, что описана в конспектов.
Function используют:
levmar предлагает несколько пользовательских функций можно вызывать подчиняясь следующим именования: первая буква (D или S) Установка двойной или одинарной точности и суффикс (_der или _dif) обозначает аналитическую или приблизительное якобиан. Если присутствует, LEC, BC и BLEC компоненты подразумевает линейное уравнение, коробка и одновременное коробку и линейных ограничений уравнение, соответственно. Более конкретно, levmar включает следующие функции:
Безусловной оптимизации
dlevmar_der (): двойной точности, аналитическое якобиан
dlevmar_dif (): двойной точности, конечно разница приближенно якобиан
slevmar_der (): одинарной точности, аналитическое якобиан
slevmar_dif (): с одинарной точностью, конечных разностей приближенно якобиан
Условный экстремум
dlevmar_lec_der (): двойной точности, линейные ограничения уравнение, аналитическое якобиан
dlevmar_lec_dif (): двойной точности, линейные ограничения уравнение, разностная приближенно якобиан
slevmar_lec_der (): одинарной точности, линейные ограничения уравнение, аналитическое якобиан
slevmar_lec_dif (): одинарной точности, линейные ограничения уравнение, разностная приближенно якобиан
dlevmar_bc_der (): двойной точности, коробка ограничения, аналитическая якобиан
dlevmar_bc_dif (): двойной точности, коробка ограничения, конечная разность приближенно якобиан
slevmar_bc_der (): одинарной точности, коробка ограничения, аналитическая якобиан
slevmar_bc_dif (): одинарной точности, коробка ограничения, конечная разность приближенно якобиан
dlevmar_blec_der (): двойной точности, коробка и линейные ограничения уравнение, аналитическое якобиан
dlevmar_blec_dif (): двойной точности, коробка и линейные ограничения уравнение, разностная приближенно якобиан
slevmar_blec_der (): одинарной точности, коробка и линейные ограничения уравнение, аналитическое якобиан
slevmar_blec_dif (): одинарной точности, коробка и линейные ограничения уравнение, разностная приближенно якобиан
Обратите внимание, что с помощью конечных разностей для аппроксимации Якоби приводит повторяющихся оценок функции для установки. Стремясь уменьшить общее количество этих оценок, функции xxxxxxx_dif реализации секущими приближения к Якоби, используя ранг одного обновления Бройдена в. Все функции решения той же задачи, то есть они стремятся вектора параметров р, что наилучшим образом описывает (в терминах нормы L2) Измерения вектор х. Точнее, учитывая вектор-функцию F: R ^ м -> R ^ N с п> = м, они вычислить AP, такие, что F (P) ~ = х, то есть квадрата нормы || || е ^ 2 = | | XF (р) || ^ 2 сводится к минимуму. Кроме того, коробка ограничения вида фунт [я]

Что нового В этом выпуске:

• этой версии добавлена ​​поддержка для диагональ масштабирование для xlevmar_bc_der (), которые могут улучшить сходимость, когда отправной точкой является далеко от истинного минимизатор.
• Линейный решатель систем поддержки параллельного разложения Холецкого с плазменным, линейной алгебры библиотеки для многоядерных процессоров.
• Линейные решатели были закреплены так, что они работают на более низких треугольников симметричных матриц, что приводит к повышению производительности кэша.
• Файлы конфигурации CMake для сборки проекта были пересмотрены.
• Несколько другие незначительные изменения были сделаны.

Что нового в версии 2.5:

• ВНИМАНИЕ для предыдущих версий ПОЛЬЗОВАТЕЛЕЙ: Для лучшего соответствия и избежания конфликты, имя файла заголовка levmar была изменена с lm.h в levmar.h; пожалуйста, обновите ваши исходные файлы, соответственно.
• Добавлена ​​поддержка минимизации при одновременном поле, линейных уравнений и неравенств ограничений (см функции xlevmar_bleic_der () & xlevmar_bleic_dif ()).
• Реализованные удобство обертками для xlevmar_bleic_der () & () xlevmar_bleic_dif дело с более простыми ограничениями случаях, например, xlevmar_blic_der () & xlevmar_blic_dif () минимизация поддержка в графе и линейные ограничения в виде неравенств только.
• Добавлена ​​линейный решатель системы, основанные на разложении Удут (т.е., SQRT без Холецкого).
• Убраны некоторые ненужные копирование памяти от большинства линейных решателей.
• Добавлена ​​новая тестовой задачи подбора данных (Osborne).
• Сделано несколько других незначительных изменений.

Что нового в версии 2.4:

• ВНИМАНИЕ для предыдущих версий ПОЛЬЗОВАТЕЛЕЙ: Размер инфо аргумента (т.е. LM_INFO_SZ) был увеличен на единицу, чтобы вместить новую обратный поле (то есть, информации [9]), что соответствует общему числу линейных систем, решаемых в ходе минимизации. Индексы ранее возвращенных полей в инфо массива остаются без изменений.
• Реализовано более кэш-эффективные схемы для вычисления приблизительной Гессе J ^ Т * J J ^ и Т * е для задач малого размера минимизации.
• Обеспечение, что любая рабочая память сохранила между вызовами линейных решателей высвобождается при прекращении levmar процедур.
• Обеспечение, что линейные решатели используют минимальное необходимое количество вспомогательного памяти, избегая иногда чрезмерно ассигнований.
• Реализована схема разворачивания цикла для ускорения вычисления е = х-Гк.
• Исправлена ​​пара проблем с выравниванием памяти на 64-битных системах.
• Добавлены функции для вычисления коэффициента детерминации.
• дело с несколько незначительных вопросов.