Programación estocástica

Marco para modelar problemas de optimización que involucran incertidumbre

En el campo de la optimización matemática , la programación estocástica es un marco para modelar problemas de optimización que involucran incertidumbre . Un programa estocástico es un problema de optimización en el que algunos o todos los parámetros del problema son inciertos, pero siguen distribuciones de probabilidad conocidas . ^{[1] [2]} Este marco contrasta con la optimización determinista, en la que se supone que todos los parámetros del problema se conocen con exactitud. El objetivo de la programación estocástica es encontrar una decisión que optimice algunos criterios elegidos por el tomador de decisiones y que tenga en cuenta adecuadamente la incertidumbre de los parámetros del problema. Debido a que muchas decisiones del mundo real involucran incertidumbre, la programación estocástica ha encontrado aplicaciones en una amplia gama de áreas que van desde las finanzas hasta el transporte y la optimización energética. ^{[3] [4]}

Métodos

Se han desarrollado varios métodos de programación estocástica:

• Métodos basados ​​en escenarios, incluida la aproximación del promedio de muestra
• Programación entera estocástica para problemas en los que algunas variables deben ser números enteros
• Programación con restricciones de probabilidad para tratar con restricciones que deben satisfacerse con una probabilidad dada
• Programación dinámica estocástica
• Proceso de decisión de Markov
• Descomposición de Bender

Definición de problema en dos etapas

La idea básica de la programación estocástica de dos etapas es que las decisiones (óptimas) deben basarse en los datos disponibles en el momento en que se toman las decisiones y no pueden depender de observaciones futuras. La formulación de dos etapas se utiliza ampliamente en la programación estocástica. La formulación general de un problema de programación estocástica de dos etapas viene dada por: donde es el valor óptimo del problema de la segunda etapa. $${\displaystyle \min _{x\in X}\{g(x)=f(x)+E_{\xi }[Q(x,\xi )]\}}$$ ${\displaystyle Q(x,\xi )}$ $${\displaystyle \min _{y}\{q(y,\xi )\,|\,T(\xi )x+W(\xi )y=h(\xi )\}.}$$

Los problemas clásicos de programación estocástica lineal de dos etapas se pueden formular como $${\displaystyle {\begin{array}{llr}\min \limits _{x\in \mathbb {R} ^{n}}&g(x)=c^{T}x+E_{\xi }[Q(x,\xi )]&\\{\text{subject to}}&Ax=b&\\&x\geq 0&\end{array}}}$$

¿Dónde está el valor óptimo del problema de la segunda etapa? ${\displaystyle Q(x,\xi )}$ $${\displaystyle {\begin{array}{llr}\min \limits _{y\in \mathbb {R} ^{m}}&q(\xi )^{T}y&\\{\text{subject to}}&T(\xi )x+W(\xi )y=h(\xi )&\\&y\geq 0&\end{array}}}$$

En esta formulación , el vector de la variable de decisión de la primera etapa es el vector de la variable de decisión de la segunda etapa y contiene los datos del problema de la segunda etapa. En esta formulación, en la primera etapa tenemos que tomar una decisión "aquí y ahora" antes de que se conozca la realización de los datos inciertos , vistos como un vector aleatorio. En la segunda etapa, después de que se disponga de una realización de, optimizamos nuestro comportamiento resolviendo un problema de optimización adecuado. ${\displaystyle x\in \mathbb {R} ^{n}}$ ${\displaystyle y\in \mathbb {R} ^{m}}$ ${\displaystyle \xi (q,T,W,h)}$ ${\displaystyle x}$ ${\displaystyle \xi }$ ${\displaystyle \xi }$

En la primera etapa optimizamos (minimizamos en la formulación anterior) el costo de la decisión de la primera etapa más el costo esperado de la decisión (óptima) de la segunda etapa. Podemos considerar el problema de la segunda etapa simplemente como un problema de optimización que describe nuestro comportamiento supuestamente óptimo cuando se revelan los datos inciertos, o podemos considerar su solución como una acción de recurso donde el término compensa una posible inconsistencia del sistema y es el costo de esta acción de recurso. ${\displaystyle c^{T}x}$ ${\displaystyle Wy}$ ${\displaystyle Tx\leq h}$ ${\displaystyle q^{T}y}$

El problema de dos etapas considerado es lineal porque las funciones objetivo y las restricciones son lineales. Conceptualmente esto no es esencial y se pueden considerar programas estocásticos de dos etapas más generales. Por ejemplo, si el problema de la primera etapa es entero, se podrían agregar restricciones de integralidad al problema de la primera etapa para que el conjunto factible sea discreto. También se podrían incorporar objetivos y restricciones no lineales si fuera necesario. ^[5]

Supuesto distributivo

La formulación del problema de dos etapas anterior supone que los datos de la segunda etapa se modelan como un vector aleatorio con una distribución de probabilidad conocida . Esto estaría justificado en muchas situaciones. Por ejemplo, la distribución de podría inferirse a partir de datos históricos si se supone que la distribución no cambia significativamente durante el período de tiempo considerado. Además, la distribución empírica de la muestra podría utilizarse como una aproximación a la distribución de los valores futuros de . Si se tiene un modelo previo para , se podría obtener una distribución a posteriori mediante una actualización bayesiana. ${\displaystyle \xi }$ ${\displaystyle \xi }$ ${\displaystyle \xi }$ ${\displaystyle \xi }$

