Optimeringsmetoder

Optimeringsmetoder avser tekniker för att hitta bästa möjliga värde av en objektiv funktion under givna begränsningar. En optimeringsuppgift består oftast av en målfunktion som ska minimeras eller maximeras, och av ett eller flera villkor som beskriver vad som är tillåtet.

Problemet kan vara kontinuerligt eller diskret, och kan vara linjärt, icke-linjärt eller blandat. Begränsningar kan vara av typen lika med eller ojämlikheter, och ibland heltalskrav som gör problemet till ett heltalsprogram.

Linjär programmering utgör en central del av optimering. Här används metoder som simplex och inre punkt-metoder för att hitta optimala lösningar när både målfunktionen och restriktionerna är linjära. Icke-linjär programmering används gradientbaserade metoder som gradientnedstigning och Newtons metod, samt mer avancerade tekniker som quasi‑Newton och SQP (sequential quadratic programming) för att hantera restriktioner. För problem med många variabler eller speciella strukturer används ofta specialiserade metoder.

Konvexa problem kännetecknas av att varje lokal optima också är globalt, vilket gör att konvexa optimeringsproblem ofta kan lösas effektivt och med garantier om konvergens. Om problemet är icke-konvext finns risk för flera lokala optima och svårare garanti för global lösning.

Hurtiga och robusta lösningar uppnås ofta med en kombination av exakta tekniker och heuristiska metoder. Heuristiska och metaheuristiska metoder som genetiska algoritmer, simulated annealing och tabu-sökning används framför allt när problemet är icke-konvext, högdimensionellt eller innehåller diskreta beslut.

Användningar och verktyg: optimeringsmetoder används inom operationsforskning, industriell ekonomi, logistik, maskininlärning och teknik. Verkygslösare och bibliotek som CPLEX, Gurobi och MOSEK, samt open source-alternativ som COIN-OR och IPOPT, stödjer ofta flera av de nämnda metoderna.