levmar

levmar est une implémentation de la non linéaire de Levenberg-Marquardt moindres carrés algorithmes en C / C ++.
La routine de lmder de MINPACK, mis en œuvre en début des années 80 à la National Lab Argonne, est peut-être le le plus largement utilisé implémentation libre de l'algorithme de LM. lmder est écrit en FORTRAN77 et au cours des années se est avéré être un morceau de logiciel fiable. Considérant que les routines FORTRAN peuvent être appelés à partir de C / C ++, on pourrait se interroger sur la motivation pour écrire une version de LM en C. Eh bien, le problème est que lorsque FORTRAN est appelé à partir de C, le programmeur doit être conscient (et conformes aux ) plusieurs règles concernant la décoration de nom, le passage des arguments, multidimensionnelle disposition de la mémoire de tableau, les conventions de liaison, etc, qui sont contre nature par rapport aux règles ordinaires de C. Une deuxième raison est que cette approche prend pour acquis que un compilateur FORTRAN pour l'environnement de programmation cible est disponible, ce qui pourrait ne pas être nécessairement le cas. Une autre raison a à voir avec l'échec de comprendre les rouages ​​d'une mise en œuvre FORTRAN: Parfois, quand il est nécessaire de comprendre précisément ce que fait le code FORTRAN, certaines pièces de celui-ci peuvent sembler incompréhensible pour les programmeurs sans aucune connaissance de FORTRAN. FORTRAN automatique à C traducteurs (par exemple f2c) ne résolvent pas le problème puisque le code produit C est assez illisible pour les humains "non-initiés". En outre, la documentation décrivant les mathématiques sur lesquels se fonde la mise en œuvre pourrait être obscur ou inaccessible. Last but not least, une mise en œuvre de LM candidat en C devrait être libre et techniquement solide. Par exemple, la variante C de l'algorithme de LM présenté dans le livre "Numerical Recipes" (c.-à-mrqmin), ne est pas toujours un choix viable: Outre son étant sous copyright, il est réputé manquer de robustesse
. Pour les raisons ci-dessus, je ai développé le package qui comprend levmar C implémentations de saveurs LM qui sont également utilisable avec C ++. levmar comprend implémentations simples et doubles précision LM, à la fois avec une différence d'analyse et finie approchée jacobiens. Il est fourni gratuitement, sous les termes de la licence GNU General Public License. La théorie mathématique derrière levmar contrainte est décrite en détail dans les notes de cours intitulé Méthodes pour Moindres carrés non linéaires Problèmes, par K. Madsen, HB Nielsen et O. Tingleff, Université technique du Danemark; Matlab implémentations des algorithmes présentés dans les notes de cours sont également disponibles. Notez cependant que la formulation du problème de minimisation adoptée ici est légèrement différente de celle décrite dans les notes de cours de l'utilisation
Fonction:.
Levmar offre plusieurs fonctions appelable utilisateur obéissant au convention de dénomination suivante: La première lettre (d ou s) spécifie la précision simple ou double et le suffixe (_der ou _dif) désigne jacobienne analytique ou approximative. Se il est présent, le lec, bc et composants BLEC impliquent équation linéaire, boîte et boîte simultanée et contraintes d'équations linéaires, respectivement. Plus précisément, levmar comprend les fonctions ci-dessous:
Optimisation sans contrainte
dlevmar_der (): double précision, jacobienne analytique
dlevmar_dif (): double précision, différences finies approchée slevmar_der jacobienne de
(): simple précision analytique slevmar_dif
jacobienne (): simple précision, différences finies approchée jacobienne
optimisation contrainte
dlevmar_lec_der () : double précision, les contraintes d'équations linéaires, jacobienne analytique
dlevmar_lec_dif (): double précision, les contraintes d'équations linéaires, différences finies estimés jacobienne de la slevmar_lec_der (): simple précision, les contraintes d'équations linéaires,
jacobienne analytique slevmar_lec_dif (): simple précision, les contraintes d'équations linéaires, différences finies approchée jacobienne
dlevmar_bc_der (): double précision, les contraintes de la boîte, jacobienne analytique
dlevmar_bc_dif (): double précision, les contraintes de la boîte, finie différence approchée jacobienne de la slevmar_bc_der (): simple précision, les contraintes de la boîte, analytique slevmar_bc_dif
jacobienne (): simple précision, les contraintes de la boîte, la différence finie approchée jacobienne
dlevmar_blec_der (): Double précision, boîte & contraintes d'équations linéaires, analyse dlevmar_blec_dif
jacobienne (): double précision, boîte & contraintes d'équations linéaires, différences finies estimés jacobienne de la slevmar_blec_der (): simple précision, boîte & équation linéaire contraintes, jacobienne analytique
slevmar_blec_dif (): simple précision, boîte & équation linéaire contraintes, différences finies estimés jacobienne
avis que l'utilisation de différences finies pour approcher les résultats Jacobiennes dans les évaluations répétitives de la fonction à être monté. Visant à réduire le nombre total de ces évaluations, les fonctions de mise en œuvre xxxxxxx_dif approximations sécantes à la jacobienne utilisant les mises à jour de rang un Broyden. Toutes les fonctions de résoudre le même problème, ce est à dire qu'ils cherchent le paramètre vecteur p qui décrit le mieux (en termes de la norme L2) la mesure vecteur x. Plus précisément, étant donné une fonction vectorielle f: R ^ m -> R ^ n avec n> = m, ils calculent ap telle que f (p) = x ~, à savoir la norme au carré || e || 2 = ^ | | xf (p) ^ || 2 est minimisée. En outre, la boîte contraintes de la forme lb [i]