Enfoque basado en escenarios

Discretización

Para resolver numéricamente el problema estocástico de dos etapas, a menudo es necesario suponer que el vector aleatorio tiene un número finito de posibles realizaciones, llamadas escenarios , por ejemplo , con respectivas masas de probabilidad . Entonces, la esperanza en la función objetivo del problema de la primera etapa se puede escribir como la suma: y, además, el problema de dos etapas se puede formular como un gran problema de programación lineal (esto se llama el equivalente determinista del problema original, consulte la sección § Equivalente determinista de un problema estocástico). ${\displaystyle \xi }$ ${\displaystyle \xi _{1},\dots ,\xi _{K}}$ ${\displaystyle p_{1},\dots ,p_{K}}$ $${\displaystyle E[Q(x,\xi )]=\sum \limits _{k=1}^{K}p_{k}Q(x,\xi _{k})}$$

Cuando hay un número infinito (o muy grande) de realizaciones posibles, el enfoque estándar es representar esta distribución mediante escenarios. Este enfoque plantea tres preguntas, a saber: ${\displaystyle \xi }$

1. Para saber cómo construir escenarios, véase § Construcción de escenarios;
2. Cómo resolver el equivalente determinista. Optimizadores como CPLEX y GLPK pueden resolver grandes problemas lineales/no lineales. El servidor NEOS, ^[6] alojado en la Universidad de Wisconsin, Madison , permite el acceso gratuito a muchos solucionadores modernos. La estructura de un equivalente determinista es particularmente susceptible a la aplicación de métodos de descomposición, ^[7] como la descomposición de Benders o la descomposición de escenarios;
3. Cómo medir la calidad de la solución obtenida con respecto al óptimo "verdadero".

Estas cuestiones no son independientes. Por ejemplo, el número de escenarios construidos afectará tanto a la viabilidad del equivalente determinista como a la calidad de las soluciones obtenidas.

Programación lineal estocástica

Un programa lineal estocástico es una instancia específica del programa estocástico clásico de dos etapas. Un programa lineal estocástico se construye a partir de una colección de programas lineales (PL) de varios períodos, cada uno con la misma estructura pero con datos ligeramente diferentes. El programa lineal de dos períodos, que representa el escenario, puede considerarse como si tuviera la siguiente forma: ${\displaystyle k^{th}}$ ${\displaystyle k^{th}}$

${\displaystyle {\begin{array}{lccccccc}{\text{Minimize}}&f^{T}x&+&g^{T}y&+&h_{k}^{T}z_{k}&&\\{\text{subject to}}&Tx&+&Uy&&&=&r\\&&&V_{k}y&+&W_{k}z_{k}&=&s_{k}\\&x&,&y&,&z_{k}&\geq &0\end{array}}}$

Los vectores y contienen las variables del primer período, cuyos valores deben elegirse inmediatamente. El vector contiene todas las variables de los períodos posteriores. Las restricciones solo afectan a las variables del primer período y son las mismas en todos los escenarios. Las demás restricciones afectan a las variables de períodos posteriores y difieren en algunos aspectos de un escenario a otro, lo que refleja la incertidumbre sobre el futuro. ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle z_{k}}$ ${\displaystyle Tx+Uy=r}$

Obsérvese que resolver el modelo lineal de dos períodos equivale a suponer que el escenario del segundo período no tiene incertidumbre. Para incorporar incertidumbres en la segunda etapa, se deben asignar probabilidades a diferentes escenarios y resolver el equivalente determinista correspondiente. ${\displaystyle k^{th}}$ ${\displaystyle k^{th}}$

Equivalente determinista de un problema estocástico

Con un número finito de escenarios, los programas lineales estocásticos de dos etapas se pueden modelar como grandes problemas de programación lineal. Esta formulación a menudo se denomina programa lineal equivalente determinista, o abreviado como equivalente determinista. (Estrictamente hablando, un equivalente determinista es cualquier programa matemático que se puede utilizar para calcular la decisión óptima de la primera etapa, por lo que también existirán para distribuciones de probabilidad continuas, cuando se pueda representar el costo de la segunda etapa en alguna forma cerrada). Por ejemplo, para formar el equivalente determinista del programa lineal estocástico anterior, asignamos una probabilidad a cada escenario . Luego podemos minimizar el valor esperado del objetivo, sujeto a las restricciones de todos los escenarios: ${\displaystyle p_{k}}$ ${\displaystyle k=1,\dots ,K}$

${\displaystyle {\begin{array}{lccccccccccccc}{\text{Minimize}}&f^{\top }x&+&g^{\top }y&+&p_{1}h_{1}^{\top }z_{1}&+&p_{2}h_{2}^{T}z_{2}&+&\cdots &+&p_{K}h_{K}^{\top }z_{K}&&\\{\text{subject to}}&Tx&+&Uy&&&&&&&&&=&r\\&&&V_{1}y&+&W_{1}z_{1}&&&&&&&=&s_{1}\\&&&V_{2}y&&&+&W_{2}z_{2}&&&&&=&s_{2}\\&&&\vdots &&&&&&\ddots &&&&\vdots \\&&&V_{K}y&&&&&&&+&W_{K}z_{K}&=&s_{K}\\&x&,&y&,&z_{1}&,&z_{2}&,&\ldots &,&z_{K}&\geq &0\\\end{array}}}$

