levmar

levmar er en implementering av Levenberg-Marquardt ikke-lineær minste kvadraters algoritmer i C / C ++.
Den lmder rutine fra Minpack, implementert i de tidlige 80-tallet ved Argonne National Lab, er kanskje den mest brukte fri gjennomføring av LM-algoritmen. lmder er skrevet i FORTRAN77 og gjennom årene har vist seg å være en pålitelig stykke programvare. Tatt i betraktning at FORTRAN rutiner kan kalles fra C / C ++, kan man lure på om motivasjonen for å skrive en versjon av LM i C. Vel, problemet er at når FORTRAN kalles fra C, bør programmerer være klar over (og i samsvar med ) flere regler om navn rulling, argument pasninger, flerdimensjonal array minne layout, linkage konvensjoner, etc, som er unaturlig forhold til vanlige C-regler. En annen grunn er at denne tilnærmingen tar for gitt at et FORTRAN kompilator for målet programmeringsmiljø er tilgjengelig, noe som kanskje ikke nødvendigvis være tilfelle. En annen grunn har å gjøre med manglende forståelse den interne driften av et FORTRAN implementering: Av og til, når det er nødvendig for å nettopp forstå hva FORTRAN koden gjør, kan visse deler av det virke uforståelig for programmerere uten noen kunnskap om FORTRAN. Automatisk FORTRAN til C oversettere (f.eks F2C) løser ikke problemet siden det produserte C-kode er ganske uleselig for "uinnvidde" mennesker. Videre dokumentasjon som beskriver matematikk hvorpå implementeringen er basert kan være uklar eller utilgjengelige. Sist men ikke minst, bør en kandidat LM implementering i C være fri og teknisk god. For eksempel er C variant av LM algoritmen presentert i "Numerical Recipes" bok (dvs. mrqmin), ikke alltid et levedyktig valg: Foruten sin blir opphavsrettsbeskyttet, er det kjent for å mangle robusthet
. For de ovennevnte grunner, har jeg utviklet levmar pakke som inkluderer C implementeringer av LM smaker som er også brukbart med C ++. levmar inkluderer doble og enkle presisjon LM implementeringer, både med analytisk og endelig differanse tilnærmes Jacobians. Den er tilgjengelig kostnadsfritt, i henhold til vilkårene i GNU General Public License. Den matematiske teorien bak ubegrenset levmar er beskrevet i detalj i kompendiet rett Metoder for ikke-lineære Least Squares Problemer ved K. Madsen, HB Nielsen og O. Tingleff, Danmarks Tekniske Universitet; Matlab implementeringer av algoritmene presentert i kompendiet er også tilgjengelig. Merk imidlertid at utformingen av minimering problem vedtatt her er litt forskjellig fra det som er beskrevet i kompendiet
funksjonens Bruk.
Levmar tilbyr flere brukercallable funksjoner adlyde følgende navnekonvensjon: Den første bokstaven (d eller e) angir dobbel eller enkel presisjon og suffikset (_der eller _dif) betegner analytisk eller omtrentlig Jacobian. Hvis den finnes, LMU, bc og BLEC komponenter innebærer lineær ligning, boks og samtidig boksen og lineære liknings begrensninger, henholdsvis. Mer spesifikt, levmar omfatter funksjonene nedenfor:
Unconstrained optimalisering
dlevmar_der (): dobbel presisjon, analytisk Jacobian
dlevmar_dif (): dobbel presisjon, endelig differanse tilnærmes jacobian
slevmar_der (): enkel presisjon, analytisk Jacobian
slevmar_dif (): enkel presisjon, endelig differanse tilnærmes Jacobian
Begrenset optimalisering
dlevmar_lec_der () : dobbel presisjon, lineære liknings begrensninger, analytisk Jacobian
dlevmar_lec_dif (): dobbel presisjon, lineære liknings begrensninger, endelig differanse tilnærmes Jacobian
slevmar_lec_der (): enkel presisjon, lineære liknings begrensninger, analytisk Jacobian
slevmar_lec_dif (): enkel presisjon, lineære liknings begrensninger, endelig differanse tilnærmes Jacobian
dlevmar_bc_der (): dobbel presisjon, boks begrensninger, analytisk Jacobian
dlevmar_bc_dif (): dobbel presisjon, boks begrensninger, finite Forskjellen tilnærmes Jacobian
slevmar_bc_der (): enkel presisjon, boks begrensninger, analytisk Jacobian
slevmar_bc_dif (): enkel presisjon, boks begrensninger, endelig differanse tilnærmes Jacobian
dlevmar_blec_der (): double presisjon, boks og lineære liknings begrensninger, analytisk Jacobian
dlevmar_blec_dif (): dobbel presisjon, boks og lineære liknings begrensninger, endelig differanse tilnærmes Jacobian
slevmar_blec_der (): enkel presisjon, boks og lineære liknings begrensninger, analytisk Jacobian
slevmar_blec_dif (): enkel presisjon, boks og lineære liknings begrensninger, endelig differanse tilnærmes Jacobian
Legg merke til at du bruker begrensede forskjeller å tilnærme Jacobian resulterer i gjentatte evalueringer av funksjonen som skal monteres. Sikte på å redusere det totale antallet av disse vurderingene, de xxxxxxx_dif funksjoner implementere sekantstrukturer tilnærmelser til Jacobian hjelp Broyden rang ett oppdateringer. Alle funksjoner løse det samme problemet, dvs. de søker parametervektor p som best beskriver (i form av L2-norm) den målinger vektor x. Mer presist, gitt en vektor funksjon f: R ^ m -> R ^ n med n> = m, beregne de ap slik at f (p) ~ = x, det vil si den firkantede normen || e || ^ 2 = | | xf (p) || ^ 2 blir minimalisert. Også boks begrensninger av skjemaet lb [i]

