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

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

Есть ли у кого-нибудь опыт в различных реализациях LM? Существуют немного разные ароматы LM, и я слышал, что точное выполнение алгоритма оказывает большое влияние на его численную стабильность. Мои функции довольно хорошо, поэтому это, вероятно, не проблема, но, конечно, я бы хотел выбрать одну из лучших альтернатив. Вот несколько альтернатив, которые я нашел:
- FPL Statistics Group Нелинейная оптимизация Java-пакета. Это включает в себя перевод Java классических подпрограмм Fortran MINPACK.
- JLAPACK, еще один перевод Fortran.
- Инструментарий алгоритмов оптимизации.
- Javanumerics.
- Некоторые реализации Python. Pure Python будет хорошо, поскольку он может быть скомпилирован с Java с помощью jythonc.
Существуют ли обычно используемые эвристики для первоначального предположения, что LM требует?
В моем приложении мне нужно установить некоторые ограничения на решение, но, к счастью, они просты: я просто требую, чтобы решения (для физических решений) неотрицательны. Немного отрицательные решения являются результатом погрешностей измерений в данных и, очевидно, должны быть равны нулю. Я думал использовать "обычный" LM, но повторяю так, чтобы, если некоторые из неизвестных становятся отрицательными, я устанавливаю его в ноль и разрешаю остальное от него. Реальные математики, вероятно, будут смеяться надо мной, но думаете ли вы, что это может сработать?

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

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

Ответ 1

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

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

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

Ответ 2

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

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

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

Ответ 3

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

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

Ответ 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, но код намного сложнее, и я никогда не разбирался в лицензировании кода.

Удачи.

Ответ 5

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

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

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