Programação estocástica - Stochastic programming

No campo da otimização matemática , a programação estocástica é uma estrutura para modelar problemas de otimização que envolvem incerteza . Um programa estocástico é um problema de otimização em que alguns ou todos os parâmetros do problema são incertos, mas seguem distribuições de probabilidade conhecidas . Essa estrutura contrasta com a otimização determinística, na qual todos os parâmetros do problema são considerados conhecidos com exatidão. O objetivo da programação estocástica é encontrar uma decisão que otimize alguns critérios escolhidos pelo tomador de decisão e leve em consideração a incerteza dos parâmetros do problema. Como muitas decisões do mundo real envolvem incerteza, a programação estocástica encontrou aplicações em uma ampla gama de áreas, desde finanças a transporte e otimização de energia.

Problemas de duas fases

A ideia básica da programação estocástica de dois estágios é que as decisões (ótimas) devem ser baseadas nos dados disponíveis no momento em que as decisões são tomadas e não podem depender de observações futuras. A formulação de dois estágios é amplamente usada na programação estocástica. A formulação geral de um problema de programação estocástica de dois estágios é dada por:

onde está o valor ideal do problema de segundo estágio ${\ displaystyle Q (x, \ xi)}$

Os problemas clássicos de programação estocástica linear de dois estágios podem ser formulados como

onde está o valor ideal do problema de segundo estágio ${\ displaystyle Q (x, \ xi)}$

Em tal formulação está o vetor de variável de decisão de primeiro estágio, é o vetor de variável de decisão de segundo estágio e contém os dados do problema de segundo estágio. Nesta formulação, no primeiro estágio, temos que tomar uma decisão "aqui e agora" antes que a realização dos dados incertos , vistos como um vetor aleatório, seja conhecida. No segundo estágio, após uma realização de torna-se disponível, otimizamos nosso comportamento resolvendo um problema de otimização apropriado. ${\ displaystyle x \ in \ mathbb {R} ^ {n}}$${\ displaystyle y \ in \ mathbb {R} ^ {m}}$${\ displaystyle \ xi (q, T, W, h)}$${\ displaystyle x}$${\ displaystyle \ xi}$${\ displaystyle \ xi}$

No primeiro estágio, otimizamos (minimizamos na formulação acima) o custo da decisão do primeiro estágio mais o custo esperado da decisão (ótima) do segundo estágio. Podemos ver o problema de segundo estágio simplesmente como um problema de otimização que descreve nosso comportamento supostamente ótimo quando os dados incertos são revelados, ou podemos considerar sua solução como uma ação de recurso onde o termo compensa uma possível inconsistência do sistema e é o custo desta ação de recurso. ${\ displaystyle c ^ {T} x}$${\ displaystyle Wy}$${\ displaystyle Tx \ leq h}$${\ displaystyle q ^ {T} y}$

O problema de dois estágios considerado é linear porque as funções objetivo e as restrições são lineares. Conceitualmente, isso não é essencial e pode-se considerar programas estocásticos de dois estágios mais gerais. Por exemplo, se o problema do primeiro estágio for inteiro, pode-se adicionar restrições de integralidade ao problema do primeiro estágio para que o conjunto viável seja discreto. Objetivos e restrições não lineares também podem ser incorporados, se necessário.

Suposição distributiva

A formulação do problema de dois estágios acima assume que os dados do segundo estágio podem ser modelados como um vetor aleatório com uma distribuição de probabilidade conhecida (não apenas incerta). Isso seria justificado em muitas situações. Por exemplo, podem ser informações derivadas de dados históricos e a distribuição não muda significativamente durante o período de tempo considerado. Em tais situações, pode-se estimar com segurança a distribuição de probabilidade necessária e a otimização na média pode ser justificada pela lei dos grandes números . Outro exemplo é que podem ser realizações de um modelo de simulação cujas saídas são estocásticas. A distribuição empírica da amostra pode ser usada como uma aproximação para a distribuição de saída verdadeira, mas desconhecida. ${\ displaystyle \ xi}$${\ displaystyle \ xi}$${\ displaystyle \ xi}$

Discretização

Para resolver numericamente o problema estocástico de dois estágios, muitas vezes é necessário supor que o vetor aleatório tem um número finito de realizações possíveis, chamadas de cenários , digamos , com as respectivas massas de probabilidade . Então, a expectativa na função objetivo do problema de primeiro estágio pode ser escrita como a soma: ${\ displaystyle \ xi}$${\ displaystyle \ xi _ {1}, \ dots, \ xi _ {K}}$${\ displaystyle p_ {1}, \ dots, p_ {K}}$

