levmar

levmar är en implementation av Levenberg-Marquardt olinjär minsta kvadrat algoritmer i C / C ++.

Lmder rutin från Minpack, genomföras i början av 80-talet på Argonne National Lab, är kanske den mest använda fri implementation av LM-algoritmen. lmder är skrivet i Fortran77 och genom åren har visat sig vara en pålitlig mjukvara. Med tanke på att FORTRAN rutiner kan anropas från C / C ++, kan man undra om motivation för att skriva en version av LM i C. Jo, problemet är att när FORTRAN anropas från C, bör programmeraren vara medveten om (och uppfyller ) flera regler om namn mangling, argument passerar, flerdimensionell array minne layout, länk konventioner, etc, som är onaturligt jämfört med vanliga C regler. En andra anledning är att detta tillvägagångssätt tar för givet att en FORTRAN kompilator för målet programmeringsmiljön är tillgänglig, som kanske inte nödvändigtvis vara fallet. Ett annat skäl har att göra med oförmåga att förstå det inre arbetet i ett FORTRAN genomförande: Ibland, när det är nödvändigt att exakt förstå vad FORTRAN kod gör, kanske vissa delar av det tyckas obegripligt för programmerare utan någon kunskap om FORTRAN. Automatisk FORTRAN till C översättare (t.ex. f2c) löser inte problemet eftersom det producerade C-koden är ganska oläsligt att "oinvigda" människor. Dessutom dokumentation som beskriver matematiken på vilka genomförandet bygger kanske otydliga eller otillgängliga. Sist men inte minst bör en kandidat LM genomförande i C vara fri och tekniskt fungerande. Till exempel är C-varianten av LM algoritmen presenteras i "Numerical Recipes" bok (dvs mrqmin), inte alltid ett lönsamt val: Förutom det att den upphovsrättsskyddade, det sägs sakna robusthet

. Av ovanstående skäl, har jag utvecklat levmar paket som inkluderar C implementeringar av LM smaker som också kan användas med C ++. levmar inkluderar dubbel och singel precision LM implementeringar, både med analytisk och finit differens approximeras Jacobians. Det är kostnadsfritt, enligt villkoren i GNU General Public License. Den matematiska teorin bakom unconstrained levmar beskrivs i detalj i föreläsningsanteckningar berättigade Metoder för olinjär minsta kvadratproblem, genom K. Madsen, HB Nielsen och O. Tingleff, Danmarks tekniska universitet; Matlab implementeringar av algoritmerna som presenteras i föreläsningsanteckningar finns också. Observera dock att formuleringen av minimeringsproblem antagits här är något annorlunda än den som beskrivs i föreläsningsanteckningar

Funktion s Användning:.

Levmar erbjuder flera användar inlösbara funktioner lyda Följande namnkonvention: Den första bokstaven (d eller s) anger dubbel eller enkel precision och suffixet (_der eller _dif) betecknar analytisk eller ungefärlig Jacobian. Om det finns, LEC, bc och BLEC komponenter innebär linjär ekvation, box och samtidig rutan och linjära ekvations begränsningar, respektive. Närmare bestämt inbegriper levmar nedanstående funktioner:

Unconstrained optimering

dlevmar_der (): dubbel precision, analytisk Jacobian
dlevmar_dif (): dubbel precision, finit differens approximeras Jacobian
slevmar_der (): enkel precision, analytisk Jacobian
slevmar_dif (): enkel precision, ändlig skillnad approximeras Jacobian

Begränsad optimering

dlevmar_lec_der () : dubbel precision, linjära ekvations begränsningar, analytisk Jacobian
dlevmar_lec_dif (): dubbel precision, linjära ekvations begränsningar, ändlig skillnad approximeras Jacobian
slevmar_lec_der (): enkel precision, linjära ekvations begränsningar, analytisk Jacobian
slevmar_lec_dif (): enkel precision, linjära ekvations begränsningar, ändlig skillnad approximeras Jacobian

