Integración Y Optimización Monte Carlo

  • Published on
    13-Oct-2015

  • View
    24

  • Download
    0

Embed Size (px)

Transcript

<ul><li><p>5/23/2018 Integracin Y Optimizacin Monte Carlo</p><p> 1/31</p><p>Integracin yOptimizacin Monte Car</p><p>Modelos y SimulacinM&amp;S</p></li><li><p>5/23/2018 Integracin Y Optimizacin Monte Carlo</p><p> 2/31</p><p>Integracin Monte Carlo</p><p>Se conocen como mtodos de Monte Carlo a mtodos ebasados en el muestreo aleatorio y que usan la computacional como tcnica de solucin</p><p> La integracin Monte Carlo es un mtodo de integracinque utiliza la simulacin para resolver integrales para las existe una solucin analtica o de forma cerrada.</p><p> Funciona mejor que otras tcnicas de solucin numrica de(como el mtodo de Simpson, o la regla trapezoidal) para de mayor dimensin.</p></li><li><p>5/23/2018 Integracin Y Optimizacin Monte Carlo</p><p> 3/31</p><p>Integracin Monte Carlo</p><p>Sea</p><p> una funcin y suponga que queremos calcular</p><p>Sies una variable aleatoria con densidad , entonces la matemtica de la variable aleatoria es:</p><p>Si se tiene disponible una muestra aleatoria de la distribuciestimador insesgado de es la media muestral.</p></li><li><p>5/23/2018 Integracin Y Optimizacin Monte Carlo</p><p> 4/31</p><p>Estimador Simple de Monte Carlo</p><p>Considere el problema de estimar</p><p>.</p><p>Si, es una muestra aleatoria uniforme(0,1), entonces</p><p> 1</p><p>=</p><p>Converge a con probabilidad 1.</p></li><li><p>5/23/2018 Integracin Y Optimizacin Monte Carlo</p><p> 5/31</p><p>Lmites de Integracin (0,1)Ejem</p><p>Calcule el estimador MC de: </p><p> y compare su estimador con el valor exacto.</p><p>Calculemos el valor exacto: ] 1.Y ahora utilizando MC:</p><p>m </p></li><li><p>5/23/2018 Integracin Y Optimizacin Monte Carlo</p><p> 6/31</p><p>Lmites de Integracin (0,1)</p><p>0</p><p>0.2</p><p>0.4</p><p>0.6</p><p>0.8</p><p>1</p><p>0.00 0.02 0.04 0.06 0.08 0.10 0.12 0.14 0.16 0.18 0.20</p><p>x</p><p>0</p><p>0.2</p><p>0.4</p><p>0.6</p><p>0.8</p><p>1</p><p>1.2</p><p>0.00 0.11 0.22 0.28 0.36 0.50 0.57 0.67</p><p>x</p><p> 2 0 1 0 0</p></li><li><p>5/23/2018 Integracin Y Optimizacin Monte Carlo</p><p> 7/31</p><p>Lmites de Integracin (0,1)EjerPropuesto</p><p>Calcule el estimador MC de: 1 </p></li><li><p>5/23/2018 Integracin Y Optimizacin Monte Carlo</p><p> 8/31</p><p>Lmites de Integracin Generales</p><p>Opcin A: Se realiza un cambio de variables de (a, b) a (0, 1)</p><p> La transformacin lineal es:</p><p>Substituyendo,</p></li><li><p>5/23/2018 Integracin Y Optimizacin Monte Carlo</p><p> 9/31</p><p>Lmites de Integracin Generales</p><p>Opcin B: Se reemplaza la densidad uniforme (0, 1) con cua</p><p>densidad vlida en los lmites de integracin (a, b)</p><p> 1</p><p>Por consiguiente, la integral es veces el valor promedsobre , .</p></li><li><p>5/23/2018 Integracin Y Optimizacin Monte Carlo</p><p> 10/31</p><p>Lmites de Integracin (,)EjeCalcule el estimador MC de:</p><p>y compare su estimador con el valor exacto.</p><p>Calculemos el valor exacto: ] .Y ahora utilizando MC:</p><p>m </p></li><li><p>5/23/2018 Integracin Y Optimizacin Monte Carlo</p><p> 11/31</p><p>Algoritmo para Integracin Simpl</p><p>Considere el problema de estimar 1. Generar , , iid de una Uniforme , 2. Calcular = 3. Se retorna </p></li><li><p>5/23/2018 Integracin Y Optimizacin Monte Carlo</p><p> 12/31</p><p>Lmites de Integracin (,)Ejercicio Propuesto</p><p>Calcule el estimador MC de: sin 0,2 + 1,1 </p><p> cos , 3 </p></li><li><p>5/23/2018 Integracin Y Optimizacin Monte Carlo</p><p> 13/31</p><p>Clculo del Error Estndar de La varianza de es donde .Cuando la distribucin de es desconocida, se sustituye por la demprica de la muestra por lo que se puede realizar la siguiente es</p><p> 1</p><p>=</p><p>Y el error estndar sera:</p><p> 1 </p><p>=</p></li><li><p>5/23/2018 Integracin Y Optimizacin Monte Carlo</p><p> 14/31</p><p>Intervalo de Confianza paraEstimadores MCEl teorema del lmite central implica que:</p><p>Converge a una 0,1 cuando . Este hecho puedepara poner lmites de confianza a las estimaciones realizadas </p></li><li><p>5/23/2018 Integracin Y Optimizacin Monte Carlo</p><p> 15/31</p><p>Reduccin de la Varianza</p><p>Cuando se usa MC, los estimadores obtenidos varansimulacin a otra.</p><p> Se desea reducir esta variabilidad para aumentar la conestimador.</p><p> Cmo hacerlo?</p><p>Incrementar el valor de , el nmero de repeticiones. Utilizar tcnicas de reduccin de varianza.</p></li><li><p>5/23/2018 Integracin Y Optimizacin Monte Carlo</p><p> 16/31</p><p>Incrementar el Nmero deSimulacionesSi tenemos una cota mxima para el error estndar de , se puedenmero de rplicas necesarias como:</p></li><li><p>5/23/2018 Integracin Y Optimizacin Monte Carlo</p><p> 17/31</p><p>Integrales MltiplesPara calcular la cantidad</p><p> , </p><p>Utilizamos el hecho que , , Con , , independientes y uniformes en 0,1 Si , , </p><p>, , </p><p>, , Son muestras independientes de estas variables, podemos estimar</p><p> 1 , , </p><p>=</p></li><li><p>5/23/2018 Integracin Y Optimizacin Monte Carlo</p><p> 18/31</p><p>Integrales MltiplesEjemplo</p><p>Calcule el estimador de MC de:</p><p> , + 0,1 0,1 </p><p>O ti i i d M t C l B</p></li><li><p>5/23/2018 Integracin Y Optimizacin Monte Carlo</p><p> 19/31</p><p>Optimizacin de Monte Carlo. Bsqualeatoria pura.</p><p>Supongamos que se desea minimizar una funcin como:</p><p>Calculando la derivada y hallando las races:</p><p>mnimo local mximo local mnimo global</p><p>{0, 5/12 ,1}</p><p> 5.1,5.0con245</p><p>3617</p><p>4)( 23</p><p>4</p><p> xxf xxx</p><p>0 . 5 0 . 5 1 1 . 5</p><p>- 0 . 0 1</p><p>0 . 0 1</p><p>0 . 0 2</p><p>0 . 0 3</p><p>0 . 0 4</p></li><li><p>5/23/2018 Integracin Y Optimizacin Monte Carlo</p><p> 20/31</p><p>Soluciones</p><p> Esta es un funcin simple, que puede resolverse a simple visel clculo manual.</p><p> Pero no todas las funciones son as, incluso algunas no sonderivables</p><p>Y entonces??</p></li><li><p>5/23/2018 Integracin Y Optimizacin Monte Carlo</p><p> 21/31</p><p>Soluciones</p><p> Existen varios algoritmos de optimizacin que me permiten el mnimo o el mximo de una funcin, aunque muchas veca caer en ptimos locales.</p></li><li><p>5/23/2018 Integracin Y Optimizacin Monte Carlo</p><p> 22/31</p><p>SolucionesLa simulacin brinda otra posibilidad, que permitetambin tratar problemas con funciones no</p><p>diferenciables, e incluso buscar directamente ptimoglobales.</p><p>Mtodos de Optimizacin de Monte Carlo</p><p>(la variante ms sencilla es la Bsqueda Aleatoria Pu</p></li><li><p>5/23/2018 Integracin Y Optimizacin Monte Carlo</p><p> 23/31</p><p>Bsqueda Aleatoria Pura</p><p> Este mtodo se basa en generar los valores de la X aleatoriaevaluando la funcin y comparando el resultado en cada itepara quedarse con el valor de la funcin ms ptima (VerEjemploMonteCarlo.xlsx).</p><p>Algoritmo de Bsqueda Aleatoria</p></li><li><p>5/23/2018 Integracin Y Optimizacin Monte Carlo</p><p> 24/31</p><p>Algoritmo de Bsqueda AleatoriaPura.</p><p>Algoritmo para determinar minx[a,b]f(x) con N nmealeatorios</p><p>Inicializar i=0;fmin=.</p><p>Mientras i</p></li><li><p>5/23/2018 Integracin Y Optimizacin Monte Carlo</p><p> 25/31</p><p>Ejercicio Propuesto:</p><p>1 - 0 . 5 0 . 5 1</p><p>- 0 . 2</p><p>0 . 2</p><p>0 . 4</p><p>0 . 6</p><p>0 . 8</p><p>Busque el mnimo global para la funcin en elintervalo [1,1]</p></li><li><p>5/23/2018 Integracin Y Optimizacin Monte Carlo</p><p> 26/31</p><p>Ejercicio propuesto</p><p>Encontrar el mnimo global de la funcin</p><p>() 60 900100en el intervalo(1,40)</p><p>a) Hgalo generando 30 nmeros aleatoriosb) Hgalo generando 100 nmeros aleatorios.</p><p>c) Hgalo generando 500 nmeros aleatorios.</p></li><li><p>5/23/2018 Integracin Y Optimizacin Monte Carlo</p><p> 27/31</p><p>Ejercicio propuesto</p><p>Encontrar el mximo global de la funcin</p><p> sin en el intervalo (1,1)</p><p>a) Hgalo generando 30 nmeros aleatorios</p><p>b) Hgalo generando 100 nmeros aleatorios.</p><p>c) Hgalo generando 500 nmeros aleatorios.</p></li><li><p>5/23/2018 Integracin Y Optimizacin Monte Carlo</p><p> 28/31</p><p>Ejercicio propuesto</p><p>Encontrar el mximo global de la funcin</p><p> en el intervalo (2,1)</p><p>a) Hgalo generando 30 nmeros aleatorios</p><p>b) Hgalo generando 100 nmeros aleatorios.</p><p>c) Hgalo generando 500 nmeros aleatorios.</p></li><li><p>5/23/2018 Integracin Y Optimizacin Monte Carlo</p><p> 29/31</p><p>Problemas de OptimizacinCombinatoria</p><p> El problema del agente viajero es un problema de</p><p>optimizacin combinatoria que tambin puede serresuelto con mtodos de Monte Carlo</p><p>Cmo puede con el mtodo de bsqueda aleatoria pur</p><p>resolver este tipo de problemas?</p><p>Propuesto: Intente hacerlo en Excel</p></li><li><p>5/23/2018 Integracin Y Optimizacin Monte Carlo</p><p> 30/31</p><p>Ejemplo</p><p> Resuelva el problema del agente viajero, partiendo d</p><p>la ciudad 1, con la siguiente matriz de distancias</p><p>Matriz de distancias entre las 5</p><p>ciudades</p><p>1 2 3 4 5</p><p>1 0 3 3 2 5</p><p>2 3 0 2 3 4</p><p>3 3 2 0 5 1</p><p>4 2 3 5 0 4</p><p>5 5 4 1 4 0</p></li><li><p>5/23/2018 Integracin Y Optimizacin Monte Carlo</p><p> 31/31</p><p>Ejercicio Propuesto</p><p> Resuelva el problema del agente viajero, partiendo</p><p>del DC, con la siguiente matriz de distancias</p></li></ul>