Quoi de neuf dans cette version:

• Cette version ajoute le support pour mise à l'échelle diagonale xlevmar_bc_der (), ce qui peut améliorer la convergence lorsque le point de départ est loin d'être le vrai minimiseur.
• A systèmes solveur linéaire parallèle soutenir la décomposition de Cholesky avec PLASMA, la bibliothèque d'algèbre linéaire pour les processeurs multi-core.
• solveurs linéaires ont été corrigés afin qu'ils fonctionnent sur des triangles inférieurs de matrices symétriques, qui se traduit par de meilleures performances de la mémoire cache.
• Les fichiers de configuration CDéfinissez pour la construction du projet ont été révisées.
• Plusieurs autres modifications mineures ont été apportées.

Ce qui est nouveau dans la version 2.5:

• ATTENTION Pour les versions antérieures UTILISATEURS: Pour une meilleure cohérence et d'éviter conflits, le nom du fichier d'en-tête de levmar a été changé de lm.h à levmar.h; se il vous plaît mettre à jour vos fichiers source en conséquence.
• Ajout du support pour la minimisation sous la case simultanée, équation et de l'inégalité des contraintes linéaires (voir fonctions xlevmar_bleic_der () & xlevmar_bleic_dif ()).
• des raccourcis pratiques mises en œuvre pour xlevmar_bleic_der () & xlevmar_bleic_dif () le traitement des cas simples, par exemple contraints xlevmar_blic_der () & xlevmar_blic_dif () le soutien minimisation sous boîte et contraintes d'inégalité linéaires seulement.
• Ajout d'un solveur de systèmes linéaire basée sur la décomposition UDUt (ie, sans sqrt-Cholesky).
• Suppression de quelques copie de mémoire nécessaire de la plupart des solveurs linéaires.
• Ajout d'un nouveau problème de test données ajustées (Osborne).
• Fait quelques autres modifications mineures.

Ce qui est nouveau dans la version 2.4:

• ATTENTION Pour les versions antérieures UTILISATEURS: La taille de l'argument info (ce est-LM_INFO_SZ) a été augmentée par un pour accueillir un nouveau champ de retour (ce est-à info [9]) correspondant au nombre total de systèmes linéaires résolus dans le cadre de la minimisation. Les indices des champs précédemment retournés dans le tableau d'information restent inchangés.
• Mise en place d'un régime plus de cache-efficace pour le calcul du Hesse J approximative ^ T * J et J ^ T * e pour les petites entreprises problèmes de minimisation.
• veiller à ce que toute la mémoire de travail retenu entre invocations des solveurs linéaires est libéré lors de la cessation de routines de levmar.
• veillé à ce que les solveurs linéaires emploient la quantité minimale requise de mémoire auxiliaire, évitant occasionnelle sur-allocations.
• Mise en œuvre d'un régime boucle de déroulement pour accélérer le calcul de e = x-hx.
• Correction d'un couple de problèmes avec l'alignement de la mémoire sur les systèmes 64 bits.
• Ajout de fonctions pour le calcul du coefficient de détermination.
• Traitées avec quelques problèmes mineurs.