Optimumigo (matematiko)

Article on other languages:

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

En matematiko, la termino optimumigo signifas la studon de problemoj, en kiuj oni celas minimumigi aŭ maksimumigi reelan funkcion per tio, sisteme elekti la valorojn de reelaj aŭ entjeraj variabloj el permesata aro. Tia problemo prezenteblas per la formo

Donita:   funkcio f : A \to R el iu aro A al la reelaj nombroj
Trovenda:   ero x0 en A tia, ke f(x0) ≤ f(x) por ĉiuj x en A ("minimumigo") aŭ tia, ke f(x0) ≥ f(x) por ĉiuj x en A ("maksimumigo").

Tia formulaĵo nomiĝas optimumiga problemo aŭ matematika problemo (termino ne rekte rilatanta al komputila programado, sed ankoraŭ uzata, ekzemple por lineara programado - vidu historion pli sube). Multaj real-mondaj kaj teoriaj problemoj modeleblas en tiu ĝenerala kadro.

Tipe, A estas iu subaro de la eŭklida spaco Rn, ofte specifigita per aro de limigoj, egalecoj aŭ neegalaĵoj kiujn la membroj de A devas kontentigi. La eroj de A estas nomitaj fareblaj solvoj. La funkcio f estas nomita objektiva funkcio, aŭ kosta funkcio. Farebla solvaĵo, kiu minimumigas (aŭ maksimumigas, se tio estas la celo) la objektivan funkcion estas nomita optimala solvo.

La domajno A de f estas nomita la serĉo-spaco, dum la eroj de A estas nomitaj kandidataj solvoj aŭ fareblaj solvaĵoj.

Ĝenerale, tie estos kelkaj lokaj minimumoj kaj maksimumoj, kie loka minimumo x* estas difinita kiel punkto tia, ke por iu δ > 0 kaj ĉiuj x tia, ke

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

la formulo

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

validas; tio estas por diri, sur iu regiono ĉirkaŭ x* ĉiuj de la funkciaj valoroj estas pli grandaj ol, aŭ egalaj al, la valoro je tiu punkto. Lokaj maksimumoj estas simile difinitaj.

Ĝenerale, estas facile trovi lokajn minimumojn — aldonaj faktoj pri la problemo (ekzemple scio de tio ke la funkcio estas konveksa) estas postulitaj por certiĝi, ke la solvo fundamente estas malloka minimumo.

Granda kvanto da algoritmoj proponitaj por solvi ne-konveksajn problemojn — inkluzive de la plejmulto de komence haveblaj solviloj — ne kapablas fari distingon inter loke optimumaj solvoj kaj rigore optimumaj solvoj, kaj traktas la antaŭajn efektivajn solvojn por la originala problemo. La subfako de aplikata matmatiko kaj numera analizo kiu sin koncernas kun la evoluigo de determinismaj algoritmoj kapablaj certigi konverĝon en finia tempo al la efektiva optimuma solvo de ne-konveksa problemo nomiĝas globa optimumigo (malloka optimumigo).

Enhavo

Notacio (skribmaniero)

Problemoj de optimumigo estas ofte esprimitaj per speciala notacio. Jen kelkaj ekzemploj:

\min_{x\in\mathbb R}\; x^2 + 1

Tio celas la minimuman valoron por la objektiva funkcio x2 + 1, kie x gamas super la reelaj nombroj R. La minimuma valoro en ĉi tiu kazo estas 1, okazanta je x = 0.

\max_{x\in\mathbb R}\; 2x

Tio celas la maksimuman valoron por la objektiva funkcio 2x, kie x gamas super la reelaj nombroj. En tiu kazo, estas nenia tia maksimumo ĉar la objektiva funkcio estas nebarita, do la respondo estas "malfinio" aŭ "nedefinita".

\operatorname{argmin}_{x\in[-\infty,-1]}\; x^2 + 1

Tio celas la valoro(j)n de x en la intervalo [−∞, −1] kiu(j) minimumigas la objektivan funkcion x2 + 1. (La efektivaa minimuma valoro de tiu funkcio ne gravas.) En ĉi tiu kazo, la respondo estas x = −1.

\operatorname{argmax}_{x\in[-5,5],\;y\in\mathbb R}\; x\cdot\cos(y)

Tio celas la (x, y) paro(j)n kiu(j) maksimumigas la valoron de la objektiva funkciox·cos(y), kun la aldonita limigo, ke x kuŝas en la intervalo [−5, 5]. (Denove, la reala maksimuma valoro de la esprimo ne gravas.) En tiu kazo, la solvoj estas la paroj de la formoj (5, 2πk) kaj (−5, (2k + 1)π), kie k gamas super ĉiuj entjeroj.

Ĉefaj subkampoj

  • Lineara programado studas la kazon en kiu la objektiva funkcio f estas lineara kaj la aro A estas specifigita uzante nur linearajn egalecojn kaj neegalaĵojn. Tia aro nomiĝas poliadro aŭ politopo se ĝi estas barita.
  • Kvadrata programado permesas al la objektiva funkcio havi kvadratajn termojn, dum la aro A devas esti specifigita per linearaj egalecoj kaj neegalaĵoj.
  • Nelinearaj programadaj studas la ĝeneralan kazon en kiu la objektiva funkcio aŭ la limigoj aŭ ambaŭ el ili enhavas nelinearajn partojn.
  • Konveksa programado studas la kazon kie la objektiva funkcio estas konveksa kaj la limigoj, se ili ekzistas, formas konveksan aron. Tio rigardeblas kiel specifa kazo de neliniara programado aŭ kiel ĝeneraligo de liniara aŭ konveksa kvadrata programado.
  • Fortika programado estas, simile al stokasta programado, provo kapti necertecon en la datumoj subkuŝantaj la optimumigan problemon. Tio ne faratas per uzado de hazardaj variabloj, sed anstataŭe, la problemon oni solvas per tio atenti malĝustaĵojn en la enfluaj datumoj.
  • Dinamikaj programadaj studas la kazon en kiu la optimumiga strategio baziĝas sur diserigo de la problemo en pli malgrandajn subproblemojn.
  • Kombina optimumigo koncerniĝas kun problemoj kie la aro de fareblaj solvaĵoj estas diskreta aŭ povas reduktiĝi al diskreta aro.
  • Disjunkcia programado uziĝas kie almenaŭ unu limigo kontentigendas, sed ne ĉiuj. Ĝi aparte utilas en la verkado de horaroj.