e, além disso, o problema de dois estágios pode ser formulado como um grande problema de programação linear (isso é chamado de equivalente determinístico do problema original, consulte a seção § Equivalente determinístico de um problema estocástico ).

Quando há um número infinito (ou muito grande) de realizações possíveis, a abordagem padrão é então representar essa distribuição por cenários. Essa abordagem levanta três questões, a saber: ${\ displaystyle \ xi}$

1. Como construir cenários, consulte § Construção de cenários ;
2. Como resolver o equivalente determinístico. Otimizadores como CPLEX , GLPK e Gurobi podem resolver grandes problemas lineares / não lineares. O NEOS Server, hospedado na University of Wisconsin, Madison , permite acesso gratuito a muitos solucionadores modernos. A estrutura de um equivalente determinístico é particularmente favorável à aplicação de métodos de decomposição, como a decomposição de Benders ou a decomposição de cenário;
3. Como medir a qualidade da solução obtida em relação ao "verdadeiro" ótimo.

Essas perguntas não são independentes. Por exemplo, o número de cenários construídos afetará a tratabilidade do equivalente determinístico e a qualidade das soluções obtidas.

Programação linear estocástica

Um programa linear estocástico é uma instância específica do programa estocástico clássico de dois estágios. Um LP estocástico é construído a partir de uma coleção de programas lineares de vários períodos (LPs), cada um com a mesma estrutura, mas com dados um tanto diferentes. O LP de dois períodos, representando o cenário, pode ser considerado como tendo a seguinte forma: ${\ displaystyle k ^ {th}}$${\ displaystyle k ^ {th}}$

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

Os vetores e contêm as variáveis ​​do primeiro período, cujos valores devem ser escolhidos imediatamente. O vetor contém todas as variáveis ​​para os períodos subsequentes. As restrições envolvem apenas variáveis ​​do primeiro período e são as mesmas em todos os cenários. As outras restrições envolvem variáveis ​​de períodos posteriores e diferem em alguns aspectos de cenário para cenário, refletindo a incerteza sobre o futuro. ${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle z_ {k}}$${\ displaystyle Tx + Uy = r}$

Observe que resolver a LP de dois períodos é equivalente a assumir o cenário no segundo período sem incerteza. Para incorporar as incertezas na segunda etapa, deve-se atribuir probabilidades a diferentes cenários e resolver o equivalente determinístico correspondente. ${\ displaystyle k ^ {th}}$${\ displaystyle k ^ {th}}$

Equivalente determinístico de um problema estocástico

Com um número finito de cenários, programas lineares estocásticos de dois estágios podem ser modelados como grandes problemas de programação linear. Esta formulação é freqüentemente chamada de programa linear equivalente determinístico ou abreviada para equivalente determinístico. (Estritamente falando, um equivalente determinístico é qualquer programa matemático que pode ser usado para calcular a decisão ótima do primeiro estágio, então eles também existirão para distribuições de probabilidade contínuas, quando se pode representar o custo do segundo estágio de alguma forma fechada.) Por exemplo, para formar o equivalente determinístico ao programa linear estocástico acima, atribuímos uma probabilidade a cada cenário . Então, podemos minimizar o valor esperado do objetivo, sujeito às restrições de todos os cenários: ${\ 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 {sujeito a}} & 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}}}$

Temos um vetor diferente de variáveis ​​de período posterior para cada cenário . As variáveis do primeiro período e são os mesmos em todos os cenários, no entanto, porque temos de tomar uma decisão para o primeiro período antes de sabermos qual o cenário será realizado. Como resultado, as restrições envolvendo apenas e precisam ser especificadas apenas uma vez, enquanto as restrições restantes devem ser fornecidas separadamente para cada cenário. ${\ displaystyle z_ {k}}$${\ displaystyle k}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle x}$${\ displaystyle y}$

Construção de cenário

Na prática, pode ser possível construir cenários evocando opiniões de especialistas sobre o futuro. O número de cenários construídos deve ser relativamente modesto para que o equivalente determinístico obtido possa ser resolvido com razoável esforço computacional. Freqüentemente, afirma-se que uma solução que é ótima usando apenas alguns cenários fornece planos mais adaptáveis ​​do que uma que assume apenas um único cenário. Em alguns casos, tal afirmação pode ser verificada por uma simulação. Em teoria, algumas medidas garantem que uma solução obtida resolva o problema original com razoável precisão. Normalmente, em aplicativos, apenas a solução ótima de primeiro estágio tem um valor prático, pois quase sempre uma realização "verdadeira" dos dados aleatórios será diferente do conjunto de cenários construídos (gerados). ${\ displaystyle x ^ {*}}$

