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

Question

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

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

  • Пакет Java FPL Statistics Group для нелинейной оптимизации . Это включает в себя Java-перевод классических подпрограмм Fortran MINPACK.

  • JLAPACK , другой перевод на Фортран.

  • Набор инструментов алгоритма оптимизации .

  • Javanumerics .

  • Некоторая реализация Python. С чистым Python все будет в порядке, поскольку его можно скомпилировать в Java с помощью jythonc.

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

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

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

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

Answer 1

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

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

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. Есть питон (полагается на Numeric, к сожалению) и версия на C. Метод LM содержит около 1500 строк кода, поэтому вы можете склониться к переносу C на Java. Фактически, «ограниченный» метод LM мало чем отличается от метода, который вы предполагали. В mpfit код корректирует размер шага относительно границ переменных. У меня были хорошие результаты и с mpfit.

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

Удачи.

Answer 5

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

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

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