Algoritmo para otimização multidimensional / root-finding / algo

Question

I tem cinco valores, A, B, C, D e E.

Dada a restrição de A + B + C + D + E = 1, e cinco funções F (A), f (B), f (C), F (D), F (E), que preciso para resolver para a a E, tal que f (a) = M (B) = F (C) = F (D) = F (E).

O que é o melhor algoritmo / abordagem para usar para isso? Eu não me importo se eu tiver que escrevê-lo eu mesmo, eu gostaria apenas de saber para onde olhar.

EDIT: Estes são funções não-lineares. Além disso, eles não podem ser caracterizadas. Alguns deles podem eventualmente ser interpolado a partir de uma tabela de dados.

Answer 1

Não há uma resposta geral para esta questão. Um solucionador de encontrar a solução para qualquer equação não existe. Como Lance Roberts já diz, você tem que saber mais sobre as funções. Apenas alguns exemplos

• Se as funções são duas vezes diferenciável, e você pode calcular a primeira derivada, você pode tentar uma variante do Newton-Raphson
• Tenha um olhar para o Lagrange Método Multiplicador para implementar a restrição.
• Se a função F é contínua (que provavelmente é, se é uma interpolação), você também pode tentar o método Bissecção, que é muito parecido com busca binária.

Antes que você possa resolver o problema, você realmente precisa saber mais sobre a função que você está estudando.

Answer 2

Como outros já publicado, nós precisamos de mais algumas informações sobre as funções. No entanto, dado que, ainda podemos tentar resolver o seguinte relaxamento com uma caixa de ferramentas de programação não-linear padrão.

min k
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

Agora podemos resolver isso de qualquer maneira que deseja, como método de penalidade

min k + mu * soma (Fi (x_i) - k) 2 ^ st
A + B + C + D + E = 1

ou um método SQP direta ou interior-ponto.

Mais detalhes e eu posso ajudar aconselhar quanto a um bom método.

m

Answer 3

As funções são todos monótona crescente com o seu argumento. Além disso, eles não podem ser caracterizadas. A abordagem que funcionou acabou por ser:

1) Iniciar com A = B = C = D = E = 1/5
2) Calcula-F1 (A) por meio de F5 (E), e A a E recalcular de tal modo que cada função que é igual a soma dividida por cinco (média).
3) Rescale o novo A a E para que todos eles soma a 1, e F1 recalcular através F5.
4) Repita até satisfeito.

Ela converge surpreendentemente rápido - apenas algumas iterações. Claro, cada iteração requer 5 achados raiz para o passo 2.

Answer 4

Uma solução das equações

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

é tomar A, B, C, D e E tudo igual a 1/5. Não tenho certeza embora se isso é o que você quer ...

Adicionado depois do comentário de John (obrigado!)

Assumindo que a segunda equação deve ler F1 (A) = F2 (B) = F3 (C) = F4 (D) = F5 (E), eu usar o método de Newton-Raphson (ver a resposta de Martijn). Você pode eliminar uma variável, definindo E = 1 - A - B - C - D. A cada passo da iteração que você precisa para resolver um sistema 4x4. O maior problema é provavelmente onde começar a iteração. Uma possibilidade é começar em um ponto aleatório, fazer algumas iterações, e se você não está recebendo qualquer lugar, escolher um outro ponto aleatório e começar de novo.

Tenha em mente que se você realmente não sabe nada sobre a função, então não precisa ser uma solução.

Answer 5

ALGENCAN (parte do TANGO) é muito bom. Existem ligações Python também.

http://www.ime.usp.br/~egbirgin /tango/codes.php -. "programação não-linear geral que não utiliza manipulações de matriz em tudo e, por isso, é capaz de resolver extremamente grandes problemas com o tempo de computador moderada O algoritmo geral é do tipo Lagrangiano Aumentado ... "

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

Answer 6

O Google OPTIF9 ou ALLUNC. Nós usamos estes para otimização geral.

Answer 7

Você pode usar padrão técnica de pesquisa como os outros mencionados. Há uma otimização de alguns que você poderia fazer uso dele ao fazer a pesquisa.

Em primeiro lugar, você só precisa resolver A, B, C, D, porque 1-E = A + B + C + D.

Em segundo lugar, você tem F (A) = F (B) = F (C) = F (D), então você pode procurar por A. Depois de conseguir F (A), você poderia resolver B, C, D se isso é possível. Se não for possível resolver as funções, você precisa continuar pesquisar cada variável, mas agora você tem uma gama limitada de pesquisa para porque A + B + C + D <= 1.

Se a pesquisa é discreto e finito, as otimizações acima deve funcionar bem razoável.

Answer 8

Gostaria de tentar Enxame de Partículas em primeiro lugar. É muito fácil de implementar e ajustar. Veja a página Wiki para ele.