Tenemos un vector diferente de variables de períodos posteriores para cada escenario . Sin embargo, las variables del primer período y son las mismas en cada escenario, porque debemos tomar una decisión para el primer período antes de saber qué escenario se realizará. Como resultado, las restricciones que involucran solo y solo deben especificarse una vez, mientras que las restricciones restantes deben darse por separado para cada escenario. ${\displaystyle z_{k}}$ ${\displaystyle k}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$

Construcción de escenarios

En la práctica, es posible construir escenarios solicitando la opinión de expertos sobre el futuro. El número de escenarios construidos debe ser relativamente modesto para que el equivalente determinista obtenido pueda resolverse con un esfuerzo computacional razonable. A menudo se afirma que una solución que es óptima utilizando solo unos pocos escenarios proporciona planes más adaptables que una que supone un solo escenario. En algunos casos, tal afirmación podría verificarse mediante una simulación. En teoría, algunas medidas de garantía de que una solución obtenida resuelve el problema original con una precisión razonable. Por lo general, en las aplicaciones, solo la solución óptima de la primera etapa tiene un valor práctico, ya que casi siempre una realización "verdadera" de los datos aleatorios será diferente del conjunto de escenarios construidos (generados). ${\displaystyle x^{*}}$

Supongamos que contiene componentes aleatorios independientes, cada uno de los cuales tiene tres posibles realizaciones (por ejemplo, las realizaciones futuras de cada parámetro aleatorio se clasifican como baja, media y alta), entonces el número total de escenarios es . Tal crecimiento exponencial del número de escenarios hace que el desarrollo de modelos utilizando la opinión de expertos sea muy difícil incluso para un tamaño razonable . La situación se vuelve aún peor si algunos componentes aleatorios de tienen distribuciones continuas. ${\displaystyle \xi }$ ${\displaystyle d}$ ${\displaystyle K=3^{d}}$ ${\displaystyle d}$ ${\displaystyle \xi }$

Muestreo de Monte Carlo y método de aproximación de la media de la muestra (SAA)

Un enfoque común para reducir el conjunto de escenarios a un tamaño manejable es mediante la simulación de Monte Carlo. Supongamos que el número total de escenarios es muy grande o incluso infinito. Supongamos además que podemos generar una muestra de réplicas del vector aleatorio . Por lo general, se supone que la muestra es independiente y está distribuida de manera idéntica (muestra iid). Dada una muestra, la función de expectativa se aproxima mediante el promedio de la muestra. ${\displaystyle \xi ^{1},\xi ^{2},\dots ,\xi ^{N}}$ ${\displaystyle N}$ ${\displaystyle \xi }$ ${\displaystyle q(x)=E[Q(x,\xi )]}$

${\displaystyle {\hat {q}}_{N}(x)={\frac {1}{N}}\sum _{j=1}^{N}Q(x,\xi ^{j})}$

y en consecuencia el problema de la primera etapa está dado por

${\displaystyle {\begin{array}{rlrrr}{\hat {g}}_{N}(x)=&\min \limits _{x\in \mathbb {R} ^{n}}&c^{T}x+{\frac {1}{N}}\sum _{j=1}^{N}Q(x,\xi ^{j})&\\&{\text{subject to}}&Ax&=&b\\&&x&\geq &0\end{array}}}$

Esta formulación se conoce como método de aproximación de promedio de muestra . El problema de SAA es una función de la muestra considerada y, en ese sentido, es aleatorio. Para una muestra dada, el problema de SAA tiene la misma forma que un problema de programación lineal estocástica de dos etapas con los escenarios ., , cada uno tomado con la misma probabilidad . ${\displaystyle \xi ^{1},\xi ^{2},\dots ,\xi ^{N}}$ ${\displaystyle \xi ^{j}}$ ${\displaystyle j=1,\dots ,N}$ ${\displaystyle p_{j}={\frac {1}{N}}}$

Inferencia estadística

Considere el siguiente problema de programación estocástica

${\displaystyle \min \limits _{x\in X}\{g(x)=f(x)+E[Q(x,\xi )]\}}$

Aquí hay un subconjunto cerrado no vacío de , es un vector aleatorio cuya distribución de probabilidad se sustenta en un conjunto , y . En el marco de la programación estocástica de dos etapas, viene dado por el valor óptimo del problema de segunda etapa correspondiente. ${\displaystyle X}$ ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle \xi }$ ${\displaystyle P}$ ${\displaystyle \Xi \subset \mathbb {R} ^{d}}$ ${\displaystyle Q:X\times \Xi \rightarrow \mathbb {R} }$ ${\displaystyle Q(x,\xi )}$

Supongamos que está bien definido y tiene un valor finito para todos los . Esto implica que para cada uno el valor es finito casi con seguridad. ${\displaystyle g(x)}$ ${\displaystyle x\in X}$ ${\displaystyle x\in X}$ ${\displaystyle Q(x,\xi )}$

