Programación estocástica

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 de los criterios elegidos por el responsable de la toma de decisiones y que dé cuenta de manera adecuada de la incertidumbre de los parámetros del problema. Debido a que muchas decisiones del mundo real implican 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]}

Problemas de 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 usa ampliamente en programación estocástica. La formulación general de un problema de programación estocástica de dos etapas viene dada por:

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

donde ${\displaystyle Q(x,\xi )}$ es el valor óptimo del problema de la segunda etapa

$${\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}}}$$

donde ${\displaystyle Q(x,\xi )}$ es el valor óptimo del problema de la segunda etapa

$${\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 tal formulación ${\displaystyle x\in \mathbb {R} ^{n}}$ es el vector variable de decisión de la primera etapa, ${\displaystyle y\in \mathbb {R} ^{m}}$ es el vector variable de decisión de la segunda etapa, y ${\displaystyle \xi (q,T,W,h)}$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"${\displaystyle x}$ antes de la realización de los datos inciertos ${\displaystyle \xi }$, visto como un vector aleatorio, se conoce. En la segunda etapa, después de una realización de${\displaystyle \xi }$ esté disponible, optimizamos nuestro comportamiento resolviendo un problema de optimización adecuado.

En la primera etapa optimizamos (minimizamos en la formulación anterior) el costo ${\displaystyle c^{T}x}$de la decisión de la primera etapa más el costo esperado de la decisión de la segunda etapa (óptima). Podemos ver 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${\displaystyle Wy}$ compensa una posible inconsistencia del sistema ${\displaystyle Tx\leq h}$ y ${\displaystyle q^{T}y}$ es el costo de esta acción de recurso.

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 un número 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 limitaciones 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 ${\displaystyle \xi }$se puede modelar como un vector aleatorio con una distribución de probabilidad conocida (no solo incierta). Esto estaría justificado en muchas situaciones. Por ejemplo,${\displaystyle \xi }$podría ser información derivada de datos históricos y la distribución no cambia significativamente durante el período de tiempo considerado. En tales situaciones, se puede estimar de manera confiable la distribución de probabilidad requerida y la optimización en promedio podría estar justificada por la ley de los grandes números . Otro ejemplo es que${\displaystyle \xi }$podrían ser realizaciones de un modelo de simulación cuyas salidas son estocásticas. La distribución empírica de la muestra podría usarse como una aproximación a la distribución de salida verdadera pero desconocida.

Discretización

Para resolver numéricamente el problema estocástico de dos etapas, a menudo es necesario suponer que el vector aleatorio ${\displaystyle \xi }$tiene un número finito de posibles realizaciones, llamadas escenarios , digamos${\displaystyle \xi _{1},\dots ,\xi _{K}}$, con respectivas masas de probabilidad ${\displaystyle p_{1},\dots ,p_{K}}$. Entonces, la expectativa en la función objetivo del problema de la primera etapa se puede escribir como la suma:

$${\displaystyle E[Q(x,\xi )]=\sum \limits _{k=1}^{K}p_{k}Q(x,\xi _{k})}$$

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, ver sección § Equivalente determinista de un problema estocástico ).

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

1. Cómo construir escenarios, ver § Construcción de escenarios ;
2. Cómo resolver el equivalente determinista. Los optimizadores como CPLEX , GLPK y Gurobi 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 de aplicar 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 "verdadero" óptimo.

Estas preguntas no son independientes. Por ejemplo, el número de escenarios construidos afectará tanto la manejabilidad del equivalente determinista como 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 LP estocástico se construye a partir de una colección de programas lineales de períodos múltiples (LP), cada uno con la misma estructura pero con datos algo diferentes. El${\displaystyle k^{th}}$ LP de dos períodos, que representa el ${\displaystyle k^{th}}$ escenario, puede considerarse que tiene la siguiente forma:

