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

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

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

мин к
ST.
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 или внутренней точки.

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

m

Answer 3

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

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 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.На каждом шаге итерации вам необходимо решить систему 4х4.Самая большая проблема, вероятно, заключается в том, с чего начать итерацию.Одна из возможностей — начать со случайной точки, выполнить несколько итераций, а если ничего не получится, выбрать другую случайную точку и начать заново.

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

Answer 5

АЛЬЖЕНКАН (часть ТАНГО) действительно хорош.Также есть привязки Python.

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

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

Answer 6

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

Answer 7

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

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

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

Answer 8

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