Suponha que contenha componentes aleatórios independentes, cada um dos quais com três realizações possíveis (por exemplo, realizações futuras de cada parâmetro aleatório são classificadas como baixa, média e alta), então o número total de cenários é . Esse crescimento exponencial do número de cenários torna o desenvolvimento do modelo usando a opinião de especialistas muito difícil, mesmo para um tamanho razoável . A situação fica ainda pior se alguns componentes aleatórios de tiverem distribuições contínuas. ${\ displaystyle \ xi}$${\ displaystyle d}$${\ displaystyle K = 3 ^ {d}}$${\ displaystyle d}$${\ displaystyle \ xi}$

Amostragem Monte Carlo e Método de Aproximação Média da Amostra (SAA)

Uma abordagem comum para reduzir o cenário definido a um tamanho gerenciável é usar a simulação de Monte Carlo. Suponha que o número total de cenários seja muito grande ou mesmo infinito. Suponha ainda que possamos gerar uma amostra de replicações do vetor aleatório . Normalmente, a amostra é considerada independente e identicamente distribuída (amostra iid). Dada uma amostra, a função de expectativa é aproximada pela média da amostra ${\ 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} )}$

e, conseqüentemente, o problema do primeiro estágio é 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 {sujeito a}} & Ax & = & b \\ && x & \ geq & 0 \ end {array}}}$

Esta formulação é conhecida como método de aproximação da média da amostra . O problema SAA é função da amostra considerada e, nesse sentido, é aleatório. Para uma dada amostra, o problema SAA é da mesma forma que um problema de programação linear estocástica de dois estágios com os cenários . ,, Cada um considerado com a mesma probabilidade . ${\ displaystyle \ xi ^ {1}, \ xi ^ {2}, \ dots, \ xi ^ {N}}$${\ displaystyle \ xi ^ {j}}$${\ displaystyle j = 1, \ dots, N}$${\ displaystyle p_ {j} = {\ frac {1} {N}}}$

Inferência estatística

Considere o seguinte problema de programação estocástica

Aqui está um subconjunto fechado não vazio de , é um vetor aleatório cuja distribuição de probabilidade é suportada em um conjunto , e . Na estrutura da programação estocástica de dois estágios, é dado pelo valor ótimo do problema de segundo estágio correspondente. ${\ 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)}$

Suponha que seja bem definido e com valor finito para todos . Isso implica que, para cada um, o valor é quase certamente finito. ${\ displaystyle g (x)}$${\ displaystyle x \ in X}$${\ displaystyle x \ in X}$${\ displaystyle Q (x, \ xi)}$

Suponha que temos uma amostra de realizações do vetor aleatório . Esta amostra aleatória pode ser vista como dados históricos de observações ou pode ser gerada por técnicas de amostragem de Monte Carlo. Então, podemos formular uma aproximação da média da amostra correspondente${\ displaystyle \ xi ^ {1}, \ dots, \ xi ^ {N}}$${\ displaystyle N}$${\ displaystyle \ xi}$${\ displaystyle N}$${\ displaystyle \ xi}$

Pela Lei dos Grandes Números temos que, sob algumas condições de regularidade converge pontualmente com probabilidade 1 a como . Além disso, sob condições adicionais suaves, a convergência é uniforme. Também temos , ou seja, é um estimador imparcial de . Portanto, é natural esperar que o valor ótimo e as soluções ótimas do problema SAA convirjam para suas contrapartes do problema verdadeiro 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}$

Consistência de estimadores SAA

Suponha que o conjunto viável do problema SAA seja corrigido, ou seja, independente da amostra. Seja e o valor ótimo e o conjunto de soluções ótimas, respectivamente, do problema verdadeiro e seja e seja o valor ótimo e o conjunto de soluções ótimas, respectivamente, do problema SAA. ${\ displaystyle X}$${\ displaystyle \ vartheta ^ {*}}$${\ displaystyle S ^ {*}}$${\ displaystyle {\ hat {\ vartheta}} _ {N}}$${\ displaystyle {\ hat {S}} _ {N}}$

