levmar

levmar er en implementering af Levenberg-Marquardt-lineær mindste kvadraters algoritmer i C / C ++.
Den lmder rutine fra Minpack, implementeret i de tidlige 80'ere på Argonne National Lab, er måske den mest udbredte fri implementering af LM algoritme. lmder er skrevet i FORTRAN77 og i årenes løb har vist sig at være en pålidelig stykke software. I betragtning af at FORTRAN rutiner kan kaldes fra C / C ++, kan man undre sig over motivationen til at skrive en version af LM i C. Nå, problemet er, at når FORTRAN kaldes fra C, skal programmøren være opmærksom på (og i overensstemmelse med ) flere regler om navn rulning, argument forbifarten, flerdimensional tabel hukommelse layout, sammenkædning konventioner mv, som er unaturlige forhold til almindelige C-regler. En anden grund er, at denne fremgangsmåde tager for givet, at en FORTRAN compiler for målet programmering miljø er tilgængelig, som måske ikke nødvendigvis være tilfældet. En anden grund har at gøre med manglende forståelse de indre funktioner af en FORTRAN implementering: lejlighedsvis, når det er nødvendigt præcist at forstå, hvad det FORTRAN kode gør, kan visse dele af det synes uforståeligt for programmører uden kendskab til FORTRAN. Automatisk FORTRAN til C-oversættere (f.eks F2C) ikke løser problemet, da den producerede C-kode er temmelig ulæselig for "uindviede" mennesker. Desuden dokumentation, der beskriver den matematik, hvorpå implementeringen bygger måske uklar eller utilgængelige. Sidst men ikke mindst, skal en kandidat LM implementering i C være fri og teknisk forsvarlig. For eksempel C variant af LM algoritmen præsenteret i "Numerical Recipes" bog (dvs. mrqmin), er ikke altid en levedygtig valg: Udover den blev ophavsretligt beskyttet, er det ry for at mangle robusthed
. Af ovennævnte grunde har jeg udviklet levmar pakken, som indeholder C-implementeringer af LM varianter, der også kan bruges med C ++. levmar inkluderer dobbelt-og enkeltværelser præcision LM implementeringer, både med analytiske og finite forskel tilnærmet Jacobianter. Det er gratis, under betingelserne i GNU General Public License. Den matematiske teori bag ubegrænset levmar er beskrevet i detaljer i lecture notes titlen Metoder til ikke-lineære mindste kvadraters metode Problemer ved K. Madsen, HB Nielsen og O. Tingleff, Tekniske Universitet Danmark; Matlab implementeringer af de algoritmer, der præsenteres i forelæsningsnoter er også tilgængelige. Bemærk dog, at formuleringen af ​​minimering problem vedtaget her er lidt anderledes end beskrevet i forelæsningsnoter
Funktion s Anvendelse:.
Levmar tilbyder flere bruger-konverterbare funktioner adlyde den følgende navngivning: Det første bogstav (d eller s) angiver dobbelt eller enkelt præcision og endelsen (_der eller _dif) betegner analytisk eller omtrentlige Jacobian. Hvis der er, LEC, bc og BLEC komponenter indebærer lineær ligning, kasse og samtidig kasse og lineær ligning begrænsninger hhv. Mere specifikt levmar indeholder nedenstående funktioner:
ubegrænset optimering
dlevmar_der (): dobbelt præcision, analytisk Jacobi
dlevmar_dif (): dobbelt præcision, finite forskel tilnærmes Jacobi
slevmar_der (): enkelt præcision, analytisk Jacobi
slevmar_dif (): enkelt præcision, finite forskel tilnærmet Jacobi
Constrained optimering
dlevmar_lec_der () : dobbelt præcision, lineær ligning begrænsninger, analytisk Jacobi
dlevmar_lec_dif (): dobbelt præcision, lineær ligning begrænsninger, finite forskel tilnærmet Jacobi
slevmar_lec_der (): enkelt præcision, lineær ligning begrænsninger, analytisk Jacobian
slevmar_lec_dif (): enkelt præcision, lineær ligning begrænsninger, tilnærmes finite forskel Jacobi
dlevmar_bc_der (): dobbelt præcision, box begrænsninger, analytisk Jacobi
dlevmar_bc_dif (): dobbelt præcision, box begrænsninger, finite forskel tilnærmet Jacobi
slevmar_bc_der (): enkelt præcision, box begrænsninger, analytisk Jacobi
slevmar_bc_dif (): enkelt præcision, box begrænsninger, finite forskel tilnærmet Jacobi
dlevmar_blec_der (): double præcision, kasse og lineær ligning begrænsninger, analytisk Jacobi
dlevmar_blec_dif (): dobbelt præcision, kasse og lineær ligning begrænsninger, finite forskel tilnærmet Jacobi
slevmar_blec_der (): enkelt præcision, box & lineær ligning begrænsninger, analytisk Jacobian
slevmar_blec_dif (): enkelt præcision, box & lineær ligning begrænsninger, finite forskel tilnærmet Jacobi
Bemærk, at ved hjælp af finite forskelle at tilnærme Jacobi resultater i gentagne evalueringer af den funktion, der skal monteres. Med sigte på at reducere det samlede antal af disse evalueringer, xxxxxxx_dif funktioner implementere sekant tilnærmelser til Jacobi ved hjælp Broyden rang én opdateringer. Alle funktioner løser det samme problem, nemlig de søger parameteren vektor p, der bedst beskriver (i form af L2 normen) den målinger vektor x. Mere præcist givet en vektor funktion f: R ^ m -> R ^ n med n> = m, de beregne ap sådan at f (p) ~ = x, dvs. kvadrerede normen || e || ^ 2 = | | xf (p) || ^ 2 minimeres. Også box begrænsninger af formen lb [i]