${\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 ${\displaystyle x}$ y ${\displaystyle y}$contienen las variables del primer período, cuyos valores deben elegirse inmediatamente. El vector${\displaystyle z_{k}}$contiene todas las variables para períodos posteriores. Las limitaciones${\displaystyle Tx+Uy=r}$involucran solo variables del primer período y son las mismas en todos los escenarios. Las otras restricciones involucran variables de períodos posteriores y difieren en algunos aspectos de un escenario a otro, lo que refleja la incertidumbre sobre el futuro.

Tenga en cuenta que resolver el ${\displaystyle k^{th}}$ LP de dos periodos es equivalente a asumir el ${\displaystyle k^{th}}$escenario en el segundo período sin incertidumbre. Para incorporar incertidumbres en la segunda etapa, se deben asignar probabilidades a diferentes escenarios y resolver el equivalente determinista correspondiente.

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 se abrevia como equivalente determinista. (Estrictamente hablando, un equivalente determinista es cualquier programa matemático que pueda usarse 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${\displaystyle p_{k}}$ a cada escenario ${\displaystyle k=1,\dots ,K}$. Entonces podemos minimizar el valor esperado del objetivo, sujeto a las restricciones de todos los escenarios:

${\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 ${\displaystyle z_{k}}$ de variables de período posterior para cada escenario ${\displaystyle k}$. Las variables del primer período${\displaystyle x}$ y ${\displaystyle y}$son los mismos en todos los escenarios, sin embargo, 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${\displaystyle x}$ y ${\displaystyle y}$ solo es necesario especificar una vez, mientras que las restricciones restantes deben indicarse por separado para cada escenario.

Construcción de escenarios

En la práctica, podría ser posible construir escenarios obteniendo opiniones 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 asume un solo escenario. En algunos casos, tal afirmación podría verificarse mediante una simulación. En teoría, algunas medidas garantizan que una solución obtenida resuelve el problema original con una precisión razonable. Por lo general, en aplicaciones solo la solución óptima de primera etapa${\displaystyle x^{*}}$ 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).

Suponer ${\displaystyle \xi }$ contiene ${\displaystyle d}$ 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 bajo, medio y alto), luego el número total de escenarios es ${\displaystyle K=3^{d}}$. 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.${\displaystyle d}$. La situación empeora aún más si algunos componentes aleatorios de${\displaystyle \xi }$ tienen distribuciones continuas.

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

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

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

y consecuentemente el problema de la primera etapa viene 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 el método de aproximación promedio de la muestra . El problema de SAA es una función de la muestra considerada y en ese sentido es aleatorio. Para una muestra dada${\displaystyle \xi ^{1},\xi ^{2},\dots ,\xi ^{N}}$ el problema de SAA tiene la misma forma que un problema de programación lineal estocástica de dos etapas con los escenarios ${\displaystyle \xi ^{j}}$., ${\displaystyle j=1,\dots ,N}$, cada uno tomado con la misma probabilidad ${\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í ${\displaystyle X}$ es un subconjunto cerrado no vacío de ${\displaystyle \mathbb {R} ^{n}}$, ${\displaystyle \xi }$ es un vector aleatorio cuya distribución de probabilidad ${\displaystyle P}$ es compatible con un conjunto ${\displaystyle \Xi \subset \mathbb {R} ^{d}}$, y ${\displaystyle Q:X\times \Xi \rightarrow \mathbb {R} }$. En el marco de la programación estocástica de dos etapas,${\displaystyle Q(x,\xi )}$ viene dado por el valor óptimo del correspondiente problema de segunda etapa.

Asumir que ${\displaystyle g(x)}$está bien definido y valorado de forma finita para todos${\displaystyle x\in X}$. Esto implica que para cada${\displaystyle x\in X}$ el valor ${\displaystyle Q(x,\xi )}$ es finito casi con seguridad.

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

${\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 algunas condiciones de regularidad${\displaystyle {\frac {1}{N}}\sum _{j=1}^{N}Q(x,\xi ^{j})}$ converge puntualmente con probabilidad 1 a ${\displaystyle E[Q(x,\xi )]}$ como ${\displaystyle N\rightarrow \infty }$. Además, en condiciones adicionales suaves, la convergencia es uniforme. También tenemos${\displaystyle E[{\hat {g}}_{N}(x)]=g(x)}$, es decir, ${\displaystyle {\hat {g}}_{N}(x)}$es un estimador insesgado de${\displaystyle g(x)}$. Por lo tanto, es natural esperar que el valor óptimo y las soluciones óptimas del problema SAA converjan con sus contrapartes del verdadero problema como${\displaystyle N\rightarrow \infty }$.

Consistencia de los estimadores de SAA

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

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

luego ${\displaystyle {\hat {\vartheta }}_{N}\rightarrow \vartheta ^{*}}$ y ${\displaystyle \mathbb {D} (S^{*},{\hat {S}}_{N})\rightarrow 0}$ con probabilidad 1 como ${\displaystyle N\rightarrow \infty }$. Tenga en cuenta que${\displaystyle \mathbb {D} (A,B)}$denota la desviación del conjunto${\displaystyle A}$ del set ${\displaystyle B}$, definido como

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

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

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

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

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

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

Asintóticas del valor óptimo de SAA

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

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

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

En otras palabras, ${\displaystyle {\hat {g}}_{N}(x)}$tiene una distribución asintóticamente normal , es decir, para grandes${\displaystyle N}$, ${\displaystyle {\hat {g}}_{N}(x)}$ tiene una distribución aproximadamente normal con media ${\displaystyle g(x)}$ y varianza ${\displaystyle {\frac {1}{N}}\sigma ^{2}(x)}$. Esto conduce a lo siguiente (aproximado)${\displaystyle 100(1-\alpha )}$% intervalo de confianza para ${\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 ${\displaystyle z_{\alpha /2}:=\Phi ^{-1}(1-\alpha /2)}$ (aquí ${\displaystyle \Phi (\cdot )}$ denota la CDF de la distribución normal estándar) y

${\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 ${\displaystyle \sigma ^{2}(x)}$. Es decir, el error de estimación de${\displaystyle g(x)}$ es (estocásticamente) de orden ${\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 forrajeo óptimo , transiciones de la historia de vida como el emplumado en aves y la puesta de huevos en 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 etapas.

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 social bajo incertidumbre es un ejemplo; a menudo es utilizado por economistas de recursos para analizar problemas bioeconómicos ^[10] donde entra la incertidumbre, como el clima, etc.

Ejemplo: optimización de cartera de varias etapas

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

Considere los retornos totales ${\displaystyle \xi _{t}=(\xi _{1t},\dots ,\xi _{nt})}$ para cada período ${\displaystyle t=1,\dots ,T}$. Esto forma un proceso aleatorio con valores vectoriales${\displaystyle \xi _{1},\dots ,\xi _{T}}$. En el período de tiempo${\displaystyle t=1}$, podemos reequilibrar la cartera especificando los importes ${\displaystyle x_{1}=(x_{11},\dots ,x_{n1})}$invertido en los respectivos activos. En ese momento, los rendimientos en el primer período se han realizado, 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${\displaystyle t=1}$, son en realidad funciones de realización del vector aleatorio ${\displaystyle \xi _{1}}$, es decir, ${\displaystyle x_{1}=x_{1}(\xi _{1})}$. Del mismo modo, en el momento${\displaystyle t}$ la decisión ${\displaystyle x_{t}=(x_{1t},\dots ,x_{nt})}$ es una función ${\displaystyle x_{t}=x_{t}(\xi _{[t]})}$ de la información disponible proporcionada por ${\displaystyle \xi _{[t]}=(\xi _{1},\dots ,\xi _{t})}$ la historia del proceso aleatorio hasta el momento ${\displaystyle t}$. Una secuencia de funciones${\displaystyle x_{t}=x_{t}(\xi _{[t]})}$, ${\displaystyle t=0,\dots ,T-1}$, con ${\displaystyle x_{0}}$siendo constante, define una política implementable del proceso de decisión. Se dice que tal política es factible si satisface las restricciones del modelo con probabilidad 1, es decir, las restricciones de no negatividad${\displaystyle x_{it}(\xi _{[t]})\geq 0}$, ${\displaystyle i=1,\dots ,n}$, ${\displaystyle t=0,\dots ,T-1}$y el equilibrio de las limitaciones de riqueza,

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

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

${\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 las decisiones hasta el momento ${\displaystyle t}$.

Suponga 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 se numeran desde ${\displaystyle t=0}$ para ${\displaystyle t=T-1}$. La optimización se realiza en todas las políticas factibles e implementables. Para completar la descripción del problema, también es necesario definir la distribución de probabilidad del proceso aleatorio.${\displaystyle \xi _{1},\dots ,\xi _{T}}$. 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 2^{nT}.}$

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

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

Del mismo modo, en etapas ${\displaystyle t=T-2,\dots ,1}$, uno debe resolver el problema

${\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 ${\displaystyle Q_{t}(W_{t},\xi _{[t]})}$. Finalmente, en la etapa${\displaystyle t=0}$, uno resuelve el problema

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

${\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 ${\displaystyle Q_{t}(W_{t})}$ es el valor óptimo de

${\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}}}$

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

Herramientas de software

Lenguajes de modelado

Todos los problemas de programación estocástica discreta se pueden representar 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 de 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 otra manera podría ser explotada en tiempo de solución por algoritmos de descomposición específicos. Están empezando a aparecer extensiones a lenguajes de modelado diseñados específicamente para SP, consulte:

• AIMMS : admite la definición de problemas de 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ñado 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.

Ver también

• Brecha de correlación
• EMP para programación estocástica
• Valor entrópico en riesgo
• FortSP
• Lenguaje de modelado algebraico SAMPL
• Optimización de escenarios
• Optimización estocástica
• Selección de cartera limitada por el azar

Referencias

1. Shapiro, Alexander; Dentcheva, Darinka ; Ruszczyński, Andrzej (2009). Conferencias sobre programación estocástica: Modelización y teoría (PDF) . Serie MPS / SIAM sobre optimización. 9 . Filadelfia, PA: Sociedad de Matemáticas Industriales y Aplicadas (SIAM). Sociedad de Programación Matemática (MPS). págs. xvi + 436. ISBN 978-0-89871-687-0. Señor  2562798 .
2. Birge, John R .; Louveaux, François (2011). Introducción a la programación estocástica . Serie Springer en Investigación de Operaciones e Ingeniería Financiera. 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. 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 Ciencias de la Gestión. 10 . Filadelfia: Elsevier . pag. 700. ISBN 978-0444508546.
8. Mangel, M. y Clark, CW 1988. Modelado dinámico en ecología del comportamiento. Prensa de la Universidad de Princeton 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 polinómicas para resolver problemas de programación dinámica estocástica: o un enfoque" Betty Crocker "para SDP". Universidad de California, Davis, Departamento de Agricultura y Economía de los 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 Prékopa . Programación estocástica. Editores Académicos Kluwer, Dordrecht, 1995.
• Andrzej Ruszczynski y Alexander Shapiro (eds.) (2003) Programación estocástica . Manuales de investigación operativa y ciencias de la gestión, vol. 10, Elsevier.
• Shapiro, Alexander; Dentcheva, Darinka ; Ruszczyński, Andrzej (2009). Conferencias sobre programación estocástica: Modelización y teoría (PDF) . Serie MPS / SIAM sobre optimización. 9 . Filadelfia, PA: Sociedad de Matemáticas Industriales y Aplicadas (SIAM). Sociedad de Programación Matemática (MPS). págs. xvi + 436. ISBN 978-0-89871-687-0. Señor  2562798 .
• 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 . Serie Springer en Investigación de Operaciones e Ingeniería Financiera. Nueva York: Springer. ISBN 978-0-387-87816-4.

Enlaces externos

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