1. Deixe e seja uma sequência de funções reais (determinísticas) com valor real. As duas propriedades a seguir são equivalentes: ${\ displaystyle g: X \ rightarrow \ mathbb {R}}$${\ displaystyle {\ hat {g}} _ {N}: X \ rightarrow \ mathbb {R}}$
   • para toda e qualquer sequência convergindo para ela segue-se que converge para${\ displaystyle {\ overline {x}} \ in X}$${\ displaystyle \ {x_ {N} \} \ subconjunto X}$${\ displaystyle {\ overline {x}}}$${\ displaystyle {\ hat {g}} _ {N} (x_ {N})}$${\ displaystyle g ({\ overline {x}})}$
   • a função é contínua e converge uniformemente em qualquer subconjunto compacto de${\ displaystyle g (\ cdot)}$${\ displaystyle X}$${\ displaystyle {\ hat {g}} _ {N} (\ cdot)}$${\ displaystyle g (\ cdot)}$${\ displaystyle X}$
2. Se o objetivo do problema SAA converge para o objetivo do problema verdadeiro com probabilidade 1, como , uniformemente no conjunto viável . Em seguida, converge para com probabilidade 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. Suponha que exista um conjunto compacto tal que ${\ displaystyle C \ subset \ mathbb {R} ^ {n}}$
   • o conjunto de soluções ótimas do verdadeiro problema não é vazio e está contido em${\ displaystyle S}$${\ displaystyle C}$
   • a função é de valor finito e contínua em${\ displaystyle g (x)}$${\ displaystyle C}$
   • a sequência de funções converge para com probabilidade 1, pois , uniformemente em${\ displaystyle {\ hat {g}} _ {N} (x)}$${\ displaystyle g (x)}$${\ displaystyle N \ rightarrow \ infty}$${\ displaystyle x \ in C}$
   • para grande o suficiente, o conjunto não é vazio e com probabilidade 1${\ displaystyle N}$${\ displaystyle {\ hat {S}} _ {N}}$${\ displaystyle {\ hat {S}} _ {N} \ subconjunto C}$

então e com probabilidade 1 como . Observe que denota o desvio de conjunto em relação ao conjunto , definido 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}$

Em algumas situações, o conjunto viável do problema de SAA é estimado, então o problema de SAA correspondente assume a forma ${\ displaystyle X}$

onde é um subconjunto de dependendo da amostra e, portanto, é aleatório. No entanto, os resultados de consistência para estimadores SAA ainda podem ser derivados sob algumas suposições adicionais: ${\ displaystyle X_ {N}}$${\ displaystyle \ mathbb {R} ^ {n}}$

1. Suponha que exista um conjunto compacto tal que ${\ displaystyle C \ subset \ mathbb {R} ^ {n}}$
   • o conjunto de soluções ótimas do verdadeiro problema não é vazio e está contido em${\ displaystyle S}$${\ displaystyle C}$
   • a função é de valor finito e contínua em${\ displaystyle g (x)}$${\ displaystyle C}$
   • a sequência de funções converge para com probabilidade 1, pois , uniformemente em${\ displaystyle {\ hat {g}} _ {N} (x)}$${\ displaystyle g (x)}$${\ displaystyle N \ rightarrow \ infty}$${\ displaystyle x \ in C}$
   • para grande o suficiente, o conjunto não é vazio e com probabilidade 1${\ displaystyle N}$${\ displaystyle {\ hat {S}} _ {N}}$${\ displaystyle {\ hat {S}} _ {N} \ subconjunto C}$
   • se e converge com probabilidade 1 para um ponto , então${\ displaystyle x_ {N} \ in X_ {N}}$${\ displaystyle x_ {N}}$${\ displaystyle x}$${\ displaystyle x \ in X}$
   • para algum ponto existe uma sequência tal que com probabilidade 1.${\ displaystyle x \ in S ^ {*}}$${\ displaystyle x_ {N} \ in X_ {N}}$${\ displaystyle x_ {N} \ rightarrow x}$

então e com probabilidade 1 como .${\ displaystyle {\ hat {\ vartheta}} _ {N} \ rightarrow \ vartheta ^ {*}}$${\ displaystyle \ mathbb {D} (S ^ {*}, {\ hat {S}} _ {N}) \ rightarrow 0}$${\ displaystyle N \ rightarrow \ infty}$

Assintóticos do valor ótimo SAA

Suponha que a amostra seja iid e fixe um ponto . Então, o estimador da média da amostra , de , é imparcial e tem variância , onde é suposto ser finito. Além disso, pelo teorema do limite central , temos 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)]}$

