Алгоритм многомерной оптимизации/корневой нахождения/что-то

У меня есть пять значений, A, B, C, D и E.Алгоритм многомерной оптимизации/корневой нахождения/что-то

Учитывая сдерживающие A + B + C + D + E = 1, и пять функций F (A), F (B), F (C), F (D), F (E), мне нужно решить для A-E такие, что F (A) = F (B) = F (C) = F (D) = F (E).

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

EDIT: Это нелинейные функции. Помимо этого, их нельзя охарактеризовать. Некоторые из них могут быть впоследствии интерполированы из таблицы данных.

источник

2009-08-21 avalys

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

Вы должны придать вашим функциям разные имена, чтобы не путать людей. – starblue

Являются ли ваши значения A ... E также неотрицательными? Во многих проблемах, когда значения ограничены суммой до 1, они также не должны быть отрицательными. Существуют ли другие ограничения? –

Общего ответа на этот вопрос нет. Решатель, найдя решение для любого уравнения, не существует. Как уже говорит Лэнс Робертс, вам нужно больше узнать о функциях. Всего лишь несколько примеров

Если функции дважды дифференцируемы, и вы можете вычислить первую производную, вы можете попробовать вариант Newton-Raphson
Посмотрите на Lagrange Multiplier Method для реализации ограничений.
Если функция F является непрерывной (что, вероятно, является, если она является интерполятором), вы также можете попробовать метод Bisection, который очень похож на двоичный поиск.

Прежде чем вы сможете решить проблему, вам действительно нужно больше узнать о функции, которую вы изучаете.

источник

2009-08-21 06:15:44 Martijn

непрерывная функция, которая не имеет производной или слишком сложна, должна выполняться методом brents. Это комбинация интерполяции параболы и золотого деления пополам, она может быть адаптирована для минимальной и максимальной оптимизации, а код довольно прямой, ознакомьтесь с ЧИСЛЕННЫМИ РЕЦЕПТАМИ на C для дальнейшего использования и методов оптимизации. – nlucaroni

Спасибо nlucaroni за предложение другого метода (которого я не знал). – Martijn

@ nlucaroni: метод Brent - только 1D. И, кстати, NR в C 15 лет. Рассмотрите возможность обновления до (удивительного) 3-го издания. –

ALGENCAN (часть TANGO) действительно приятный. Также есть привязки Python.

http://www.ime.usp.br/~egbirgin/tango/codes.php - «общего нелинейного программирования, который не использует матричные манипуляции на всех, и, таким образом, способен решать чрезвычайно большие проблемы с умеренным компьютерного времени Общий алгоритм типа дополненной лагранжиана ....»

http://pypi.python.org/pypi/TANGO%20Project%20-%20ALGENCAN/1.0

источник

2009-08-21 06:27:40

Одно из решений уравнений

A + B + C + D + E = 1 
F(A) = F(B) = F(C) = F(D) = F(E)

это взять A, B, C, D и Е все равны 1/5. Не уверен, хотя ли это то, что вы хотите ...

Добавлено после комментария Иоанна (спасибо!)

Если предположить, что второе уравнение следует читать F1 (А) = F2 (B) = F3 (C) = F4 (D) = F5 (E), я бы использовал метод Ньютона-Рафсона (см. Ответ Мартьяна). Вы можете исключить одну переменную, установив E = 1 - A - B - C - D. На каждом шаге итерации вам нужно решить систему 4x4. Самая большая проблема - это, вероятно, где начать итерацию. Одна из возможностей - начать с произвольной точки, сделать несколько итераций, и если вы никуда не денутся, выберите другую случайную точку и начните снова.

Имейте в виду, что если вы действительно ничего не знаете о функции, тогда не должно быть решения.

источник

2009-08-21 08:41:34

Это решает вопрос, но не то, что он имел в виду. Похоже, проблема должна была сказать F_1 (A) + F_2 (B) + ... –

-1

Сначала я попытался бы оптимизировать рой частиц. Его очень легко реализовать и настроить. См. Страницу Wiki.

источник

2009-08-24 18:23:28 Fantius

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

мин. K
st.
А + В + С + D + E = 1
F1 (А) - к = 0
F2 (В) - к = 0
F3 (С) -k = 0
F4 (D) - к = 0
F5 (E) -k = 0

Теперь мы можем решить эту проблему каким-либо образом мы хотим, например, методом штрафа

мин к + мю * сумма (Fi (x_i) - к)^2 st
A + B + C + D + E = 1

или прямолинейный метод SQP или внутренняя точка.

Подробнее, и я могу помочь посоветовать, как хороший метод.

источник

2009-09-01 00:29:59 SplittingField

+1. Мне нравится этот подход. –

Google OPTIF9 или ALLUNC. Мы используем их для общей оптимизации.

источник

2009-09-01 00:34:14

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

Прежде всего, вам нужно решить только A, B, C, D, потому что 1-E = A + B + C + D.

Во-вторых, у вас есть F (A) = F (B) = F (C) = F (D), то вы можете найти A. Когда вы получите F (A), вы можете решить B, C, D, если это возможно. Если вам не удастся решить эти функции, вам необходимо продолжить поиск каждой переменной, но теперь у вас есть ограниченный диапазон для поиска, потому что A + B + C + D < = 1.

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

источник

2009-09-01 00:49:31 leiz

Функции все монотонно увеличиваются с их аргументом. Помимо этого, их нельзя охарактеризовать. Подход, который работал оказался:

1) Начать с A = B = C = D = Е = 1/5
2) Вычислить F1 (А) через F5 (E), и пересчитать А-Е так что каждая функция равна этой сумме, деленной на 5 (среднее).
3) Отсканируйте новый A до E так, чтобы все они суммировались до 1 и пересчитывали F1 через F5.
4) Повторяйте до удовлетворения.

Он сходится на удивление быстро - всего несколько итераций. Конечно, для каждой итерации требуется 5 корневых поисков для шага 2.

источник

2009-09-12 04:39:59 avalys

Алгоритм многомерной оптимизации/корневой нахождения/что-то

ответ

Смежные вопросы