Алгоритм минимизации 2D-функций или библиотека C / C ++
Мне нужно минимизировать 2D function f(x,y), у меня уже есть 1-D минимизация с использованием Brent's Method (похоже на бисекционный поиск для поиска корня.) Я подумал 2D Версия была бы довольно простой, распространенной проблемой, в которой было бы много хороших алгоритмов и библиотек, но я не нашел ни одной. Я думаю только об использовании Downhill Simplex from Numerical Recipes, но я подумал, что может быть проще 2Dили удобная библиотека.
Для заинтересованных, вот еще несколько деталей:
Я на самом деле пытаюсь найти линию, которая минимизирует точку между двумя одномерными функциями, АКА — битангенс. 1D-функции обычно выглядят как параболы, и в какой-то момент они пересекаются. Точка пересечения дает X точки для минимизации, и я хочу найти линию, которая касается парабол, которая минимизирует Y в этом X.
Итак, я действительно minimizing g( f1(x1), f2(x2) ),
К сожалению, у меня нет больше информации о f1 () и f2 (). Функции выбираются или даже предоставляются пользователем. Если пользователь предоставляет данные, я получаю функции в виде набора точек. Я могу сделать интерполяцию, чтобы получить довольно хорошую числовую производную в любой точке линии, но это все. Предыдущий разработчик думал, что минимизация — это самый общий способ найти битангенс. Я все еще пытаюсь выяснить, был ли он прав.
Решение
Я так понимаю ты хочешь minimize g(f1(x),f2(y)) = h(x,y), Downhill Simplex может быть хорошим решением вашей проблемы, поскольку его легко реализовать, если у вас есть NR. Другим возможным методом может быть метод Бройдена. Однако, поскольку у вас есть производные, вы можете использовать алгоритмы, которые также предоставляют эту информацию. Например, Метод сопряженного градиента существует в реализации NR (или, по крайней мере, NR3).
В случае, если вы можете предоставить grad(h) быть очень простым, то есть grad(h)[1] в зависимости от одного и grad(h)[2] с другой переменной, это может быть проще всего решить для grad(h) = 0 и проверьте, если это минимум. Даже если градиент не так прост, вы можете решить проблему рукой и предоставить общую формулу, которая делает работу, если f1 а также f2 следовать определенному шаблону (например, если они различаются только в отношении параметров).
Другие решения
Минимизация сопряженного градиента, вероятно, подойдет.
Но ваша проблема также может быть сформулирована как система из двух уравнений с двумя неизвестными вместо.
Вы знаете кривые и их наклоны, поэтому для данного X1 Вы можете найти ординату Z1(X1) где касательная к кривой 1 пересекает вертикаль через X, И аналогично Z2(X2), Одновременно рассмотрим ординату пересечения между вертикалью и линией, проходящей через две точки касания, Z(X1, X2),
Z1(X1) = Y1(X1) + Y1'(X1).(X1 - X)
Z2(X2) = Y2(X2) + Y2'(X2).(X2 - X)
Z(X1, X2) = ((X1 - X).Y2(X2) - (X2 - X).Y1(X1)) / (X1 - X2)
Теперь вам нужно решить Z1(X1) = Z2(X2) = Z(X1, X2)возможно, используя тот же метод, который вы использовали, чтобы найти значение X,
В научной библиотеке Gnu есть функции минимизации, которые мне нужны, поэтому я интегрирую их. Ответы были довольно хорошими, но в моем случае они оказались не лучшим решением. Во многом потому, что я недостаточно четко сформулировал проблему.