onde denota convergência na distribuição e tem uma distribuição normal com média e variância , escrita como . ${\ displaystyle {\ xrightarrow {\ mathcal {D}}}}$${\ displaystyle Y_ {x}}$${\ displaystyle 0}$${\ displaystyle \ sigma ^ {2} (x)}$${\ displaystyle {\ mathcal {N}} (0, \ sigma ^ {2} (x))}$

Em outras palavras, tem distribuição assintoticamente normal , ou seja, para o grande , tem distribuição aproximadamente normal com média e variância . Isso leva ao seguinte (aproximado) intervalo de confiança de% 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)}$

onde (aqui denota o cdf da distribuição normal padrão) e ${\ displaystyle z _ {\ alpha / 2}: = \ Phi ^ {- 1} (1- \ alpha / 2)}$${\ displaystyle \ Phi (\ cdot)}$

é a estimativa da variância da amostra de . Ou seja, o erro de estimativa de é (estocasticamente) de ordem . ${\ displaystyle \ sigma ^ {2} (x)}$${\ displaystyle g (x)}$${\ displaystyle O ({\ sqrt {N}})}$

Aplicações e exemplos

Aplicações biológicas

A programação dinâmica estocástica é freqüentemente usada para modelar o comportamento animal em campos como ecologia comportamental . Testes empíricos de modelos de forrageamento ideal , transições de história de vida , como emplumação em pássaros e postura de ovos em vespas parasitóides , mostraram o valor dessa técnica de modelagem para explicar a evolução da tomada de decisão comportamental. Normalmente, esses modelos têm vários estágios, em vez de dois estágios.

Aplicações econômicas

A programação dinâmica estocástica é uma ferramenta útil na compreensão da tomada de decisão sob incerteza. A acumulação de estoque de capital sob incerteza é um exemplo; frequentemente é usado por economistas de recursos para analisar problemas bioeconômicos onde a incerteza entra, como clima, etc.

Exemplo: otimização de portfólio em vários estágios

A seguir está um exemplo de finanças de programação estocástica de vários estágios. Suponha que no momento temos capital inicial para investir em ativos. Suponha ainda que possamos reequilibrar nosso portfólio às vezes, mas sem injetar dinheiro adicional nele. Em cada período , tomamos uma decisão sobre redistribuir a riqueza atual entre os ativos. Sejam os valores iniciais investidos nos n ativos. Exigimos que cada um seja não negativo e que a equação de equilíbrio se mantenha. ${\ 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 os retornos totais para cada período . Isso forma um processo aleatório com valor vetorial . No período de tempo , podemos reequilibrar a carteira especificando os valores investidos nos respectivos ativos. Nessa altura, os retornos do primeiro período foram realizados, pelo que é razoável utilizar esta informação na decisão de rebalanceamento. Assim, as decisões de segundo estágio, no momento , são na verdade funções de realização do vetor aleatório , ou seja ,. Da mesma forma, no momento a decisão é função das informações disponíveis fornecidas pelo histórico do processo aleatório até o momento . Uma sequência de funções , por ser constante, define uma política implementável do processo de decisão. Diz-se que tal política um é viável desde que preencha os constrangimentos modelo com probabilidade 1, ou seja, as restrições de não negatividade , , , eo saldo de restrições 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},}$

onde no período a riqueza é 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 da realização do processo aleatório e das decisões até o momento . ${\ displaystyle t}$

Suponha que o objetivo seja maximizar a utilidade esperada dessa riqueza no último período, ou seja, considerar o problema

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

Este é um problema de programação estocástica de múltiplos estágios, onde os estágios são numerados de a . A otimização é realizada em todas as políticas implementáveis ​​e viáveis. Para completar a descrição do problema, também é necessário definir a distribuição de probabilidade do processo aleatório . Isso pode ser feito de várias maneiras. Por exemplo, pode-se construir uma árvore de cenário particular definindo a evolução temporal do processo. Se em cada estágio o retorno aleatório de cada ativo puder ter duas continuações, independentes de outros ativos, então o número total de cenários é${\ displaystyle t = 0}$${\ displaystyle t = T-1}$${\ displaystyle \ xi _ {1}, \ dots, \ xi _ {T}}$${\ displaystyle 2 ^ {nT}.}$

Para escrever equações de programação dinâmica , considere o problema de vários estágios acima, retrocedendo no tempo. No último estágio , uma realização do processo aleatório é conhecida e escolhida. Portanto, é necessário resolver o seguinte 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 {sujeito a}} & 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}}}$

