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

Question

У меня есть пять значений, 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).

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

РЕДАКТИРОВАТЬ: это нелинейные функции. Кроме того, они не могут быть охарактеризованы. Некоторые из них могут быть в конечном итоге интерполированы из таблицы данных.

Answer 1

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

• Если функции дважды дифференцируемы, и вы можете вычислить первую производную, вы можете попробовать вариант Ньютон-Рафсон
• Взгляните на метод множителей Лагранжа для реализации ограничения.
• Если функция F непрерывна (что, вероятно, является интерполяцией), вы также можете попробовать метод деления пополам, который очень похож на двоичный поиск.

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

Answer 2

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

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

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

Answer 3

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

мин к
ул.
A + B + C + D + E = 1
F1 (A) - k = 0
F2 (B) - k = 0
F3 (C) -k = 0
F4 (D) - k = 0
F5 (E) -k = 0

Теперь мы можем решить это любым удобным для нас способом, например, методом штрафа.

min k + mu * сумма (Fi (x_i) - k) ^ 2 й
A + B + C + D + E = 1

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

Более подробная информация, и я могу помочь советом относительно хорошего метода.

м * * тысяча двадцать-одина

Answer 4

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

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

означает, что A, B, C, D и E равны 1/5. Хотя не уверен, что ты этого хочешь ...

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

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

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

Answer 5

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

Прежде всего, вам нужно решить только 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. </p>

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

Answer 6

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

Answer 7

Сначала я бы попробовал Оптимизацию частиц. Это очень легко реализовать и настроить. См. Страницу Wiki для этого.

Answer 8

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

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

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