Hvad er nyt i denne udgivelse:

• Denne version tilføjer understøttelse for diagonal skalering til xlevmar_bc_der (), som kan forbedre konvergensen når udgangspunktet er langt fra den sande Minimizer.
• En lineær systemer solver understøtter parallel Cholesky nedbrydning med Plasma, den lineære algebra bibliotek for multi-core processorer.
• Lineære solvers er fastsat således, at de opererer på lavere trekanter af symmetriske matricer, hvilket resulterer i bedre cache resultater.
• CForetag konfigurationsfiler til opbygning af projektet er blevet revideret.
• Flere andre mindre ændringer er foretaget.

Hvad er nyt i version 2.5:

• FORSIGTIG til tidligere versioner BRUGERE: For bedre sammenhæng og undgåelse af konflikter, blev navnet på levmar overskrift fil ændret fra lm.h til levmar.h; Husk at opdatere dine kildefiler i overensstemmelse hermed.
• Tilføjet understøttelse af minimering under samtidig kasse, lineære ligning og ulighed begrænsninger (se funktioner xlevmar_bleic_der () & xlevmar_bleic_dif ()).
• Gennemførte convenience indpakning til xlevmar_bleic_der () & xlevmar_bleic_dif () beskæftiger sig med enklere begrænsede tilfælde, f.eks xlevmar_blic_der () & xlevmar_blic_dif () støtte minimering under boksen og lineære ulighed begrænsninger alene.
• Tilføjet en lineær systemer Solver baseret på UDUt nedbrydning (dvs. sqrt-fri Cholesky).
• Fjernet nogle unødvendige hukommelse kopiering fra de fleste lineære løsere.
• Tilføjet en ny data-montering test problem (Osborne).
• lavet et par andre mindre ændringer.

Hvad er nyt i version 2.4:

• FORSIGTIG til tidligere versioner BRUGERE: Størrelsen af ​​info argumentet (dvs. LM_INFO_SZ) blev forhøjet med en til at modtage en ny tilbagevenden felt (dvs. info [9]), som svarer til det samlede antal af lineære systemer løses under minimering. Indeksene for tidligere returnerede felter i info-array forbliver uændrede.
• gennemført en mere cache-effektive ordning til beregning af omtrentlige hessiske J ^ T * J og J ^ T * e for små minimering problemer.
• sikres, at eventuelle arbejdshukommelsen bevares mellem kald af de lineære solvers frigives ved afslutningen af ​​levmar rutiner.
• Sikret at lineære løsere ansætte minimum krævede mængde ekstra hukommelse, undgå lejlighedsvis over-tildelinger.
• implementeret en løkke udrulning ordning til at fremskynde beregningen af ​​e = x-HX.
• Fast et par problemer med hukommelse tilpasning på 64 bit systemer.
• Tilføjet funktioner til beregning af determinationskoefficienten.
• Behandlet med et par mindre problemer.