levmar

levmar é uma implementação da não-linear Levenberg-Marquardt mínimos quadrados algoritmos em C / C ++.
A rotina lmder de MINPACK, implementado no início dos anos 80, no Laboratório Nacional Argonne, é, talvez, o mais amplamente utilizado livre implementação do algoritmo de LM. lmder é escrito em FORTRAN77 e ao longo dos anos tem provado ser uma peça confiável de software. Considerando-se que as rotinas Fortran pode ser chamado de C / C ++, pode-se perguntar sobre a motivação para escrever uma versão do LM em C. Bem, o problema é que quando Fortran é chamado de C, o programador deve estar ciente de (e em conformidade com ) várias regras relativas desconfiguração do nome, o argumento de passagem, layout de memória matriz multidimensional, convenções de ligação, etc, que não são naturais em comparação com regras comuns C. A segunda razão é que esta abordagem toma como certo que um compilador Fortran para o ambiente de programação alvo está disponível, o que pode não ser necessariamente o caso. Outra razão tem a ver com a incapacidade de compreender o funcionamento interno de uma aplicação Fortran: Ocasionalmente, quando é necessário para entender exatamente o que o código FORTRAN faz, certas partes dele pode parecer incompreensível para programadores sem qualquer conhecimento do Fortran. FORTRAN Automatic para tradutores C (por exemplo, f2c) não resolver o problema, já que o código C produzido é bastante ilegível para os seres humanos "não iniciados". Além disso, a documentação que descreve a matemática em que a implementação se baseia pode ser obscuro ou inacessível. Por último, mas não menos importante, uma implementação candidato LM em C deve ser livre e tecnicamente sólida. Por exemplo, a variante C do algoritmo LM apresentado no "Numerical Recipes" livro (ie mrqmin), nem sempre é uma opção viável: Além de seu ser com direitos de autor, que tem a fama de falta de robustez
. Pelas razões acima expostas, tenho desenvolvido o pacote levmar que inclui implementações C de sabores LM, que também são utilizáveis ​​com C ++. levmar inclui implementações de casal e solteiro precisão LM, ambos com diferença analítica e finito aproximado Jacobianos. Ele é fornecido gratuitamente, sob os termos da GNU General Public License. A teoria matemática por trás levmar irrestrita é descrito em detalhes nas notas de aula Métodos direito para não-linear dos Mínimos Quadrados Problemas, por K. Madsen, HB Nielsen e O. Tingleff, Universidade Técnica da Dinamarca; Matlab implementações dos algoritmos apresentados nas notas de aula também estão disponíveis. Note, porém, que a formulação do problema de minimização adotada aqui é um pouco diferente do que foi descrito nas notas de aula Use de
Função:.
Levmar oferece várias funções que pode ser chamado pelo usuário, obedecendo a seguinte convenção de nomenclatura: A primeira letra (d ou s) especifica precisão dupla ou simples e o sufixo (_der ou _dif) denota Jacobian analítica ou aproximado. Se estiver presente, o LEC, bc e componentes BLEC implica equação linear, box e caixa simultânea e restrições de equações lineares, respectivamente. Mais especificamente, levmar inclui as funções abaixo:
otimização sem restrições
dlevmar_der (): precisão dupla, Jacobian analítico
dlevmar_dif (): precisão dupla, diferença finita aproximada slevmar_der Jacobian
(): precisão única, analítico slevmar_dif
Jacobian (): precisão única, diferença finita aproximada Jacobian
otimização restrita
dlevmar_lec_der () : precisão dupla, as restrições de equações lineares, Jacobian analítico
dlevmar_lec_dif (): precisão dupla, as restrições de equações lineares, diferença finita aproximada Jacobian
slevmar_lec_der (): precisão única, restrições de equações lineares,
Jacobian analítica slevmar_lec_dif (): precisão única, restrições de equações lineares, diferença finita aproximada Jacobian
dlevmar_bc_der (): precisão dupla, as restrições de caixa, Jacobian analítico
dlevmar_bc_dif (): precisão dupla, as restrições de caixa, finita diferença aproximada Jacobian
slevmar_bc_der (): precisão única, as restrições de caixa, analítico slevmar_bc_dif
Jacobian (): precisão única, as restrições de caixa, diferença finita aproximada Jacobian
dlevmar_blec_der (): double precisão, caixa e restrições de equações lineares, analítico dlevmar_blec_dif
Jacobian (): precisão dupla, caixa e restrições de equações lineares, diferença finita aproximada Jacobian
slevmar_blec_der (): precisão simples, caixa & equação linear restrições, Jacobian analítica
slevmar_blec_dif (): restrições de precisão simples, caixa & equação linear, diferença finita aproximada Jacobian
Observe que usando diferenças finitas para aproximar os resultados Jacobianas em avaliações repetidas da função a ser montados. Com o objetivo de reduzir o número total destas avaliações, as funções xxxxxxx_dif implementar aproximações secantes ao Jacobian usando um posto atualizações de Broyden. Todas as funções de resolver o mesmo problema, ou seja, eles procuram o vetor de parâmetros p que melhor descreve (em termos de a norma L2) a medições vector x. Mais precisamente, dado um vetor função f: R ^ m -> R ^ n com n> = m, eles computam ap tal que f (p) ~ = x, ou seja, a norma quadrado || e || ^ 2 = | | xf (p) || ^ 2 é minimizada. Além disso, as restrições de caixa da forma lb [i]