Teknikoj

Por dufoje-diferencialeblaj funkcioj, nelimigitaj problemoj solveblas per trovado de la punktoj kie la gradiento de la objektiva funkcio estas nulo (tio estas, la stabilaj punktoj) kaj uzado de la matrico de Hessian por klasifiki la tipon de ĉiu punkto. Se la matrico de Hessian estas pozitive difinita matrico, la punkto estas loka minimumo, se negativa difinita, loka maksimumo, kaj se nedefinita ĝi estas ia selo-punkto.

Oni povas trovi la stabilajn punktojn per tio stari ĉe konjekto por stabila punkto, kaj tiam ripeti al ĝi per uzado de la jenaj metodoj. Tamen, la ekzisto de derivativoj ne ĉiam certas kaj multajn metodojn oni elpensis por apartaj situacioj. La bazaj klasoj de metodoj, bazitaj sur la glateco de la objektiva funkcio, estas:

  • Kombinatoraj metodoj
  • Senderivativaj metodoj
  • Unuaordaj metodoj
  • Duaordaj metodoj

Efektivaj metodoj el inter la ĉi-supraj kategorioj inkluzivas:

Se la objektiva funkcio estus konveksa super la regiono de intereso, tiam ĉiu loka minimumo ankaŭ estus malloka minimumo. Ekzistas fortikaj, rapidaj ciferecaj teknikoj por optimumigi duoble diferencialeblajn konveksajn funkciojn.

Limigitaj problemoj ofte konverteblas en nelimigitajn problemojn per helpo de multiplikantoj de Lagrange.

Jen kelkaj aliaj popularaj metodoj:

Utiloj

Problemoj en solida dinamiko ofte postulas programadajn teknikojn, ĉar oni povas rigardi solidan dinamikon provanta solvi ordinara diferenciala ekvacio sur limigo (dukto); la limigoj estas diversajn nelinearajn geometriajn limigojn tiajn, kiaj "ĉi tiuj du punktoj devas ĉiam koincidi", "ĉi tiu surfaco devas ne penetri iun ajn alian", aŭ "ĉi tiu punkto devas ĉiam kuŝi ie sur tiu kurbo". Ankaŭe, la problemo komputi kontaktajn fortojn fareblas per tio solvi linearan komplementecan problemon, kiu ankaŭ rigardeblas kiel (en:"QP") (kvadrata programada problemo).

Multaj dizajno-problemoj esprimeblas ankaŭ kiel optimumigaj programoj. Tiu apliko estas nomata kiel dizajna optimumigo. Unu ĵusa kaj kreskanta subaro de ĉi tiu kampo estas multfaka dizajna optimumigo, kio, dum ĝi utilas en multaj problemoj, jam aparte estas aplikata al problemoj de aerokosma flugadika inĝenierado.

Ĉefskola ekonomiko ankaŭ grave subtenas sin sur matematika programado. Klientoj kaj firmaoj estas atendataj maksimumigi sian profiton. Ankaŭe, agentojn oni atendas esti risk-evitemaj, per tio volantaj minimumigi kian ajn riskon sperteblan. Ankaŭ prezoj de havaĵoj klarigeblas per uzado de optimumigo, kvankam la subkuŝanta teorio estas pli komplika ol simpla optimigo de utilo aŭ profito. Ankaŭ komerc-teorio uzas optimigadon por klarigi komercajn aranĝojn inter landoj.

Alia kampo kiu amplekse uzas optimumigajn teknikojn estas operaciesploro.

Historio

La unua optimumiga teĥniko, konata kiel plejkruta descendo', datiĝas de Gauss. Historie, la unua termino prezentita estis lineara programado, kiu estis inventita de Georgo Dantzig en la 1940-aj jaroj. La termino programado en ĉi tiu ĉirkaŭteksto ne signifas komputilan programadon,(kvankam komputiloj estas nuntempe amplekse uzataj por solvi matematikajn programojn). Anstataŭe, la termino originas en la uzo de programo far la Usonaj militservoj por nomi proponitan trejnadajn kaj loĝistikajn horarojn, kiuj estis la problemoj, kiujn tiutempe studis Dantzig. (Aldone, pli malfrue, la uzado de la termino "programado" estis evidente utila por ricevadi registaran fonduson, ĉar ĝin oni asociis kun esplorkampoj de alta-teknologio, kiuj estis konsiderataj gravaj.)

Aliaj gravaj matematikistoj en la optimumiga kampo inkluzivas:

Vidu ankaŭ jenon

Referencoj

Eksteraj ligoj

Modeligaj lingvoj:

Solviloj:

program-bibliotekoj:

Elŝutita el "http://eo.wikipedia.org/wiki/Optimumigo_(matematiko)"

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

Giant Panda

Mercedes Car
James Bond Guide
This site monitored by SitePinger.net