Решение нелинейных уравнений численно

Question

Мне нужно решить проблемы нелинейной минимизации (наименьшие остаточные квадраты из N неизвестных) в моей программе Java. Обычный способ решения этих проблем - алгоритм Levenberg-Marquardt. У меня есть пара вопросов

• Есть ли у кого-нибудь опыт в различных вариантах реализации LM? Существуют немного разные ароматы LM, и я слышал, что точное выполнение алгоритма оказывает большое влияние на его численную стабильность. Мои функции довольно хорошо, поэтому это, вероятно, не проблема, но, конечно, я бы хотел выбрать одну из лучших альтернатив. Вот несколько альтернатив, которые я нашел:

  • FPL Statistics Group's Nonlinear Optimization Java Package. Это включает в себя перевод Java классических подпрограмм Fortran MINPACK.

  • JLAPACK, другой перевод Fortran.

  • Optimization Algorithm Toolkit.

  • Javanumerics.

  • Некоторые реализации на Python. Pure Python будет хорошо, поскольку он может быть скомпилирован на Java с jythonc.

• Есть ли обычно используемые эвристики, чтобы сделать первоначальное предположение, что требуется LM?

• В моем приложении мне нужно установить некоторые ограничения на решение, но, к счастью, они просты: я просто требую, чтобы решения (для того, чтобы быть физическими решениями) неотрицательны. Немного отрицательные решения являются результатом погрешностей измерений в данных и, очевидно, должны быть равны нулю. Я думал использовать «обычный» LM, но повторяю так, чтобы, если некоторые из неизвестных становятся отрицательными, я устанавливаю его в ноль и разрешаю остальное от него. Реальные математики, вероятно, будут смеяться надо мной, но вы думаете, что это может сработать?

Спасибо за любые мнения!

Обновление: Это не наука о ракетах, количество параметров для решения (N) не более 5, а наборы данных едва достаточно велики, чтобы сделать возможным решение, поэтому я считаю, что Java достаточно эффективна для решения это. И я считаю, что эта проблема была решена много раз умными прикладными математиками, поэтому я просто ищу какое-то готовое решение, а не готовить свои собственные. Например. Scipy.optimize.minpack.leastsq, вероятно, будет хорошо, если бы он был чистым Python.

Answer 1

Я фактически не использовал ни одну из этих библиотек Java, поэтому возьмите это с солью: на основе бэкэндов я, вероятно, посмотрю сначала в JLAPACK. Я считаю, что LAPACK является бэкендом Numpy, который по существу является стандартом для выполнения линейной алгебры/математических манипуляций в Python. По крайней мере, вы определенно должны использовать хорошо оптимизированную библиотеку C или Fortran, а не чистую Java, потому что для больших наборов данных эти задачи могут стать чрезвычайно трудоемкими.

Для создания первоначального предположения, это действительно зависит от того, какую функцию вы пытаетесь поместить (и какие у вас есть данные). В принципе, просто найдите некоторые относительно быстрые (возможно, O (N) или лучше) вычисления, которые дадут приблизительное значение для требуемого параметра.(Недавно я сделал это с распределением Гаусса в Numpy, и я оценил среднее значение как average(values, weights = counts) - то есть средневзвешенное значение счетчиков в гистограмме, которое было истинным средним набором данных. Это был не точный центр от пика, который я искал, но он получил достаточно близко, и алгоритм прошел остаток пути.)

Что касается сохранения положительных положительных результатов, то ваш метод кажется разумным. Поскольку вы пишете программу для выполнения этой работы, возможно, просто создайте логический флаг, который позволяет легко включать или отключать поведение «неотрицательное действие» и запускать его для сравнения. Только если вы получите большое несоответствие (или если одна версия алгоритма занимает неоправданно длинную), это может быть чем-то беспокоиться. (И РЕАЛЬНЫЕ математики сделали бы минимизацию наименьших квадратов аналитически, с нуля; -P, поэтому я думаю, что вы тот, кто может смеяться над ними ... шутите. Может быть.)

Answer 2

Чем ближе ваше первоначальное предположение, тем лучше решение, тем быстрее вы сходитесь.

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

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

Answer 3

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

Если вы счастливы использовать Scipy, я бы порекомендовал scipy.optimize.fmin_l_bfgs_b Вы можете разместить простые оценки по вашим переменным с помощью L-BFGS-B.

Обратите внимание, что L-BFGS-B принимает общую нелинейную целевую функцию, а не только - нелинейную проблему наименьших квадратов.

Answer 4

Пакет FPL достаточно надежный, но имеет несколько причуд (доступ к массиву начинается с 1) из-за его очень буквальной интерпретации старого кода fortran. Сам метод LM достаточно надежный, если ваша функция хорошо себя ведет. Простым способом принудительных неотрицательных ограничений является использование квадрата параметров вместо параметров напрямую. Это может привести к ложным решениям, но для простых моделей эти решения легко экранируются.

Доступен код для «ограниченного» метода LM. Смотрите здесь http://www.physics.wisc.edu/~craigm/idl/fitting.html для mpfit. Существует python (полагается на Numeric к сожалению) и версия C. Метод LM составляет около 1500 строк кода, поэтому вы можете склоняться к переносу C на Java. Фактически, «ограниченный» метод LM не сильно отличается от метода, который вы предполагали. В mpfit код корректирует размер шага относительно границ переменных. У меня были хорошие результаты с mpfit.

У меня нет такого большого опыта работы с BFGS, но код намного сложнее, и я никогда не разбирался в лицензировании кода.

Удачи.

Answer 5

Я согласен с codehippo; Я считаю, что наилучшим способом решения проблем с ограничениями является использование алгоритмов, специально предназначенных для решения этих проблем. Алгоритм L-BFGS-B, вероятно, должен быть хорошим решением в этом случае.

Однако, если использовать scipy.optimize для python.Модуль fmin_l_bfgs_b не является жизнеспособным вариантом в вашем случае (потому что вы используете Java), вы можете попробовать использовать библиотеку, которую я написал: оболочку Java для исходного кода Fortran алгоритма L-BFGS-B. Вы можете скачать его с http://www.mini.pw.edu.pl/~mkobos/programs/lbfgsb_wrapper и посмотреть, соответствует ли он вашим потребностям.