O que é novo nesta versão:

• Esta versão adiciona suporte para scaling diagonal para xlevmar_bc_der (), o que pode melhorar a convergência quando o ponto de partida é muito longe da verdade minimizador.
• A sistemas solver linear apoio decomposição Cholesky paralelo com PLASMA, a biblioteca de álgebra linear para processadores multi-core.
• solucionadores lineares foram corrigidos para que eles operam em triângulos inferiores de matrizes simétricas, o que resulta em melhor desempenho do cache.
• Os arquivos de configuração do CMake para a construção do projeto foram revistos.
• Várias outras pequenas alterações foram feitas.

O que é novo na versão 2.5:

• CUIDADO para versões anteriores USUÁRIOS: Para uma melhor consistência e evitar a conflitos, o nome do arquivo de cabeçalho do levmar foi alterada de lm.h para levmar.h; por favor atualize seus arquivos de origem em conformidade.
• Adicionado suporte para minimização sob a caixa simultânea, equação e desigualdade restrições lineares (ver funções xlevmar_bleic_der () & xlevmar_bleic_dif ()).
• wrappers conveniência implementadas para xlevmar_bleic_der () & xlevmar_bleic_dif () lidar com casos mais simples, por exemplo, com restrições xlevmar_blic_der () & xlevmar_blic_dif () minimização de apoio sob a caixa e restrições de desigualdade lineares só.
• Adicionado a sistemas solver linear baseado na decomposição UDUt (ie, livre-sqrt Cholesky).
• Removido alguns cópia de memória desnecessária na maioria dos solucionadores lineares.
• Adicionado um novo problema teste de ajuste de dados (Osborne).
• Feitas algumas outras pequenas alterações.

O que é novo na versão 2.4:

• CUIDADO para versões anteriores USUÁRIOS: O tamanho do argumento Informação (ou seja, LM_INFO_SZ) foi aumentado por um para acomodar um novo campo de retorno (isto é, informação [9]), que corresponde ao número total de sistemas lineares resolvido durante o curso da minimização. Os índices de campos previamente devolvidos na Informação matriz permanecem inalteradas.
• Implementação de um sistema mais eficiente-cache para o cálculo do Hessian J aproximada ^ T * J e J ^ T * e para pequeno porte problemas de minimização.
• assegurado que qualquer memória de trabalho mantidas entre as invocações dos solucionadores lineares é liberado após o término de rotinas levmar.
• garantiu que solucionadores lineares empregar a quantidade mínima necessária de memória auxiliar, evitando eventual excesso de alocações.
• aplicado um regime desenrolar loop para acelerar a computação de e = x-hx.
• Corrigido um par de problemas com alinhamento de memória em sistemas de 64 bits.
• Adicionado funções para o cálculo do coeficiente de determinação.
• Negociado com algumas questões menores.