MINOS (optimeringsprogram)

MINOS är ett Fortran mjukvarupaket för att lösa linjära och olinjära matematiska optimeringsproblem . MINOS (Modular In-core Nolinear Optimization System) kan användas för linjär programmering, kvadratisk programmering och mer allmänna objektiva funktioner och begränsningar, och för att hitta en möjlig punkt för en uppsättning linjära eller olinjära likheter och ojämlikheter.

MINOS utvecklades först av Bruce Murtagh och Michael Saunders , mestadels vid Systems Optimization Laboratory vid Department of Operations Research vid Stanford University. 1985 tilldelades Saunders det inledande Orchard-Hays-priset av Mathematical Programming Society (nu Mathematical Optimization Society ) för sitt arbete med MINOS. Trots att paketet är en av de första begränsade optimeringslösarna för allmänt bruk som dykt upp, är paketet fortfarande flitigt använt. MINOS stöds i modelleringssystemen AIMMS , AMPL , APMonitor , GAMS och TOMLAB . Dessutom är det fortfarande en av de mest använda lösarna på NEOS-servern och i GAMS .

Drift

Idealiskt bör användaren tillhandahålla gradienter för de olinjära funktionerna. (Detta är automatiskt i de flesta modelleringssystem som nämns ovan.) Om några eller alla gradienter inte tillhandahålls, kommer MINOS att approximera de saknade med ändliga skillnader, men detta kan vara långsamt och mindre tillförlitligt. Om objektivfunktionen är konvex och begränsningarna är linjära kommer den erhållna lösningen att vara en global minimering. Annars kan den erhållna lösningen vara en lokal minimerare.

används en tvåfasig primal simplexmetod . Den första fasen minimerar summan av oförmögenheter. För problem med linjära begränsningar och ett icke-linjärt mål används en reducerad gradientmetod. En quasi-Newton approximation till den reducerade hessian upprätthålls för att få sökriktningar. Metoden är mest effektiv när många begränsningar eller gränser är aktiva vid lösningen.

För problem med icke-linjära begränsningar används en linjärt begränsad lagrangisk metod. Detta involverar en sekvens av större iterationer, som var och en löser (kanske ungefär) ett linjärt begränsat delproblem. Delproblemmålet är en förstärkt Lagrangian , och delproblembegränsningarna är linjäriseringar av de olinjära begränsningarna vid den aktuella punkten.

MINOS är avsedd för stora glesa problem. Det finns ingen fast gräns för problemets storlek. De flesta fungerande lagringsutrymmen finns i en dubbelprecisionsuppsättning (som bör vara tillräckligt stor). Källkoden är lämplig för alla vetenskapliga maskiner med en Fortran-kompilator.

Vidare läsning

• BA Murtagh, MA Saunders (1982). "En projicerad lagrangisk algoritm och dess implementering för glesa olinjära begränsningar" ( PDF) . Matematisk programmering . 16 :84–117.

externa länkar

• Systems Optimization Laboratory, Stanford University Systems Optimization Laboratory (SOL).
• MINOS 5.5 - Beskrivning - Distributörer av programvaran.