Hva er nytt i denne utgaven:

• Denne versjonen legger til støtte for diagonal skalering til xlevmar_bc_der (), som kan forbedre konvergens når utgangspunktet er langt fra den sanne minimizer.
• Et lineært system løser støtter parallell Cholesky dekomponering med plasma, lineær algebra biblioteket for multi-core prosessorer.
• Formløsere har blitt fikset slik at de opererer på lavere trekanter av symmetriske matriser, noe som resulterer i bedre cache ytelse.
• De CUtfør konfigurasjonsfiler for å bygge prosjektet har blitt revidert.
• Flere andre mindre endringer har blitt gjort.

Hva er nytt i versjon 2.5:

• FORSIKTIG for tidligere versjoner BRUKERE: For bedre konsistens og unngåelse av konflikter, ble navnet på levmar header fil endret fra lm.h til levmar.h; du oppdatere kildefilene tilsvarende.
• Lagt til støtte for minimering under samtidig boksen, lineære liknings og ulikhet begrensninger (se funksjoner xlevmar_bleic_der () og xlevmar_bleic_dif ()).
• Gjennomførte convenience wrappers å xlevmar_bleic_der () og xlevmar_bleic_dif () arbeider med enklere begrenset tilfeller, f.eks xlevmar_blic_der () og xlevmar_blic_dif () støtte minimering i rubrikk og lineære ulikhet begrensninger bare.
• Lagt til en lineær systemer løser basert på UDUt dekomponering (dvs. sqrt fritt Cholesky).
• Fjernet noen unødvendig minne kopiering fra de fleste lineære løsere.
• Lagt til en ny data sittende test problem (Osborne).
• Gjort noen andre mindre endringer.

Hva er nytt i versjon 2.4:

• FORSIKTIG for tidligere versjoner BRUKERE: Størrelsen på info argumentet (dvs. LM_INFO_SZ) ble økt med en for å imøtekomme en ny retur felt (dvs. info [9]) som svarer til det totale antall lineære systemer løses i løpet av minimalisering. Indeksene av tidligere returnert felt i info matrise forblir uendret.
• Gjennomført en mer cache-effektiv ordning for å beregne omtrentlig Hessere J ^ T * J og J ^ T * e for små-sized minimalisering problemer.
• Sikret at ethvert arbeidsminnet beholdes mellom besvergelser av de lineære løsere frigjøres ved opphør av levmar rutiner.
• Sikret at lineære løsere ansette minimum nødvendige mengden av hjelpe minne, unngå sporadisk over-bevilgninger.
• Gjennomført en løkke utrulling ordning for fartsovertredelse opp beregningen av e = x-hx.
• Fast et par problemer med minne justering på 64 bits systemer.
• Lagt funksjoner for beregning av koeffisienten.
• Jobbet med noen mindre problemer.