onde denota a expectativa condicional de dado . O valor ideal do problema acima depende de e e é denotado . ${\ 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]})}$

Da mesma forma, em etapas , deve-se resolver o 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 {sujeito a}} & 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} }}$

cujo valor ideal é denotado por . Finalmente, no estágio , um resolve o 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]})] & \\ {\ texto {sujeito a}} & 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}}}$

Processo aleatório independente de estágio

Para uma distribuição geral do processo , pode ser difícil resolver essas equações de programação dinâmica. A situação se simplifica dramaticamente se o processo for independente do estágio, ou seja, (estocasticamente) independente de for . Neste caso, as correspondentes expectativas condicionais tornar expectativas incondicionais, e a função , não depende . Ou seja, é o valor ideal do 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 {sujeito a}} & 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}}}$

e é o valor ideal de ${\ displaystyle Q_ {t} (W_ {t})}$

${\ displaystyle {\ begin {array} {lrclr} \ max \ limits _ {x_ {t}} & E [Q_ {t + 1} (W_ {t + 1})] & \\ {\ text {sujeito a} } & 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}$

Ferramentas de software

Linguagens de modelagem

Todos os problemas de programação estocástica discreta podem ser representados com qualquer linguagem de modelagem algébrica , implementando manualmente a não antecipatividade explícita ou implícita para garantir que o modelo resultante respeite a estrutura da informação disponibilizada em cada estágio. Uma instância de um problema SP gerado por uma linguagem de modelagem geral tende a crescer bastante (linearmente no número de cenários), e sua matriz perde a estrutura que é intrínseca a esta classe de problemas, que de outra forma poderia ser explorada no momento da solução por algoritmos de decomposição específicos. Extensões para linguagens de modelagem projetadas especificamente para SP estão começando a aparecer, consulte:

• AIMMS - suporta a definição de problemas de SP
• EMP SP (Extended Mathematical Programming for Stochastic Programming) - um módulo do GAMS criado para facilitar a programação estocástica (inclui palavras-chave para distribuições paramétricas, restrições de chance e medidas de risco, como valor em risco e déficit esperado ).
• SAMPL - um conjunto de extensões para AMPL projetado especificamente para expressar programas estocásticos (inclui sintaxe para restrições de chance, restrições de chance integradas e problemas de otimização robusta )

Ambos podem gerar o formato de nível de instância SMPS, que transmite de forma não redundante a estrutura do problema ao solucionador.

Veja também

• Lacuna de correlação
• EMP para programação estocástica
• Valor entrópico em risco
• FortSP
• Linguagem de modelagem algébrica SAMPL
• Otimização de cenário
• Otimização estocástica
• Seleção de portfólio com restrição de chance

Referências

Leitura adicional

• John R. Birge e François V. Louveaux. Introdução à Programação Estocástica . Springer Verlag, Nova York, 1997.
• Kall, Peter; Wallace, Stein W. (1994). Programação estocástica . Série Wiley-Interscience em Sistemas e Otimização. Chichester: John Wiley & Sons, Ltd. pp. Xii + 307. ISBN 0-471-95158-7. MR  1315300 .
• G. Ch. Pflug: Otimização de Modelos Estocásticos. A interface entre simulação e otimização . Kluwer, Dordrecht, 1996.
• András Prékopa . Programação estocástica. Kluwer Academic Publishers, Dordrecht, 1995.
• Andrzej Ruszczynski e Alexander Shapiro (eds.) (2003) Stochastic Programming . Handbooks in Operations Research and Management Science, vol. 10, Elsevier.
• Shapiro, Alexander; Dentcheva, Darinka ; Ruszczyński, Andrzej (2009). Aulas teóricas de programação estocástica: Modelação e teoria (PDF) . Série MPS / SIAM sobre otimização. 9 . Filadélfia, PA: Society for Industrial and Applied Mathematics (SIAM). Mathematical Programming Society (MPS). pp. xvi + 436. ISBN 978-0-89871-687-0. MR  2562798 .
• Stein W. Wallace e William T. Ziemba (eds.) (2005) Applications of Stochastic Programming . Série de livros MPS-SIAM sobre otimização 5
• King, Alan J .; Wallace, Stein W. (2012). Modelagem com Programação Estocástica . Série Springer em Pesquisa Operacional e Engenharia Financeira. Nova York: Springer. ISBN 978-0-387-87816-4.

links externos

• Página inicial da comunidade de programação estocástica