dlevmar_bc_der (): dubbel precision, box begränsningar, analytisk Jacobian
dlevmar_bc_dif (): dubbel precision, box begränsningar, ändliga Skillnaden approximeras Jacobian
slevmar_bc_der (): enkel precision, box begränsningar, analytisk Jacobian
slevmar_bc_dif (): enkel precision, box begränsningar, ändlig skillnad approximeras Jacobian

dlevmar_blec_der (): dubbel precision, box & linjära ekvations begränsningar, analytisk Jacobian
dlevmar_blec_dif (): dubbel precision, box & linjära ekvations begränsningar, ändlig skillnad approximeras Jacobian
slevmar_blec_der (): enkel precision, box & linjära ekvations begränsningar, analytisk Jacobian
slevmar_blec_dif (): enkel precision, box & linjära ekvations begränsningar, ändlig skillnad approximeras Jacobian

märke till att med hjälp av finita differenser att närma Jacobian resultat i repetitiva utvärderingar av den funktion som ska monteras. Syftar till att minska det totala antalet dessa utvärderingar, xxxxxxx_dif funktionerna genomför sekant approximationer till Jacobian använder Broyden rang en uppdatering. Alla funktioner lösa samma problem, dvs de söker parametervektorn p som bäst beskriver (i termer av L2 norm) den mätningar vektorn x. Mer exakt, givet en vektor funktion f: R ^ m -> R ^ n med n> = m, de beräkna ap så att f (p) ~ = x, dvs kvadrat normen || e || ^ 2 = | | xf (p) || ^ 2 minimeras. Även box begränsningar formen lb [i]

Vad är nytt i den här versionen:

• Denna version lägger till stöd för diagonal skalning till xlevmar_bc_der (), vilket kan förbättra konvergensen när utgångspunkten är långt från den sanna minimizer.
• En linjär system solver stöder parallell Cholesky nedbrytning med PLASMA, den linjära algebra biblioteket för multi-core processorer.
• Linjär lösare har fastställts så att de fungerar på lägre trianglar av symmetriska matriser, vilket resulterar i bättre cache prestanda.
• De CGör konfigurationsfiler för att bygga projektet har reviderats.
• Flera andra mindre ändringar har gjorts.

Vad är nytt i version 2.5:

• VARNING för tidigare versioner ANVÄNDARE: För bättre konsekvens och undvikande av konflikter, var namnet på levmar header fil ändrats från lm.h att levmar.h; vänligen uppdatera dina källfiler därefter.
• Stöd för minimering under samtidig box, linjära ekvations och olikhetsbivillkor (se funktioner xlevmar_bleic_der () & xlevmar_bleic_dif ()).
• Genomförda bekvämlighets omslag till xlevmar_bleic_der () & xlevmar_bleic_dif () behandlar enklare begränsade fall, t.ex. xlevmar_blic_der () & xlevmar_blic_dif () supportminimering i rutan och linjära olikhetsbivillkor bara.
• Inkom en linjär system solver baserad på Udut nedbrytning (dvs sqrt fria Cholesky).
• Tog bort några onödiga minnes kopiering från de flesta linjära lösare.
• Lade till en ny datapassande provproblem (Osborne).
• Made några andra mindre förändringar.

Vad är nytt i version 2.4:

• VARNING för tidigare versioner ANVÄNDARE: Storleken på info argumentet (dvs, LM_INFO_SZ) ökades med en för att passa en ny returfält (dvs info [9]) som motsvarar det totala antalet linjära system lösas under minimeringen. Indexen för tidigare return fält i info array förblir oförändrade.
• Genomfört en mer cache effektivt system för beräkning av ungefärliga hessiska J ^ T * J och J ^ T * e för små minimeringsproblem.
• Sett till att alla arbetsminnet bevaras mellan anrop av de linjära lösare släpps vid uppsägning av levmar rutiner.
• Sett till att linjära lösare anställa minsta beloppet av extraminne, undvika tillfällig över anslag.
• Genomfört en slinga avrullning system för att påskynda beräkning av e = x-hx.
• Fixat ett par frågor med minnes inriktning på 64 bitars system.
• Inkom funktioner för beräkning av förklaringsgraden.
• Behandlas med några mindre frågor.