Supongamos que tenemos una muestra de realizaciones del vector aleatorio . Esta muestra aleatoria puede considerarse como datos históricos de observaciones de , o puede generarse mediante técnicas de muestreo de Monte Carlo. Luego podemos formular una aproximación de promedio de muestra correspondiente ${\displaystyle \xi ^{1},\dots ,\xi ^{N}}$ ${\displaystyle N}$ ${\displaystyle \xi }$ ${\displaystyle N}$ ${\displaystyle \xi }$

${\displaystyle \min \limits _{x\in X}\{{\hat {g}}_{N}(x)=f(x)+{\frac {1}{N}}\sum _{j=1}^{N}Q(x,\xi ^{j})\}}$

Por la Ley de los Grandes Números tenemos que, bajo ciertas condiciones de regularidad converge puntualmente con probabilidad 1 a como . Además, bajo condiciones adicionales leves la convergencia es uniforme. También tenemos , es decir, es un estimador insesgado de . Por lo tanto, es natural esperar que el valor óptimo y las soluciones óptimas del problema SAA converjan a sus contrapartes del problema verdadero como . ${\displaystyle {\frac {1}{N}}\sum _{j=1}^{N}Q(x,\xi ^{j})}$ ${\displaystyle E[Q(x,\xi )]}$ ${\displaystyle N\rightarrow \infty }$ ${\displaystyle E[{\hat {g}}_{N}(x)]=g(x)}$ ${\displaystyle {\hat {g}}_{N}(x)}$ ${\displaystyle g(x)}$ ${\displaystyle N\rightarrow \infty }$

Consistencia de los estimadores SAA

Supongamos que el conjunto factible del problema SAA es fijo, es decir, es independiente de la muestra. Sean y el valor óptimo y el conjunto de soluciones óptimas, respectivamente, del problema verdadero y sean y el valor óptimo y el conjunto de soluciones óptimas, respectivamente, del problema SAA. ${\displaystyle X}$ ${\displaystyle \vartheta ^{*}}$ ${\displaystyle S^{*}}$ ${\displaystyle {\hat {\vartheta }}_{N}}$ ${\displaystyle {\hat {S}}_{N}}$

1. Sea y una secuencia de funciones reales (deterministas). Las dos propiedades siguientes son equivalentes: ${\displaystyle g:X\rightarrow \mathbb {R} }$ ${\displaystyle {\hat {g}}_{N}:X\rightarrow \mathbb {R} }$
   • para cualquier y cualquier secuencia que converge a se sigue que converge a ${\displaystyle {\overline {x}}\in X}$ ${\displaystyle \{x_{N}\}\subset X}$ ${\displaystyle {\overline {x}}}$ ${\displaystyle {\hat {g}}_{N}(x_{N})}$ ${\displaystyle g({\overline {x}})}$
   • la función es continua en y converge uniformemente en cualquier subconjunto compacto de ${\displaystyle g(\cdot )}$ ${\displaystyle X}$ ${\displaystyle {\hat {g}}_{N}(\cdot )}$ ${\displaystyle g(\cdot )}$ ${\displaystyle X}$
2. Si el objetivo del problema SAA converge al objetivo del problema verdadero con probabilidad 1, como , uniformemente en el conjunto factible . Entonces converge a con probabilidad 1 como . ${\displaystyle {\hat {g}}_{N}(x)}$ ${\displaystyle g(x)}$ ${\displaystyle N\rightarrow \infty }$ ${\displaystyle X}$ ${\displaystyle {\hat {\vartheta }}_{N}}$ ${\displaystyle \vartheta ^{*}}$ ${\displaystyle N\rightarrow \infty }$
3. Supongamos que existe un conjunto compacto tal que ${\displaystyle C\subset \mathbb {R} ^{n}}$
   • El conjunto de soluciones óptimas del problema verdadero no está vacío y está contenido en ${\displaystyle S}$ ${\displaystyle C}$
   • La función tiene un valor finito y es continua en ${\displaystyle g(x)}$ ${\displaystyle C}$
   • la secuencia de funciones converge a con probabilidad 1, como , uniformemente en ${\displaystyle {\hat {g}}_{N}(x)}$ ${\displaystyle g(x)}$ ${\displaystyle N\rightarrow \infty }$ ${\displaystyle x\in C}$
   • Para un tamaño suficientemente grande el conjunto no está vacío y la probabilidad es 1. ${\displaystyle N}$ ${\displaystyle {\hat {S}}_{N}}$ ${\displaystyle {\hat {S}}_{N}\subset C}$

entonces y con probabilidad 1 como . Nótese que denota la desviación del conjunto respecto del conjunto , definida como ${\displaystyle {\hat {\vartheta }}_{N}\rightarrow \vartheta ^{*}}$ ${\displaystyle \mathbb {D} (S^{*},{\hat {S}}_{N})\rightarrow 0}$ ${\displaystyle N\rightarrow \infty }$ ${\displaystyle \mathbb {D} (A,B)}$ ${\displaystyle A}$ ${\displaystyle B}$

