Optimering (matematik)

Poll without page-refresh

Article on other languages:

	del.icio.us
	Digg
	Furl
	Reddit
	Rojo
	Add to OnlyWire

Formatering
Denne artikel bør formateres (med afsnitsinddeling, interne links o.l.) som det anbefales i Wikipedias retningslinjer

Optimering er en matematisk metode til bestemmelse af den optimale løsning på en særlig type af problemer. Det kunne eksempelvis dreje sig om at minimere materialeforbruget ved produktion af en beholder: Hvis målet er at fremstille en metaldåse i form af en hul cylinder med given vægtykkelse, kan man for fastholdt volumen spørge sig hvorledes dåsen skal dimensioneres for at gøre metalforbruget mindst muligt. En fysisk overvejelse viser at det gælder om at minimere dåsens overfladeareal, og ved optimering indses at målet nås når dåsens højde er lig dåsens diameter, dvs. når dåsens form er så tæt på kuglens som muligt.

Matematisk grundlag

I matematikken refererer ordet optimering til studiet af problemer hvor man søger at minimere eller maksimere en funktion. Det matematiske grundlag for optimering er differentialregning.

Hvis funktionen er defineret på en delmængde af de reelle tal og antager reelle værdier, kan opgaven formuleres på følgende måde: Givet en funktion $f: A \rightarrow \mathbf{R}$ hvor $A \subset \mathbf{R}$ søges et minimumspunkt eller et maksimumspunkt, dvs. et tal $x_0 \in A$ som opfylder at $f(x) \geq f(x_0)$ henholdsvis $f(x) \leq f(x_0)$ for alle $x \in A$ . Et sådant punkt $x 0$ kaldes et ekstremumspunkt, og den tilsvarende funktionsværdi $f (x 0)$ , som altså er et minimum eller et maksimum, kaldes et ekstremum. Hvis $f(x) \geq f(x_0)$ henholdsvis $f(x) \leq f(x_0)$ for alle $x$ i funktionens definitionsmængde, siges ekstremumspunktet $x 0$ at være globalt.

Hvis funktionen er kontinuert og defineret på et begrænset og lukket interval, antager funktionen ifølge en af den matematiske analyses centrale sætninger såvel maksimum som minimum i intervallet.

Hvis funktionen er differentiabel, og $x 0$ er et lokalt ekstremumspunkt, dvs. der findes et åbent interval indeholdende $x 0$ , så $f(x) \geq f(x_0)$ henholdsvis $f(x) \leq f(x_0)$ for alle $x$ i intervallet, da er funktionens differentialkvotient nul i punktet: $f'(x 0) = 0$ . Det betyder at de mulige ekstremumspunkter for $f$ skal søges blandt de $x$ -værdier som opfylder $f'(x) = 0$ .

Noter

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 en mængde - her følger en forklaring på hvad dette betyder.

Typisk er $A$ en delmængde af det euklidske rum $\mathbf{R}^n$ , ofte beskrevet med nogle restriktioner i form af ligninger eller uligheder som elementerne 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 for 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 entydigt bestemt, lokalt ekstremum i det område 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 et område i nærheden af 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 det valgte område, 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

Hentet fra "http://da.wikipedia.org/wiki/Optimering_(matematik)"

This article is from Wikipedia. All text is available under the terms of the GNU Free Documentation License.

Giant Panda

Mercedes Car

This site monitored by SitePinger.net