Optimering (matematik)

Optimering er en matematisk metode der ved brug af differentialregning kan finde den optimale løsning på et problem. Det kunne eksempelvis omhandle dimensionerne på et produkt i relation til forbruget af materiale.

Optimering

I matematikken refererer ordet optimering til studiet af problemer hvor man søger at minimere eller maksimere en funktion som er defineret for alle reelle tal eller en delmængde heraf ved systematisk at vælge værdier af reelle eller heltalsværdier fra den opgivne definitionsmængde.

Opgaven kan opstilles på følgende måde:

Givet: en funktion f : A -> R hvor A er et givet sæt, og hvor funktionen altså afbilder dette sæt på de reelle tals mængde.

Minimumspunkt søges: Et element f(x₀) in A således at

f(x₀) ≤ f( x) for alle x in A

eller ved maksimering: f(x₀) ≥ f(x) for alle x in A

Note 1: En sådan formulering kaldes et optimeringsproblem (eng: optimization problem or a mathematical programming problem - dette er omtalt på den engelske wikipedia som “a term not directly related to computer programming, but still in use for example in linear programming - see history below”). Mange praktiske og teoretiske problemer kan modelleres efter denne generelle model.

Note 2: Den engelske wikipedia har en meget stor artikel om definitionsmængden for funktionen f der skal optimeres, se ovenfor. Man anvender betegnelsen A med bemærkningen at A er et sæt - her følger en forklaring på hvad dette betyder.

Typisk er A et subsæt af det euclidske rum R^n, ofte beskrevet med nogle nærmere beskrevne begrænsninger i form af lignininger eller uligheder som medlemmerne i A skal opfylde.

Elementerne i A kaldes for mulige løsninger (eng: feasible solutions). Funktionen f kaldes en formålsfunktion (eng: objective function), eller en omkostningsfunktion (eng: cost function).

En mulig løsning er en løsning de minimerer (eller maksimerer, afhængigt af målet) funktionen. En sådan fundet løsning kaldes for en optimal løsning.

Definitionsmængden A af f kaldes for søgerummet (eng: search space) og elementerne i A kaldes for mulige løsninger (eng: candidate solutions ).

Generelt gælder, at når funktionen f ikke indeholder et enkelt lokalt ekstremum i den region, hvor en mulig løsning ønskes fundet, kan der opstå problemer:

Hvis der eksisterer adskillige lokale minima og maxima, hvor et lokalt minimum x* er defineret som et punkt for hvilket der eksisterer et δ > 0 således at for alle x om hvilke det gælder

$\|\mathbf {x} -\mathbf {x} ^{*}\|\leq \delta$;

vil udtrykket

$f(\mathbf {x} ^{*})\leq f(\mathbf {x} )$

være sandt, det vil sige, i en region omkring x* vil alle funktionsværdier være større eller lig med værdien i det pågældende punkt. Lokale maxima er defineret på tilsvarende måde.

Et stort antal algoritmer, som er foreslået til at løse sådanne ikke-entydige optimeringer (eng: non-convex problems ) – og dette inkluderer størstedelen af de kommercielt tilgængelige optimeringsalgoritmer – er ikke i stand til at foretage en skelnen (eng: distinction) mellem lokale optimale løsninger (lokale optima) og løsninger som vitterligt er extreme i den region, der er valgt, dvs. ekstremumspunkter der gælder for hele A. De fleste algoritmer vil opfatte en funden lokalt optimal løsning som om det var en optimal løsning for hele A, dvs. programmet indser ikke, at dets løsning ikke er den rigtige. Den gren af anvendt matematik og numerisk analyse der beskæftiger sig med udvikling af deterministiske algoritmer som er i stand til at garantere konvergens indenfor en endelig tid (dvs. som er i stand til at finde den korrekte løsning og hvor man er i stand til at give et bud på, hvor lang tid programmet skal bruge på det) kaldes for global optimering.

Kildehenvisning

• Den engelsksprogede Wikipedia
• sciencenet.dk