${\displaystyle \mathbb {D} (A,B):=\sup _{x\in A}\{\inf _{x'\in B}\|x-x'\|\}}$

En algunas situaciones se estima el conjunto factible del problema SAA, luego el problema SAA correspondiente toma la forma ${\displaystyle X}$

${\displaystyle \min _{x\in X_{N}}{\hat {g}}_{N}(x)}$

donde es un subconjunto de que depende de la muestra y, por lo tanto, es aleatorio. No obstante, los resultados de consistencia para los estimadores SAA aún se pueden derivar bajo algunos supuestos adicionales: ${\displaystyle X_{N}}$ ${\displaystyle \mathbb {R} ^{n}}$

1. Supongamos que existe un conjunto compacto tal que ${\displaystyle C\subset \mathbb {R} ^{n}}$
   • El conjunto de soluciones óptimas del problema verdadero no está vacío y está contenido en ${\displaystyle S}$ ${\displaystyle C}$
   • La función tiene un valor finito y es continua en ${\displaystyle g(x)}$ ${\displaystyle C}$
   • la secuencia de funciones converge a con probabilidad 1, como , uniformemente en ${\displaystyle {\hat {g}}_{N}(x)}$ ${\displaystyle g(x)}$ ${\displaystyle N\rightarrow \infty }$ ${\displaystyle x\in C}$
   • Para un tamaño suficientemente grande el conjunto no está vacío y la probabilidad es 1. ${\displaystyle N}$ ${\displaystyle {\hat {S}}_{N}}$ ${\displaystyle {\hat {S}}_{N}\subset C}$
   • Si y converge con probabilidad 1 a un punto , entonces ${\displaystyle x_{N}\in X_{N}}$ ${\displaystyle x_{N}}$ ${\displaystyle x}$ ${\displaystyle x\in X}$
   • para algún punto existe una secuencia tal que con probabilidad 1. ${\displaystyle x\in S^{*}}$ ${\displaystyle x_{N}\in X_{N}}$ ${\displaystyle x_{N}\rightarrow x}$

entonces y con probabilidad 1 como . ${\displaystyle {\hat {\vartheta }}_{N}\rightarrow \vartheta ^{*}}$ ${\displaystyle \mathbb {D} (S^{*},{\hat {S}}_{N})\rightarrow 0}$ ${\displaystyle N\rightarrow \infty }$

Asintótica del valor óptimo de SAA

Supongamos que la muestra es iid y fija un punto . Entonces, el estimador promedio de la muestra , de , es insesgado y tiene varianza , donde se supone que es finita. Además, por el teorema del límite central tenemos que ${\displaystyle \xi ^{1},\dots ,\xi ^{N}}$ ${\displaystyle x\in X}$ ${\displaystyle {\hat {g}}_{N}(x)}$ ${\displaystyle g(x)}$ ${\displaystyle {\frac {1}{N}}\sigma ^{2}(x)}$ ${\displaystyle \sigma ^{2}(x):=Var[Q(x,\xi )]}$

${\displaystyle {\sqrt {N}}[{\hat {g}}_{N}-g(x)]{\xrightarrow {\mathcal {D}}}Y_{x}}$

donde denota convergencia en la distribución y tiene una distribución normal con media y varianza , escrita como . ${\displaystyle {\xrightarrow {\mathcal {D}}}}$ ${\displaystyle Y_{x}}$ ${\displaystyle 0}$ ${\displaystyle \sigma ^{2}(x)}$ ${\displaystyle {\mathcal {N}}(0,\sigma ^{2}(x))}$

En otras palabras, tiene una distribución asintóticamente normal , es decir, para valores grandes , tiene una distribución aproximadamente normal con media y varianza . Esto conduce al siguiente intervalo de confianza (aproximado) % para : ${\displaystyle {\hat {g}}_{N}(x)}$ ${\displaystyle N}$ ${\displaystyle {\hat {g}}_{N}(x)}$ ${\displaystyle g(x)}$ ${\displaystyle {\frac {1}{N}}\sigma ^{2}(x)}$ ${\displaystyle 100(1-\alpha )}$ ${\displaystyle f(x)}$

${\displaystyle \left[{\hat {g}}_{N}(x)-z_{\alpha /2}{\frac {{\hat {\sigma }}(x)}{\sqrt {N}}},{\hat {g}}_{N}(x)+z_{\alpha /2}{\frac {{\hat {\sigma }}(x)}{\sqrt {N}}}\right]}$

donde (aquí denota la cdf de la distribución normal estándar) y ${\displaystyle z_{\alpha /2}:=\Phi ^{-1}(1-\alpha /2)}$ ${\displaystyle \Phi (\cdot )}$

${\displaystyle {\hat {\sigma }}^{2}(x):={\frac {1}{N-1}}\sum _{j=1}^{N}\left[Q(x,\xi ^{j})-{\frac {1}{N}}\sum _{j=1}^{N}Q(x,\xi ^{j})\right]^{2}}$

es la estimación de la varianza muestral de . Es decir, el error de estimación de es (estocásticamente) de orden . ${\displaystyle \sigma ^{2}(x)}$ ${\displaystyle g(x)}$ ${\displaystyle O({\sqrt {N}})}$

Aplicaciones y ejemplos

Aplicaciones biológicas

La programación dinámica estocástica se utiliza con frecuencia para modelar el comportamiento animal en campos como la ecología del comportamiento . ^{[8] [9]} Las pruebas empíricas de modelos de búsqueda de alimento óptima y transiciones en la historia de vida , como el emplumamiento en las aves y la puesta de huevos en las avispas parasitoides , han demostrado el valor de esta técnica de modelado para explicar la evolución de la toma de decisiones conductuales. Estos modelos suelen tener muchas etapas, en lugar de dos.

Aplicaciones económicas

La programación dinámica estocástica es una herramienta útil para comprender la toma de decisiones en condiciones de incertidumbre. La acumulación de capital en condiciones de incertidumbre es un ejemplo; los economistas especializados en recursos la utilizan a menudo para analizar problemas bioeconómicos ^[10] en los que interviene la incertidumbre, como el clima, etc.

Ejemplo: optimización de cartera en varias etapas

El siguiente es un ejemplo de finanzas de programación estocástica de múltiples etapas. Supongamos que en un momento dado tenemos capital inicial para invertir en activos. Supongamos además que se nos permite reequilibrar nuestra cartera en ocasiones, pero sin inyectarle efectivo adicional. En cada período tomamos una decisión sobre la redistribución de la riqueza actual entre los activos. Sean las cantidades iniciales invertidas en los n activos. Requerimos que cada una sea no negativa y que la ecuación de equilibrio se cumpla. ${\displaystyle t=0}$ ${\displaystyle W_{0}}$ ${\displaystyle n}$ ${\displaystyle t=1,\dots ,T-1}$ ${\displaystyle t}$ ${\displaystyle W_{t}}$ ${\displaystyle n}$ ${\displaystyle x_{0}=(x_{10},\dots ,x_{n0})}$ ${\displaystyle x_{i0}}$ ${\displaystyle \sum _{i=1}^{n}x_{i0}=W_{0}}$

Considere los rendimientos totales para cada período . Esto forma un proceso aleatorio de valor vectorial . En el período de tiempo , podemos reequilibrar la cartera especificando las cantidades invertidas en los respectivos activos. En ese momento se han realizado los rendimientos en el primer período, por lo que es razonable utilizar esta información en la decisión de reequilibrio. Por lo tanto, las decisiones de la segunda etapa, en el momento , son en realidad funciones de realización del vector aleatorio , es decir, . De manera similar, en el momento la decisión es una función de la información disponible dada por la historia del proceso aleatorio hasta el momento . Una secuencia de funciones , , con ser constante, define una política implementable del proceso de decisión. Se dice que dicha política es factible si satisface las restricciones del modelo con probabilidad 1, es decir, las restricciones de no negatividad , , , y las restricciones de equilibrio de riqueza, ${\displaystyle \xi _{t}=(\xi _{1t},\dots ,\xi _{nt})}$ ${\displaystyle t=1,\dots ,T}$ ${\displaystyle \xi _{1},\dots ,\xi _{T}}$ ${\displaystyle t=1}$ ${\displaystyle x_{1}=(x_{11},\dots ,x_{n1})}$ ${\displaystyle t=1}$ ${\displaystyle \xi _{1}}$ ${\displaystyle x_{1}=x_{1}(\xi _{1})}$ ${\displaystyle t}$ ${\displaystyle x_{t}=(x_{1t},\dots ,x_{nt})}$ ${\displaystyle x_{t}=x_{t}(\xi _{[t]})}$ ${\displaystyle \xi _{[t]}=(\xi _{1},\dots ,\xi _{t})}$ ${\displaystyle t}$ ${\displaystyle x_{t}=x_{t}(\xi _{[t]})}$ ${\displaystyle t=0,\dots ,T-1}$ ${\displaystyle x_{0}}$ ${\displaystyle x_{it}(\xi _{[t]})\geq 0}$ ${\displaystyle i=1,\dots ,n}$ ${\displaystyle t=0,\dots ,T-1}$

${\displaystyle \sum _{i=1}^{n}x_{it}(\xi _{[t]})=W_{t},}$

donde en el periodo la riqueza viene dada por ${\displaystyle t=1,\dots ,T}$ ${\displaystyle W_{t}}$

${\displaystyle W_{t}=\sum _{i=1}^{n}\xi _{it}x_{i,t-1}(\xi _{[t-1]}),}$

que depende de la realización del proceso aleatorio y de las decisiones tomadas hasta el momento . ${\displaystyle t}$

Supongamos que el objetivo es maximizar la utilidad esperada de esta riqueza en el último período, es decir, considerar el problema

${\displaystyle \max E[U(W_{T})].}$

Este es un problema de programación estocástica de múltiples etapas, donde las etapas están numeradas de a . La optimización se realiza sobre todas las políticas implementables y factibles. Para completar la descripción del problema, también es necesario definir la distribución de probabilidad del proceso aleatorio . Esto se puede hacer de varias maneras. Por ejemplo, se puede construir un árbol de escenarios particular que defina la evolución temporal del proceso. Si en cada etapa se permite que el rendimiento aleatorio de cada activo tenga dos continuaciones, independientemente de otros activos, entonces el número total de escenarios es ${\displaystyle t=0}$ ${\displaystyle t=T-1}$ ${\displaystyle \xi _{1},\dots ,\xi _{T}}$ ${\displaystyle 2^{nT}.}$

Para escribir ecuaciones de programación dinámica , considere el problema de múltiples etapas anterior hacia atrás en el tiempo. En la última etapa , se conoce y se ha elegido una realización del proceso aleatorio . Por lo tanto, es necesario resolver el siguiente problema ${\displaystyle t=T-1}$ ${\displaystyle \xi _{[T-1]}=(\xi _{1},\dots ,\xi _{T-1})}$ ${\displaystyle x_{T-2}}$

${\displaystyle {\begin{array}{lrclr}\max \limits _{x_{T-1}}&E[U(W_{T})|\xi _{[T-1]}]&\\{\text{subject to}}&W_{T}&=&\sum _{i=1}^{n}\xi _{iT}x_{i,T-1}\\&\sum _{i=1}^{n}x_{i,T-1}&=&W_{T-1}\\&x_{T-1}&\geq &0\end{array}}}$

donde denota la esperanza condicional de dado . El valor óptimo del problema anterior depende de y y se denota . ${\displaystyle E[U(W_{T})|\xi _{[T-1]}]}$ ${\displaystyle U(W_{T})}$ ${\displaystyle \xi _{[T-1]}}$ ${\displaystyle W_{T-1}}$ ${\displaystyle \xi _{[T-1]}}$ ${\displaystyle Q_{T-1}(W_{T-1},\xi _{[T-1]})}$

De manera similar, en las etapas , se debe resolver el problema. ${\displaystyle t=T-2,\dots ,1}$

${\displaystyle {\begin{array}{lrclr}\max \limits _{x_{t}}&E[Q_{t+1}(W_{t+1},\xi _{[t+1]})|\xi _{[t]}]&\\{\text{subject to}}&W_{t+1}&=&\sum _{i=1}^{n}\xi _{i,t+1}x_{i,t}\\&\sum _{i=1}^{n}x_{i,t}&=&W_{t}\\&x_{t}&\geq &0\end{array}}}$

cuyo valor óptimo se denota por . Finalmente, en la etapa , se resuelve el problema ${\displaystyle Q_{t}(W_{t},\xi _{[t]})}$ ${\displaystyle t=0}$

${\displaystyle {\begin{array}{lrclr}\max \limits _{x_{0}}&E[Q_{1}(W_{1},\xi _{[1]})]&\\{\text{subject to}}&W_{1}&=&\sum _{i=1}^{n}\xi _{i,1}x_{i0}\\&\sum _{i=1}^{n}x_{i0}&=&W_{0}\\&x_{0}&\geq &0\end{array}}}$

Proceso aleatorio independiente por etapas

Para una distribución general del proceso , puede resultar difícil resolver estas ecuaciones de programación dinámica. La situación se simplifica drásticamente si el proceso es independiente por etapas, es decir, es (estocásticamente) independiente de para . En este caso, las expectativas condicionales correspondientes se convierten en expectativas incondicionales y la función , no depende de . Es decir, es el valor óptimo del problema ${\displaystyle \xi _{t}}$ ${\displaystyle \xi _{t}}$ ${\displaystyle \xi _{t}}$ ${\displaystyle \xi _{1},\dots ,\xi _{t-1}}$ ${\displaystyle t=2,\dots ,T}$ ${\displaystyle Q_{t}(W_{t})}$ ${\displaystyle t=1,\dots ,T-1}$ ${\displaystyle \xi _{[t]}}$ ${\displaystyle Q_{T-1}(W_{T-1})}$

${\displaystyle {\begin{array}{lrclr}\max \limits _{x_{T-1}}&E[U(W_{T})]&\\{\text{subject to}}&W_{T}&=&\sum _{i=1}^{n}\xi _{iT}x_{i,T-1}\\&\sum _{i=1}^{n}x_{i,T-1}&=&W_{T-1}\\&x_{T-1}&\geq &0\end{array}}}$

y es el valor óptimo de ${\displaystyle Q_{t}(W_{t})}$

${\displaystyle {\begin{array}{lrclr}\max \limits _{x_{t}}&E[Q_{t+1}(W_{t+1})]&\\{\text{subject to}}&W_{t+1}&=&\sum _{i=1}^{n}\xi _{i,t+1}x_{i,t}\\&\sum _{i=1}^{n}x_{i,t}&=&W_{t}\\&x_{t}&\geq &0\end{array}}}$

para . ${\displaystyle t=T-2,\dots ,1}$

Herramientas de software

Lenguajes de modelado

Todos los problemas de programación estocástica discreta pueden representarse con cualquier lenguaje de modelado algebraico , implementando manualmente la no anticipatividad explícita o implícita para asegurarse de que el modelo resultante respete la estructura de la información disponible en cada etapa. Una instancia de un problema SP generado por un lenguaje de modelado general tiende a crecer bastante (linealmente en el número de escenarios), y su matriz pierde la estructura que es intrínseca a esta clase de problemas, que de otro modo podría ser explotada en el momento de la solución por algoritmos de descomposición específicos. Están comenzando a aparecer extensiones a lenguajes de modelado diseñados específicamente para SP, consulte:

• AIMMS - apoya la definición de problemas SP
• EMP SP (Programación matemática extendida para programación estocástica): un módulo de GAMS creado para facilitar la programación estocástica (incluye palabras clave para distribuciones paramétricas, restricciones de azar y medidas de riesgo como valor en riesgo y déficit esperado ).
• SAMPL : un conjunto de extensiones de AMPL diseñadas específicamente para expresar programas estocásticos (incluye sintaxis para restricciones de azar, restricciones de azar integradas y problemas de optimización robusta )

Ambos pueden generar un formato de nivel de instancia SMPS, que transmite de forma no redundante la estructura del problema al solucionador.

Véase también

• Selección de carteras sujeta a restricciones de azar
• Brecha de correlación
• EMP para programación estocástica
• El valor entrópico en riesgo
• Fuerte SP
• Lenguaje de modelado algebraico SAMPL
• Optimización de escenarios
• Optimización estocástica

Referencias

1. Shapiro, Alexander; Dentcheva, Darinka ; Ruszczyński, Andrzej (2009). Lecciones sobre programación estocástica: modelado y teoría (PDF) . Serie MPS/SIAM sobre optimización. Vol. 9. Filadelfia, PA: Sociedad de Matemáticas Industriales y Aplicadas (SIAM). pp. xvi+436. ISBN 978-0-89871-687-0. MR  2562798. Archivado desde el original (PDF) el 24 de marzo de 2020. Consultado el 22 de septiembre de 2010 . {{cite book}}: Parámetro desconocido |agency=ignorado ( ayuda )
2. Birge, John R.; Louveaux, François (2011). Introducción a la programación estocástica. Springer Series in Operations Research and Financial Engineering. doi :10.1007/978-1-4614-0237-4. ISBN 978-1-4614-0236-7. ISSN  1431-8598.
3. Stein W. Wallace y William T. Ziemba (eds.). Aplicaciones de la programación estocástica . Serie de libros MPS-SIAM sobre optimización 5, 2005.
4. Las aplicaciones de la programación estocástica se describen en el siguiente sitio web, Comunidad de Programación Estocástica.
5. Shapiro, Alexander; Philpott, Andy. Un tutorial sobre programación estocástica (PDF) .
6. "Servidor NEOS para optimización".
7. Ruszczyński, Andrzej ; Shapiro, Alexander (2003). Programación estocástica . Manuales de investigación de operaciones y ciencia de la gestión. Vol. 10. Filadelfia: Elsevier . p. 700. ISBN 978-0444508546.
8. Mangel, M. y Clark, CW 1988. Modelado dinámico en ecología del comportamiento. Princeton University Press ISBN 0-691-08506-4 
9. Houston, A. I y McNamara, JM 1999. Modelos de comportamiento adaptativo: un enfoque basado en el estado . Cambridge University Press ISBN 0-521-65539-0 
10. Howitt, R., Msangi, S., Reynaud, A y K. Knapp. 2002. "Uso de aproximaciones polinomiales para resolver problemas de programación dinámica estocástica: o un enfoque "Betty Crocker" para SDP". Universidad de California, Davis, Departamento de Economía Agrícola y de Recursos, Documento de trabajo.

Lectura adicional

• John R. Birge y François V. Louveaux. Introducción a la programación estocástica . Springer Verlag, Nueva York, 1997.
• Kall, Peter; Wallace, Stein W. (1994). Programación estocástica. Serie Wiley-Interscience en sistemas y optimización. Chichester: John Wiley & Sons, Ltd., págs. xii+307. ISBN 0-471-95158-7.Señor 1315300  .
• G. Ch. Pflug: Optimización de modelos estocásticos. La interfaz entre simulación y optimización . Kluwer, Dordrecht, 1996.
• András Prekopa . Programación estocástica. Editorial académica Kluwer, Dordrecht, 1995.
• Andrzej Ruszczynski y Alexander Shapiro (eds.) (2003) Programación estocástica . Manuales de investigación de operaciones y ciencia de la gestión, vol. 10, Elsevier.
• Shapiro, Alexander; Dentcheva, Darinka ; Ruszczyński, Andrzej (2009). Lecciones sobre programación estocástica: modelado y teoría (PDF) . Serie MPS/SIAM sobre optimización. Vol. 9. Filadelfia, PA: Sociedad de Matemáticas Industriales y Aplicadas (SIAM). pp. xvi+436. ISBN 978-0-89871-687-0. MR  2562798. Archivado desde el original (PDF) el 24 de marzo de 2020. Consultado el 22 de septiembre de 2010 . {{cite book}}: Parámetro desconocido |agency=ignorado ( ayuda )
• Stein W. Wallace y William T. Ziemba (eds.) (2005) Aplicaciones de la programación estocástica . Serie de libros MPS-SIAM sobre optimización 5
• King, Alan J.; Wallace, Stein W. (2012). Modelado con programación estocástica. Springer Series in Operations Research and Financial Engineering. Nueva York: Springer. ISBN 978-0-387-87816-4.

Enlaces externos

• Página de inicio de la comunidad de programación estocástica