eo eo en eo eo eo eo es eo eo eo eo da eo eo hbs_lat fr fr en eo uz eo eo eo eo eo eo eo lt eo eo eo eo de es eo eo eo eo eo sv ur eo eo eo eo es eo eo eo eo eo eo eo eo tr eo eo eo eo eo eo eo eo eo eo eo eo eo eo
Redaktado de Optimumigo (matematiko) - Vikipedio
Jump to navigation Jump to search
Averto: vi ne estas ensalutinta. Via IP-adreso enregistriĝos en la redakta historio de tiu ĉi paĝo. Se vi ensalutas aŭ kreas konton, viaj redaktoj estos atribuitaj al via uzantnomo, kune kun aliaj bonaĵoj.
Kontrolo kontraŭ spamo. Ne entajpu ion ajn!
En [[matematiko]], la termino '''optimumigo''' signifas trovi la plej bonan solvon al iu problemo, ĉar ĝi devenas de la latina vorto ''optimum'', kiu signifas ''plejbonecon''. Plejkomune oni celas minimumigi aŭ maksimumigi [[reela funkcio|reelan funkcion]] per sistema elekto de la valorojn de [[reelo|reelaj]] aŭ [[entjero|entjeraj]] [[variablo]]j el permesata aro. Tia problemo prezenteblas per la formo :''Donita:'' &nbsp; [[Funkcio (matematiko)|funkcio]] ''f'' : ''A'' <math>\to</math> '''R''' el iu [[Aro (matematiko)|aro]] ''A'' al la [[Reela nombro|reelaj nombroj]] :''Trovenda:'' &nbsp; ero ''x''<sub>0</sub> en ''A'' tia, ke ''f''(''x''<sub>0</sub>) ≤ ''f''(''x'') por ĉiuj ''x'' en ''A'' ("minimumigo") aŭ tia, ke ''f''(''x''<sub>0</sub>) ≥ ''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]] '''R'''<sup>''n''</sup>, 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 (matematiko)|domajno]] ''A'' de ''f'' estas nomita la '''serĉo-spaco''', dum la eroj de ''A'' estas nomitaj '''[[Kandidata solvaĵo|kandidataj solvoj]]''' aŭ '''fareblaj solvaĵoj'''. Ĝenerale, tie estos kelkaj lokaj minimumoj kaj maksimumoj, kie ''[[loka minimumo]]'' x<sup>*</sup> estas difinita kiel punkto tia, ke por iu δ &gt; 0 kaj ĉiuj x tia, ke :<math>\|\mathbf{x}-\mathbf{x}^*\|\leq\delta</math>; la formulo :<math>f(\mathbf{x}^*)\leq f(\mathbf{x})</math> validas; tio estas por diri, sur iu regiono ĉirkaŭ x<sup>*</sup> ĉ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 funkcio|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 [[aplika matematiko]] 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). == Notacio (skribmaniero) == Problemoj de optimumigo estas ofte esprimitaj per speciala notacio. Jen kelkaj ekzemploj: :<math>\min_{x\in\mathbb R}\; x^2 + 1</math> Tio celas la minimuman valoron por la objektiva funkcio ''x<sup>2</sup>''&nbsp;+&nbsp;1, kie ''x'' gamas super la [[Reela nombro|reelaj nombroj]] '''R'''. La minimuma valoro en ĉi tiu kazo estas 1, okazanta je ''x''&nbsp;=&nbsp;0. :<math>\max_{x\in\mathbb R}\; 2x</math> Tio celas la maksimuman valoron por la objektiva funkcio 2''x'', kie ''x'' gamas super la reelaj nombroj. En tiu kazo, estas nenia tia maksimumo ĉar la objektiva funkcio estas nebarita, do la respondo estas "[[Infinito|malfinio]]" aŭ "nedefinita". :<math>\operatorname{argmin}_{x\in[-\infty,-1]}\; x^2 + 1</math> Tio celas la valoro(j)n de ''x'' en la [[Intervalo (matematiko)|intervalo]] [−∞,&nbsp;−1] kiu(j) minimumigas la objektivan funkcion ''x''<sup>2</sup>&nbsp;+&nbsp;1. (La efektiva minimuma valoro de tiu funkcio ne gravas.) En ĉi tiu kazo, la respondo estas ''x'' = −1. :<math>\operatorname{argmax}_{x\in[-5,5],\;y\in\mathbb R}\; x\cdot\cos(y)</math> Tio celas la (''x'',&nbsp;''y'') paro(j)n kiu(j) maksimumigas la valoron de la objektiva funkcio''x''·cos(''y''), kun la aldonita limigo, ke ''x'' kuŝas en la intervalo [−5,&nbsp;5]. (Denove, la reala maksimuma valoro de la esprimo ne gravas.) En tiu kazo, la solvoj estas la paroj de la formoj (5,&nbsp;2[[Pi (nombro)|π]]''k'') kaj (−5,&nbsp;(2''k''&nbsp;+&nbsp;1)π), kie ''k'' gamas super ĉiuj [[Entjero|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. * [[Entjera programado]] studas linearajn programojn, en kiuj iuj aŭ ĉiuj variabloj estas devigitaj alpreni [[entjero|entjerajn]] valorojn. * [[Kvadrata programado]] permesas al la objektiva funkcio havi kvadratajn termojn, dum la aro A devas esti specifigita per linearaj egalecoj kaj neegalaĵoj. * [[Nelineara programado]] 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 funkcio]] kaj la limigoj, se ili ekzistas, formas [[konveksa aro|konveksan aron]]. Tio rigardeblas kiel specifa kazo de nelineara programado, aŭ kiel ĝeneraligo de lineara aŭ konveksa kvadrata programado. * [[Duondifinita programado]] (en:"SDP") estas subkampo de konveksa optimigo kie la subkuŝantaj variabloj estas [[duondifinita matrico|duondifinitaj matricoj]]. Ĝi estas ĝeneraligo de lineara kaj konveksa kvadrataj programadoj. * [[Duaorda konusa programado]] (en:"SOCP"). * [[Stokasta programado]] studas la kazon en kiu iuj el la limigoj dependas de [[hazarda variablo]]. * [[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. * [[Dinamika programado]] 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. * [[Malfinidimensia optimumigo]] studas la kazon kiam la aro de fareblaj solvaĵoj estas subaro de [[malfinidimensia spaco]], kiel ekzemple [[spaco de funkcioj]]. * [[Limigo-kotentigo]] studas la kazon en kiu la objektiva funkcio ''f'' estas konstanto (tio estas uzita en [[AI]], aparte en [[aŭtomata rezonado]]). * [[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 [[ripeta maniero|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: * [[Gradienta descendo]], alinome [[plejkruta descendo]], aŭ plejkruta ascendo * [[Nelder-Mead-a metodo]], alinome la [[ameba metodo]] * [[Subgradienta metodo]] - similas la gradientan metodon en la kazo, ke ne estas gradientoj * [[Simpleksa metodo]] * [[Elipsoida metodo]] * [[Faskaj metodoj]] * [[Neŭtona metodo en optimumigo|Neŭtona metodo]] * [[Metodoj kvazaŭ-Neŭtonaj]] * [[Metodoj interna punkto]] * [[Metodo konjugita gradiento]] * [[Linio serĉo]] 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 [[multiplikanto de Lagrange|multiplikantoj de Lagrange]]. Jen kelkaj aliaj popularaj metodoj: * [[Montet-grimpado]] * [[Tabua serĉo]] * [[Radia serĉo]] * [[Genetikaj algoritmoj]] * [[Formik-kolonia optimumigo]] * [[Evoluisma strategio]] * [[Stokasta tunelado]] * [[Diferenciala evoluismo]] * [[Partikla svarma optimumigo]] <!--* Simulita _annealing_ * Kvantuma _annealing_--> == Utiloj == Problemoj en [[solido|solida]] dinamiko ofte postulas programadajn teknikojn, ĉar oni povas rigardi solidan dinamikon provanta solvi [[ordinara diferenciala ekvacio]] sur limigo ([[dukto (matematiko)|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. [[Kliento]]j kaj [[firmao]]j estas atendataj maksimumigi sian [[profito]]n. Ankaŭe, agentojn oni atendas esti [[risk-evitemo|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 [[komputila programado|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ĝistiko|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.) <!--Fakte, iu programada laboro estis farata antaŭe...(ĉiu? - Gaŭso farita iu remburi ĉi tie)--> Aliaj gravaj matematikistoj en la optimumiga kampo inkluzivas: * [[John von Neumann]] * [[Leonid Vitalyevich Kantorovich]] * Naum Shor * Leonid Khachian * Boris Polyak * Yurii Nesterov * Arkadii Nemirovskii * Michael J. Todd * [[Richard Bellman]] == Vidu ankaŭ == * [[Argumento de maksimumo]] * [[Ludoteorio]] * [[Operaciesploro]] * [[Neakra logiko]] * [[Hazarda optimumigo]] * [[Simpleca algoritmo]] * [[Ena-punkta metodo]] * [[Varia neegalaĵo]] * [[Varia kalkulo]] * [[Minimumo]] * [[Maksimumo]] * [[Loka optimumo]] * [[Malloka optimumo]] * [[Optimumiga programaro]] <!-- *[[List of publications in mathematics#Optimization|Important publications in optimization]] *[[Radial basis function]] *[[Brachistochrone]] --> == Referencoj == * Mordecai Avriel (2003).'' Nonlinear Programming: Analysis and Methods.'' Dover Publishing. ISBN 0-486-43227-0. {{(en)}} * Stephen Boyd kaj Lieven Vandenberghe (2004). [http://www.stanford.edu/~boyd/cvxbook.html Konveksa Optimumigo], Kembriĝo (Britio) Universitato Premi. ISBN 0-521-83378-7. {{(en)}} * Panos Y. Papalambros and Douglass J. Wilde (2000). [http://www.optimaldesign.org/ Principles of Optimal Design : Modeling and Computation], Cambridge University Press. ISBN 0-521-62727-3. {{(en)}} * Jorge Nocedal and Stephen J. Wright (2006). [http://www.ece.northwestern.edu/~nocedal/book/num-opt.html Numerical Optimization], Springer. ISBN 0-387-30303-0. {{(en)}} == Eksteraj ligiloj == * [http://www-fp.mcs.anl.gov/otc/Guide/index.html NEOS Gvidilo] {{(en)}} * [http://www.mathprog.org/ Mathematical Programming Society] {{(en)}} * [http://www.coin-or.org/ COIN-OR] — Computational Infrastructure for Operations Research {{(en)}} * [http://glossary.computing.society.informs.org/ Nonlinear Programming Glossary] {{(en)}} * [http://www.ipp.mpg.de/de/for/bereiche/stellarator/Comp_sci/CompScience/csep/csep1.phy.ornl.gov/mo/mo.html Mathematical optimization] {{(en)}} * [http://www.mat.univie.ac.at/%7Eneum/glopt.html Global optimization] {{(en)}} * [http://www2.arnes.si/%7Eljc3m2/igor/links.html Optimization Related Links] {{(en)}} '''Modeligaj lingvoj:''' * [http://www.gams.com/ GAMS] — General Algebraic Modeling System * [http://www.ampl.com/ AMPL] * [http://www.maximal-usa.com/mpl/ MPL] * [http://www.aimms.com/aimms/pricing/try_aimms.html?dm=wikipedia AIMMS Optimization Modeling] — include optimization in industry solutions (free trial license available); * [http://www.ilog.com/products/oplstudio/ OPL] '''Solviloj:''' * [http://www.ilog.com/products/cplex/ CPLEX] * [http://www.mosek.com/ Mosek] * [http://www.sas.com/technologies/analytics/optimization/ SAS OR] * [http://www.conopt.com/ CONOPT] * [http://www.dashoptimization.com/ Xpress-MP - Optimization software free to students] * [[IPOPT]] - an open-source primal-dual interior point method NLP solver * [[KNITRO]] - solver for nonlinear optimization problems * [http://www.stanford.edu/group/SOL/software.html Free Optimization Software by Systems Optimization Laboratory, Stanford University] * [http://www.ingenious.cc/products/prosched.htm Optimizing Resource and Capacity with Advanced Planning and Scheduling] '''program-bibliotekoj:''' * [http://ool.sourceforge.net/ OOL (Open Optimization library)] - a set of optimization routines in C. * [http://www2.arnes.si/~ljc3m2/igor/ioptlib/ IOptLib (Investigative Optimization Library)] - a free open source library for development of optimization algorithms (ANSI C). * [http://www.aimms.com/aimms/pricing/try_aimms.html?dm=wikipedia AIMMS Optimumigo Modelanta] — inkluzivi optimumigo en industriaj solvaĵoj (libera prova permesilo havebla); * [http://www.dashoptimization.com/ Xpress-MP - Optimumiga programaro libera al studentoj] [[Kategorio:Optimumigo]] [[Kategorio:Matematiko]]
Konservante, vi konsentas senlime doni vian kontribuon laŭ la Permesilo Creative Commons Attribution-ShareAlike 3.0 kaj la GFDL.
Vi konsentas esti agnoskata de reuzantoj almenaŭ per ligilo aŭ URL al la paĝo kontribuita. Vidu la Rajtojn de Uzado por detaloj.
Nuligi Helpo pri redaktado (malfermiĝas en nova fenestro)
Specialaj Signoj: Ĉ ĉ Ĝ ĝ Ĥ ĥ Ĵ ĵ Ŝ ŝ Ŭ ŭ Ā ā Ē ē Ī ī Ō ō Ū ū · ß · Ð ð Þ þ · ĉ ĝ ĥ ĵ ŝ ŭ ·
Æ æ Œ œ · ÿ Ÿ · – — • ’ | … ~ ° «» ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ⁹ ⁰ ½ nedisegebla spaco :    ·
Vikisintakso: ligiloj [] [[]] komento :   ŝablono : {{}} {{#if:|1|0}} parametro {{{}}}
defaŭlta ordigŝlosilo {{DEFAŬLTORDIGO:}} [[Kategorio:]] {{PAGENAME}}
[[Dosiero:]] [[Media:]] #ALIDIREKTU[[]] · [[Commons:]] [[m:]] [[n:]] [[q:]] [[s:]] [[Wikt:]]
·    ·    ·    ·
Vikidatumoj entities used in this page
Ŝablonoj uzitaj sur ĉi tiu paĝo:
Ĉi tiu paĝo estas membro de 1 kaŝita kategorio:
Kategorio:Paĝoj kiuj uzas ISBNajn magiajn ligilojn
Informoj pri la paĝo
Regularo pri respekto de la privateco