확률적 프로그래밍

수학 최적화 분야에서 확률 프로그래밍은 불확실성을 수반하는 최적화 문제를 모델링하기 위한 프레임워크다. 확률적 프로그램은 일부 또는 모든 문제 매개변수가 불확실하지만 알려진 확률 분포를 따르는 최적화 문제다.^[1][2] 이 프레임워크는 모든 문제 매개변수가 정확히 알려진 것으로 가정되는 결정론적 최적화와 대비된다. 확률적 프로그래밍의 목적은 의사결정자가 선택한 일부 기준을 최적화하고, 문제 매개변수의 불확실성을 적절히 설명하는 결정을 찾는 것이다. 많은 실제 결정들이 불확실성을 수반하기 때문에, 확률적 프로그래밍은 금융에서 교통, 에너지 최적화까지 광범위한 영역에서 응용 프로그램을 발견했다.^[3][4]

2단계 문제

2단계 확률형 프로그래밍의 기본 개념은 (최적적) 결정은 의사결정이 이루어지는 시점에 이용 가능한 데이터에 기초해야 하며 향후 관찰에 의존할 수 없다는 것이다. 2단계 제형은 확률형 프로그래밍에 널리 사용된다. 2단계 확률형 프로그래밍 문제의 일반적인 공식화는 다음과 같다.

여기서 $Q{\displaystyle }$( ${\displaystyle x}$ ,${\displaystyle \xi }$) ${\displaystyle Q(x,\xi )}$는 2단계 문제의 최적 값이다.

고전적인 2단계 선형 확률적 프로그래밍 문제는 다음과 같이 공식화될 수 있다.

여기서 $Q{\displaystyle }$( ${\displaystyle x}$ ,${\displaystyle \xi }$) ${\displaystyle Q(x,\xi )}$는 2단계 문제의 최적 값이다.

In such formulation ${\displaystyle x\in \mathbb {R} ^{n}}$ is the first-stage decision variable vector, ${\displaystyle y\in \mathbb {R} ^{m}}$ is the second-stage decision variable vector, and ${\displaystyle \xi (q,T,W,h)}$ contains the data of the second-stage problem. 이 공식에서, 임의 벡터로 보이는$$불확실한 데이터 $\xi {\displaystyle }$ ${\displaystyle \xi}$의 실현이 알려지기 전에$$ 첫 번째 단계에서 우리는 "여기서 지금" $결정{\displaystyle }$ x ${\displaystyle x}$을 내려야 한다. 두 번째 단계에서는 $\xi {\displaystyle }$ ${\displaystyle \xi}$의 실현이 가능해진$$ 후, 적절한 최적화 문제를 해결하여 행동을 최적화한다.

첫 번째 단계에서 비용 $c{\displaystyle {}^{}}$ t ${\displaystyle {}^{}}$ ${\displaystyle c^{{$1단계 결정의$$ $T}x}$에 (최적) 2단계 결정의 예상 비용 추가. 우리는 2단계 문제를 단순히 불확실한 데이터가 드러날 때 우리의 최적의 행동을 설명하는 최적화 문제로 볼 수도 있고, ${\displaystyle \mathrm{Wy}}$ ${\displaystyle Wy}$라는 용어가 $시스템{\displaystyle }$ T x${\displaystyle x}$ h ${\displaystyle Tx\leq$h}의 가능한 불일치를$$ 보상하는 재청구 작업으로 고려할 수도 있다.$$ ${\displaystyle {}^{}}$ ${\displaystyle T^{}}$ y ${\displaystyle q^{$$T}y}$은(는) 이 상환 청구 조치의 비용이다.

객관적 기능과 제약조건이 선형이기 때문에 고려되는 2단계 문제는 선형이다. 개념적으로 이것은 필수적인 것이 아니며 더 일반적인 2단계 확률론 프로그램을 고려할 수 있다. 예를 들어 1단계 문제가 정수일 경우 1단계 문제에 통합성 제약조건을 추가하여 실현 가능한 집합이 분리되도록 할 수 있다. 필요한 경우 비선형 목표와 제약조건도 통합할 수 있다.^[5]

분포 가정

위의 2단계 문제의 공식화에서는 2단계 데이터 $\xi {\displaystyle }$ ${\displaystyle \xi}$을(를) 알려진 확률 분포의 랜덤 벡터로 모델링할 수 있다고$$ 가정한다. 이것은 많은 상황에서 정당화될 것이다. 예를 들어 $\xi {\displaystyle }$ ${\displaystyle \xi}$은(는) 과거 데이터에서 파생된 정보일 수 있으며$$, 해당 분포는 고려된 기간 동안 크게 변경되지 않는다. 그러한 상황에서는 요구되는 확률 분포를 신뢰성 있게 추정할 수 있으며 평균적으로 최적화는 대수의 법칙에 의해 정당화될 수 있다. 또 다른 예는 $outputs{\displaystyle }$ ${\displaystyle \xi}$이(가) 출력이 확률적인 시뮬레이션 모델의 실현일 수 있다는$$ 것이다. 표본의 경험적 분포는 참이지만 알 수 없는 출력 분포에 대한 근사치로 사용될 수 있다.

디스커트화

2단계 확률적 문제를 수치적으로 해결하려면 종종 무작위 벡터 $\xi {\displaystyle }$${\$$displaystyle$ $\xi}}$이(가) 시나리오라고 하는 가능한 실현의 수가 한정되어 있다고$$ 가정할 필요가 있는데, 이는 각각 ${\displaystyle {확률}_{}}$ $p$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle }$$,$ ${\displaystyle P_{}}$ ${\$}, P {\$dotsyty}$이다$.$$le p_{1},\dots,p_{K$ 그러면 1단계 문제의 객관적 기능에 대한 기대치를 다음과 같은 합계로 작성할 수 있다.

또한, 2단계 문제는 하나의 큰 선형 프로그래밍 문제로 공식화될 수 있다(이 문제를 원래 문제의 결정론적 등가라고 한다, 섹션 § 확률론적 문제의 결정론적 등가 참조).

$\xi {\displaystyle }$ ${\displaystyle \xi}$이(가) 무한(또는 매우 큰) 실현 수를 가질 경우$$ 표준 접근방식은 시나리오별로 이 분포를 나타내는 것이다. 이 접근방식은 세 가지 의문을 제기한다.

1. 시나리오를 작성하는 방법, § 시나리오 구조를 참조한다.
2. 결정론적 등가물을 해결하는 방법. CPLEX, GLPK와 같은 최적기는 큰 선형/비선형 문제를 해결할 수 있다. 매디슨 주 위스콘신 대학교에서 ^[6]주최하는 NEOS 서버는 많은 현대적인 해결사들에게 무료로 접근할 수 있다. 결정론적 등가물의 구조는 특히 벤더의 분해 또는 시나리오 ^[7]분해와 같은 분해 방법을 적용하기에 적합하다.
3. "진정한" 최적값에 대해 획득한 솔루션의 품질을 측정하는 방법.

이 질문들은 독립적이지 않다. 예를 들어, 구성된 시나리오의 수는 결정론적 등가의 추적성과 획득한 해결책의 품질 모두에 영향을 미칠 것이다.

확률적 선형 프로그래밍

확률적 선형 프로그램은 고전적인 2단계 확률적 프로그램의 특정한 예다. 확률형 LP는 다주기 선형 프로그램(LP)의 모음에서 만들어지며, 각각 구조는 같지만 데이터는 다소 다르다. $k{\displaystyle {}^{}}$ ${\displaystyle t^{}}$ ${\displaystyle h^{}}$ ${\$ k$^{th}}$ k ${\displaystyle t^{}}$ h ${\$ 시나리오를$$ 나타내는 2주기$$ LP는 다음과 같은 형태를 갖는 것으로 볼 수 있다.

${\displaystyle {\begin{array}{lccccccc}{\text{Minimize}&f^{T}x&+&g^{\displaysty}{lcccc}{\text{Minimize}T}y&+&h_{k}^{T}z_{k}&\\{\text{대상}}&&#{{text{대상}&#&#&#&#}&#&#&#&#&#&#&#Tx&+&uy&&&#&r\&r\&r\&#&v_{k}y&+&W_{k}z_{k}&s_{k}\&x&,&y&,&z_{k}>&#0\end{array}}}}}}}}}}$

벡터 $x{\displaystyle }$ ${\displaystyle x}$ $및$ y ${\displaystyle y}$에는 첫 번째 주기 변수가 포함되어$$ 있으며 이 변수는 즉시 값을 선택해야 한다. 벡터 $z{\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\$는 이후 기간에$$ 대한 모든 변수를 포함한다. 제한조건 $T{\displaystyle }$ ${\displaystyle x}$+ ${\displaystyle U}$ ${\displaystyle y}$= ${\displaystyle r}$ ${\displaystyle Tx+Uy=r}$은(는) 첫 번째 주기 변수만 포함하며$$ 모든 시나리오에서 동일하다. 다른 제약조건은 이후 기간의 변수를 포함하며 미래에 대한 불확실성을 반영하여 시나리오마다 일부 측면에서 다르다.

$k{\displaystyle {}^{}}$ ${\displaystyle t^{}}$ ${\displaystyle h^{}}$ ${\$ k$^{th}}$ 2주기$$ LP를 푸는 것은 불확실성 없이 k $t{\displaystyle {}^{}}$ ${\displaystyle h^{}}$ ${\$ 시나리오를$$ 2기로 가정하는 것과 같다는 점에 유의한다. 2단계에서 불확실성을 통합하기 위해서는 다른 시나리오에 확률을 할당하고 그에 상응하는 결정론적 등가물을 해결해야 한다.

확률적 문제에 대한 결정론적 등가

한정된 수의 시나리오로, 2단계 확률적 선형 프로그램은 큰 선형 프로그래밍 문제로 모델링될 수 있다. 이 공식은 흔히 결정론적 등가선형 프로그램 또는 결정론적 등가선형 프로그램으로 약칭된다.(결정론적 등가선형은 최적의 1단계 결정을 계산하는 데 사용할 수 있는 수학적 프로그램이기 때문에 이러한 프로그램들은 한 사람이 대표할 수 있는 경우 연속 확률분포에도 존재할 것이다.t 어떤 폐쇄형 형태의 2단계 비용) 예를 들어, 위의 확률적 선형 프로그램과 동등한 결정론적 형태를 형성하기 위해 ${\displaystyle \mathrm{확률}}$ ${\displaystyle p_{}}$ $k{\displaystyle {}_{}}$ ${\$를 각 시나리오 $k{\displaystyle }$= ${\displaystyle 1}$,${\displaystyle \dots ,}$ 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{대상}}&\{\text{pubject}}>>>>}>>>Tx&+&uy&&&&&&&&&&&&&&&&&&&>&r\\&&v_{1}y&+>>W_{1}z_{1}z_{1}&&&&&&&&&&=&s_{1}\\\&V_{2}y&&&+&#&#&#&#&#&#&#&#&#&#&#&#&#&#&#&#&#&#W_{2}z_{2}z_{2}&&&&&&&#••••••{K}y&&&&&&&&&&#&#&#&#&#&#&#&#&#&#&#&#&#&#&#&#&#&#&#&#&#&#&#&#&#&#&#&#&#&#W_{K}z_{K}z_{K}&s_{K}\\&x&,&y&,&z_{1}&,&z_{1}&,&z_{2},&&dots &,&z_{K}&\geq &0\\\\end{array}}}}}}}}}}}}}}}}?$

각 시나리오 $k{\displaystyle }$ ${\displaystyle k$에 대해 다른$$ 벡터 $z{\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\$}가 있다$.$ 그러나 첫 번째 주기 변수 $x{\displaystyle }$ ${\displaystyle x}$과 $y{\displaystyle }$ ${\displaystyle y}$은 모든 시나리오에서 동일하다$$. 어떤 시나리오가 실현될지 알기 전에 첫 번째 기간에 대한 결정을 내려야 하기 때문이다. $따라서{\displaystyle }$ x ${\displaystyle x}$ 및$$ $y{\displaystyle }$ ${\displaystyle y}$만 포함하는 제약조건은 한 번만 지정하면 되며$$, 나머지 제약조건은 각 시나리오별로 별도로 부여해야 한다.

시나리오 구성

실제로 미래에 대한 전문가들의 의견을 이끌어냄으로써 시나리오를 구성하는 것이 가능할 수 있다. 생성된 시나리오의 수는 얻어진 결정론적 등가물이 합리적인 계산 노력으로 해결될 수 있도록 상대적으로 적어야 한다. 단 몇 개의 시나리오만을 사용하여 최적화한 솔루션이 단일 시나리오만을 가정하는 솔루션보다 더 적응성 있는 계획을 제공한다고 주장하는 경우가 많다. 어떤 경우에는 시뮬레이션으로 그러한 청구를 확인할 수 있다. 이론적으로, 얻어진 해결책이 원래의 문제를 합리적인 정확도로 해결한다는 보장의 몇몇 척도가 있다. 일반적으로 애플리케이션에서는 1단계 최적 솔루션 $x{\displaystyle {}^{}}$∗{\$displaystyle$ x$^{*}}$만 실제 값을 가지는데$$, 거의 항상 무작위 데이터의 "진정한" 실현은 구성된(생성된) 시나리오 집합과 다를 것이기 때문이다.

▼ ${\displaystyle \xi}$에 $d{\displaystyle }$ ${\displaystyle d}$ 독립$$ 랜덤 성분이 포함되어$$ 있다고 가정해 보십시오(예: 각 랜덤 파라미터의 미래 실현은 로우, 중간 및 하이로 분류됨). 그러면 시나리오의 총 $개수$는${\displaystyle }$K = ${\displaystyle {3d}^{}}${\$displaysty K=3^{d$ 그러한 지수시나리오 수의 증가는 합리적인 크기 $d{\displaystyle }$ ${\displaystyle$ d$}$에도 전문가의 의견을 이용한 모델 개발을 매우 어렵게 만든다$.$ $\xi {\displaystyle }$ ${\displaystyle \xi}$의 일부 랜덤 성분이 연속적인 분포를 갖는다면$$ 상황은 더욱 악화된다.

몬테카를로 표본 추출 및 표본 평균 근사법(SAA)

관리 가능한 크기로 설정된 시나리오를 줄이기 위한 일반적인 접근방식은 몬테카를로 시뮬레이션을 사용하는 것이다. 시나리오의 총 수가 매우 크거나 심지어 무한하다고 가정합시다. $또한{\displaystyle }$ 랜덤 벡터$$$vector1{\displaystyle }$,${\displaystyle {}^{}{}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ $,$ ${\displaystyle N^{}}$ ${\$\xi ^{$1},\xi$^{$2},\dots,\$xi ^{$N}$의 랜덤$$ 벡터 $vector$${\displaystyle \xi \}$ 복제$$ 샘플을 생성할 수 있다고 가정해 보십시오$($i.d 샘플). 일반적으로 샘플은 독립적이고 동일한 분산된 것으로 가정한다. 표본이 주어진 기대 함수 ${\displaystyle q}$ (${\displaystyle }$x${\displaystyle }$)${\displaystyle }$= E${\displaystyle }$[ Q${\displaystyle }$( ${\displaystyle x}$ ,${\displaystyle \xi }$) ${\displaystyle ]}$ ${\displaystyle q(x)=E[Q(x,\xi )]}$은 표본 평균으로 근사치된다$$.

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

그리고 결과적으로 1단계 문제는 다음과 같다.

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

이 공식은 표본 평균 근사법이라고 알려져 있다. SAA 문제는 고려된 샘플의 함수로서, 그러한 의미에서 무작위적이다. For a given sample ${\displaystyle \xi ^{1},\xi ^{2},\dots ,\xi ^{N}}$ the SAA problem is of the same form as a two-stage stochastic linear programming problem with the scenarios ${\displaystyle \xi ^{j}}$., ${\displaystyle j=1,\dots ,N}$, each taken with the same probability ${\displaystyle p_{}}$ ${\displaystyle j_{}}$= ${\displaystyle 1\frac{\mathrm{}}{}}$ ${\displaystyle \frac{N}{}}$ ${\$

통계적 추론

다음의 확률적 프로그래밍 문제를 고려하십시오.

Here ${\displaystyle X}$ is a nonempty closed subset of ${\displaystyle \mathbb {R} ^{n}}$, ${\displaystyle \xi }$ is a random vector whose probability distribution ${\displaystyle P}$ is supported on a set ${\displaystyle \Xi \subset \mathbb {R} ^{d}}$, and ${\display$$스타일 Q:X\times \Xi \rightarrow \mathb {R$ 2단계 확률 프로그래밍의 프레임워크에서 $Q{\displaystyle (x}$ ,${\displaystyle \xi }$) ${\displaystyle Q(x,\xi$)는 해당 2단계 문제의 최적 값으로 주어진다$$.

$g{\displaystyle }$( ${\displaystyle x}$) ${\displaystyle g(x)}$이(가) ${\displaystyle \mathrm{모든}}$ x ${\displaystyle \in }$ X ${\displaystyle$ $x$$\in$ $X$$}$에 대해 잘 정의되고 유한하다고 가정하자$.$ 이는 모든 $x{\displaystyle }$∈ ${\displaystyle X}$에 대해$$ $Q{\displaystyle (}$ x ,${\displaystyle \xi }$ $){\displaystystyle Q(x,\xi$)가 거의 확실히 유한하다는$$ 것을 의미한다.

$랜덤{\displaystyle }$ 벡터 $,$${\displaystyle }$…,${\displaystyle {}^{}}$ ${\displaystyle N^{}}$ ${\$$displaystyle$ $\xi$ \xi $\1},\dots,\xi$ $^{N}$의 표본이 $있다고{\displaystyle {}^{}}$ 가정합시다$.$ 이 무작위 샘플은 $\xi {\displaystyle }${\$displaystyle \xi$의 N$${\$displaystyle$N} 관측치의 과거 데이터로 볼 수 있으며, 몬테카를로 샘플링 기법에 의해 생성될 수 있다. 그런 다음 해당 표본 평균 근사치를 공식화할 수 있다.

By the Law of Large Numbers we have that, under some regularity conditions ${\displaystyle {\frac {1}{N}}\sum _{j=1}^{N}Q(x,\xi ^{j})}$ converges pointwise with probability 1 to ${\displaystyle E[Q(x,\xi )]}$ as ${\displaystyle N\rightarrow \infty }$. Moreover, unde경미한 추가 조건 수렴이 균일하다. We also have ${\displaystyle E[{\hat {g}}_{N}(x)]=g(x)}$, i.e., ${\displaystyle {\hat {g}}_{N}(x)}$ is an unbiased estimator of ${\displaystyle g(x)}$. Therefore, it is natural to expect that the optimal value and optimal solutions of the SAA problem converge to 그들의 $진정$한 문제의 상대자들인${\displaystyle }$N → ${\displaystyle \mathrm{\infty }}$ ${\displaystyle$ N$\rightarrow \infit$ $\}.$

SAA 추정기의 일관성

SAA 문제의 실현$$ 가능한 세트 $X{\displaystyle }$ ${\displaystyle X}$이(가) 고정되어 있다고 가정하십시오. 즉, 샘플과 무관하다. Let ${\displaystyle \vartheta ^{*}}$ and ${\displaystyle S^{*}}$ be the optimal value and the set of optimal solutions, respectively, of the true problem and let ${\displaystyle {\hat {\vartheta }}_{N}}$ and ${\displaystyle {\hat {S}}_{N}}$ be the optimal value and the set of 각각 SAA 문제의 최적 해결책.

1. $g{\displaystyle }$: ${\displaystyle X}$→ ${\displaystyle R\mathbb{}}$ ${\$및$$ $g{\displaystyle {\stackrel{}{}}_{}}$ ${\displaystyle {\stackrel{}{^}}_{}N{}_{}}$: X${\displaystyle }$→ ${\displaystyle R\mathbb{}}$ ${\$은(결정적) 실제 가치 함수의 연속이다$$. 다음 두 가지 속성은 동일하다.
   • for any ${\displaystyle {\overline {x}}\in X}$ and any sequence ${\displaystyle \{x_{N}\}\subset X}$ converging to ${\displaystyle {\overline {x}}}$ it follows that ${\displaystyle {\hat {g}}_{N}(x_{N})}$ converges to ${\displaystyle g({\overl$$ine{x}}}$
   • 함수 $g{\displaystyle }$ (${\displaystyle \cdot }$ ) ${\displaystyle$ g$(\cdot )}$은(는) $X{\displaystyle }$ ${\displaystyle X}$ 및 ${\displaystyle g_{}}$ ${\displaystyle {\stackrel{}{^}}_{}}$ N${\displaystyle {}_{}}$($$^)$${\$displaystyle$ ${\g}_{N}(\$$cdot$ )은 $X{\displaystyle }$ ${\\displaystystyle$ $X$$}$의 $콤팩트$ 부분 $집합$에서 균일하게 수렴된다$$$$.
2. If the objective of the SAA problem ${\displaystyle {\hat {g}}_{N}(x)}$ converges to the true problem's objective ${\displaystyle g(x)}$ with probability 1, as ${\displaystyle N\rightarrow \infty }$, uniformly on the feasible set ${\displaystyle X}$. Then ${\displays$$tyle {\hat{\bartheta }}_{N}}$은(는)${\displaystyle {}^{}}probability{\displaystyle {}^{}}$ ${\$에 수렴하며$$$$, 확률 $1$은 N${\displaystyle }$→ ${\displaystyle \mathrm{\infty }}$ ${\displaystyle N\rightarrow \infty$
3. 콤팩트 세트 $C{\displaystyle }$ ${\displaystyle \subset }$ ${\displaystyle {}^{}}$ ${\$이(가) 있다고 가정해 보십시오.
   • 실제 문제의 최적 해결책의$$ S $설정{\displaystyle }${\$displaystyle S}$은(는) $비어{\displaystyle }$ 있지 않으며 C {\$displaystyle C}$에 포함되어 있다.
   • ${\displaystyle \mathrm{함수}}$ $g{\displaystyle }$( x${\displaystyle }$) ${\displaystyle g(x)}$은(는) 유한 값으로 $C{\displaystyle }$ ${\displaystyle$ C$}$에서 연속적으로 지정됨$$
   • 함수 $g{\displaystyle {\stackrel{}{}}_{}}$ ${\displaystyle {\stackrel{}{^}}_{}}$ ${\displaystyle N_{}}$( ${\displaystyle x}$) ${\displaystyle {\hat {g}_{N}(x$)}은(는) $확률{\displaystyle }$ 1과 함께$$ $g{\displaystyle }$( x${\displaystyle }$) ${\displaystyle g(x)}$에 통합되며$$, N${\displaystyle }$→ ${\displaystyle \mathrm{\infty }}$ ${\$$displaystyle$ $N\rigarrow$\$infty$ $\}$로 균일하게 x$}$이다.
   • $설정{\displaystyle {\stackrel{}{}}_{}}$ $S{\displaystyle {\stackrel{}{}}_{}}$^ ${\displaystyle N_{}}$${\displaystyle$ {\$s}$_{N$}이($가$$) 충분히$$$$ 큰 $N{\displaystyle }$$$${\$displaystyle {\${\displaystyle \mathrm{displaystyle}}$ ${\s}{N}} 확률 1인$ S ${\displaystyle {}_{}}$ N ^ ${\displaystyle N_{}}$ ^{\$displaystystyle$ C$}$

then ${\displaystyle {\hat {\vartheta }}_{N}\rightarrow \vartheta ^{*}}$ and ${\displaystyle \mathbb {D} (S^{*},{\hat {S}}_{N})\rightarrow 0}$ with probability 1 as ${\displaystyle N\rightarrow \infty }$. Note that ${\displaystyle \mathbb {D}$$(A,B)}$은(는) 다음과 같이 정의된 세트 $B{\displaystyle }$ ${\displaystyle B}$에서 세트 $A{\displaystyle }$ ${\displaystyle A}$의 편차를 나타낸다$$$.$

어떤 상황에서는 SAA 문제의 실현$$ 가능한 $세트{\displaystyle }$ X ${\displaystyle X}$을(를) 추정하면 해당 SAA 문제가 형태를 취한다.

여기서 $X{\displaystyle {}_{}}$ ${\displaystyle N_{}}$ ${\$는 표본에 따라$$ ${\displaystyle {}^{}}$ ${\$의 부분 집합이므로$$ 랜덤이다. 그럼에도 불구하고 SAA 추정기에 대한 일관성 결과는 다음과 같은 추가 가정에 따라 도출될 수 있다.

1. 콤팩트 세트 $C{\displaystyle }$ ${\displaystyle \subset }$ ${\displaystyle {}^{}}$ ${\$이(가) 있다고 가정해 보십시오.
   • 실제 문제의 최적 해결책의$$ S $설정{\displaystyle }${\$displaystyle S}$은(는) $비어{\displaystyle }$ 있지 않으며 C {\$displaystyle C}$에 포함되어 있다.
   • ${\displaystyle \mathrm{함수}}$ $g{\displaystyle }$( x${\displaystyle }$) ${\displaystyle g(x)}$은(는) 유한 값으로 $C{\displaystyle }$ ${\displaystyle$ C$}$에서 연속적으로 지정됨$$
   • 함수 $g{\displaystyle {\stackrel{}{}}_{}}$ ${\displaystyle {\stackrel{}{^}}_{}}$ ${\displaystyle N_{}}$( ${\displaystyle x}$) ${\displaystyle {\hat {g}_{N}(x$)}은(는) $확률{\displaystyle }$ 1과 함께$$ $g{\displaystyle }$( x${\displaystyle }$) ${\displaystyle g(x)}$에 통합되며$$, N${\displaystyle }$→ ${\displaystyle \mathrm{\infty }}$ ${\$$displaystyle$ $N\rigarrow$\$infty$ $\}$로 균일하게 x$}$이다.
   • $설정{\displaystyle {\stackrel{}{}}_{}}$ $S{\displaystyle {\stackrel{}{}}_{}}$^ ${\displaystyle N_{}}$${\displaystyle$ {\$s}$_{N$}이($가$$) 충분히$$$$ 큰 $N{\displaystyle }$$$${\$displaystyle {\${\displaystyle \mathrm{displaystyle}}$ ${\s}{N}} 확률 1인$ S ${\displaystyle {}_{}}$ N ^ ${\displaystyle N_{}}$ ^{\$displaystystyle$ C$}$
   • $X{\displaystyle {}_{}}$ ${\displaystyle N_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle N_{}}$ ${\$과(${\displaystyle {와}_{}}$)$$x N {\$displaystyle$$$x_{$N}$이(가$)$ 확률 $1$과(와) 합쳐지면$$, $x{\displaystyle }$$$${\displaystyle \in }$ ${\displaystyle X}$ ${\displaystyle$ x$\in X}$
   • 어떤 지점 $x{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle {}^{}}$∗ ${\$ S$^{*}}}$에 대해, 확률 ${\displaystyle 1}$을 갖는$$ $x{\displaystyle {}_{}}$ ${\displaystyle N_{}}$→ x ${\displaystyle x_{N}\{$$N$}\in $X_{$$N}}$에 시퀀스 $x{\displaystyle {}_{}}$ ∈ ${\displaystyle X_{}}$∈ X ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ N이 ${\displaystyle {있다}_{}}$.

then ${\displaystyle {\hat {\vartheta }}_{N}\rightarrow \vartheta ^{*}}$ and ${\displaystyle \mathbb {D} (S^{*},{\hat {S}}_{N})\rightarrow 0}$ with probability 1 as ${\displaystyle N\rightarrow \infty }$.

SAA 최적값의 점근법

Suppose the sample ${\displaystyle \xi ^{1},\dots ,\xi ^{N}}$ is i.i.d. and fix a point ${\displaystyle x\in X}$. Then the sample average estimator ${\displaystyle {\hat {g}}_{N}(x)}$, of ${\displaystyle g(x)}$, is unbiased and has variance ${\displaystyle \frac{1}{N}{\sigma }^2(x)}$${\displaystyle {\frac$ {$1}{N}\sigma ^{2}(x$ 여기서 $\sigma {\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$( ${\displaystyle x}$) ${\displaystyle :=}$ ${\displaystyle V}$ ${\displaystyle a}$[ ${\displaystyle Q}$( ${\displaystyle x}$ ,${\displaystyle \xi }$) ${\displaystyle ]}$ ${\displaystyle \sigma ^{2}(x):$$=Var[Q(x,\xi )]}$은(는) 유한해야 한다. 게다가, 중앙 한계 정리로는

where ${\displaystyle {\xrightarrow {\mathcal {D}}}}$ denotes convergence in distribution and ${\displaystyle Y_{x}}$ has a normal distribution with mean ${\displaystyle 0}$ and variance ${\displaystyle \sigma ^{2}(x)}$, written as ${\displaystyle {\mathcal$${N}(0,\sigma ^{2}(x)}}$.

In other words, ${\displaystyle {\hat {g}}_{N}(x)}$ has asymptotically normal distribution, i.e., for large ${\displaystyle N}$, ${\displaystyle {\hat {g}}_{N}(x)}$ has approximately normal distribution with mean ${\displaystyle g(x)}$ and variance ${\displaystyle \frac{1}{N}{\sigma }^2(x}$${\displaystyle )}$ ${\displaystyle {\frac {1}{N}\sigma ^{2}(x$ 이렇게 하면 $f{\displaystyle (}$ ${\displaystyle x}$) ${\$$displaystyle 100(\alpha ){\$$displaystystyle f($x$)\}$에 대한 신뢰 구간이 다음(대략${\displaystyle )}$로 이어진다$.$

여기서 $z{\displaystyle {}_{}}$ ${\displaystyle {\alpha }_{}}$/ ${\displaystyle {2\mathrm{}}_{}}$ ${\displaystyle :=}$ ${\displaystyle {\mathrm{}}^{}}$- ${\displaystyle 1{}^{}}$( 1 -${\displaystyle \alpha \mathrm{}}$/ 2${\displaystyle }$) ${\displaystyle z_{\alpha /2}=\$$Phi ^{-1}(1-\alpha /2)}($여기서 $\phi {\displaystyle \mathrm{}}$ (${\displaystyle }$⋅ ) ${\displaystyle \Phi (\cdot )}$는 표준 정규 분포의 cdf를 나타냄) 및

$\sigma {\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$( $){\displaystyle \sigma ^{2}(x)}$의 표본 분산 추정치 입니다$.$ $,$g (${\displaystyle x}$ ) {\$displaystyle$ g$(x)}$의 추정 오차는 (stocholic) $O$ (${\displaystyle N}$)$${\displaystysty $O({\sqrt{N$

응용 프로그램 및 예제

생물학적 응용

확률론적 동적 프로그래밍은 행동 생태학 같은 분야에서 동물의 행동을 모형화하는 데 자주 사용된다.^[8][9] 최적의 노화, 생물-역사 전환 모델(예: 새의 산란, 파라시토이드 말벌의 난자 산란 등)의 경험적 실험은 행동 의사결정 진화를 설명하는 데 있어 이 모델링 기법의 가치를 보여주었다. 이 모델들은 일반적으로 2단계라기보다는 다단계라 할 수 있다.

경제 적용

확률론적 동적 프로그래밍은 불확실성 하에서 의사결정을 이해하는 데 유용한 도구다. 불확실성에 따른 자본 주식의 축적이 한 예인데, 종종 자원 경제학자들이 날씨 등 불확실성이 유입되는 바이오 경제 문제를^[10] 분석하기 위해 사용한다.

예: 다단계 포트폴리오 최적화

다음은 다단계 확률형 프로그래밍의 재정에서 나온 예다. $t{\displaystyle }$= ${\displaystyle 0}$ ${\displaystyle t=0}$에 $n{\displaystyle }$ ${\displaystyle n}$ 자산에$$$$ $투자$할 초기 자본 W 0 {\$displaystyle$ W_${0}$이 있다고 가정합시다. 더 나아가 우리가 포트폴리오에 추가 현금을 투입하지 않고 $때때로$${\displaystyle \mathrm{t}}$ =${\displaystyle }$1,${\displaystyle }$… ,${\displaystyle T}$ - ${\displaystyle 1}$ ${\디스플레이 스타일$t=$1,\dots ,T-1}$을(를) 재조정할 수 있다고 가정하자. 각 $기간{\displaystyle }$ t ${\displaystyle t}$에서 $n{\displaystyle }$ ${\$$displaystyle$ $n}$ 자산 $중$ $현재$재산 W t {\$displaystyle$ W_{t$$$}$를 재분배하기로 결정한다. $x{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$=${\displaystyle }$( ${\displaystyle {}_{}}$ ${\displaystyle {10}_{}}$,${\displaystyle }$…${\displaystyle }$, ${\displaystyle {}_{}}$ ${\displaystyle {\mathrm{n}}_{}}$ 0${\displaystyle {}_{}}$) ${\displaystyle x_{0}=(x_{10},\dots ,x_{n0})$를 n 자산에 투자한 초기 금액으로 한다$$. 각 x $i{\displaystyle {}_{}}$ ${\displaystyle 0_{}}$ ${\$}이$($가$$) 음이 아니며 균형 방정식${\displaystyle \underset{equation}{\overset{}{}}}$ i${\displaystyle \underset{}{\overset{}{}}}$= ${\displaystyle \underset{}{\overset{}{}}}$ x ${\displaystyle {\mathrm{i}}_{}}$ 0${\displaystyle {}_{}}$= ${\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\$이(가)가 되어야 한다.$W_{0}}$은(는) 참아야 한다$$.

Consider the total returns ${\displaystyle \xi _{t}=(\xi _{1t},\dots ,\xi _{nt})}$ for each period ${\displaystyle t=1,\dots ,T}$. This forms a vector-valued random process ${\displaystyle \xi _{1},\dots ,\xi _{T}}$. At time period ${\displayst$$yle t=1$ 각 자산에 투자한 $금액$ x ${\displaystyle {1\mathrm{}}_{}}$=${\displaystyle }$( x ${\displaystyle {11}_{}}$,${\displaystyle }$…${\displaystyle }$, x ${\displaystyle {\mathrm{n}}_{}}$ ${\displaystyle 1_{}}$ $){\displaystyle x_{1}=(x_{11},\reason ,x_{n1}})$을 지정하여 포트폴리오의 균형을 재조정할 수 있다. 그 때 첫 번째 기간의 수익이 실현되었으므로 이 정보를 재조정 결정에 사용하는 것이 합리적이다. Thus, the second-stage decisions, at time ${\displaystyle t=1}$, are actually functions of realization of the random vector ${\displaystyle \xi _{1}}$, i.e., ${\displaystyle x_{1}=x_{1}(\xi _{1})}$. Similarly, at time ${\displaystyle t}$ the decision ${\displaystyle x_t=(x_{1t},}$${\displaystyle x_{t}=(x_{1t},\dots ,x_{nt})}$ is a function ${\displaystyle x_{t}=x_{t}(\xi _{[t]})}$ of the available information given by ${\displaystyle \xi _{[t]}=(\xi _{1},\dots ,\xi _{t})}$ the history of the random process up to time ${\displaystyle }$${\displaystyle t}$. A sequence of functions ${\displaystyle x_{t}=x_{t}(\xi _{[t]})}$, ${\displaystyle t=0,\dots ,T-1}$, with ${\displaystyle x_{0}}$ being constant, defines an implementable policy of the decision process. It is said that such a policy is feasible if it satisfies the model constraints with probability 1, i.e., the nonnegativity constraints ${\displaystyle x_{it}(\xi _{[t]})\geq 0}$, ${\displaystyle i=1,\dots ,n}$, ${\displaystyle t=0,\dots ,T-1}$, and the balance of weal번째 구속조건,

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

여기서$$$$ $period{\displaystyle }$ t${\displaystyle }$= ${\displaystyle 1}$,${\displaystyle }$…${\displaystyle }$, ${\displaystyle T}$ ${\displaystyle t=1,\dots,$T}은$($는$)$ 재산 $W{\displaystyle {}_{}}$ ${\displaystyle t_{}}$ {\$displaystyle$ W_${t}$에 의해 주어진다.

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

임의 프로세스의 실현과 시간 $t{\displaystyle }$ ${\displaystyle t}$까지의 결정에 따라 달라진다$.$

마지막 기간에 이 부의 기대 효용, 즉 문제를 고려하는 것이 목적이라고 가정합시다.

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

이것은 다단계 확률 프로그래밍 문제로, 단계 $번호$가 t${\displaystyle }$= ${\displaystyle 0}$ ${\displaystyle t=0}$에서 ${\displaystyle t}$ =${\displaystyle }$T${\displaystyle }$- 1 ${\displaystyle t=T-1}$까지이며$,$ 실행 가능하고 실현 가능한 모든 정책에 대해 최적화가 수행된다. 문제 설명을 완성하기 위해서는 무작위 ${\displaystyle {공정}_{}}$의 ${\displaystyle {확률분포도\mathrm{}}_{}}$ needs${\displaystyle {}_{}}$1 ,${\displaystyle }$…,${\displaystyle {}_{}}$ T$${\$displaystyle \xi$\$1},\dots,\xi$ _${T$ 이것은 다양한 방법으로 할 수 있다. 예를 들어 프로세스의 시간 진화를 정의하는 특정 시나리오 트리를 구성할 수 있다. 각 자산의 무작위 수익률이 다른 자산과 독립적으로 두 개의 연속성을 가질 수 있다면, 시나리오의 총 수는 ${\displaystyle {2n}^{}}$ ${\displaystyle T^{}}$ ${\displaystyle$ 2$^{nT}$이다.$}$

동적 프로그래밍 방정식을 작성하려면 위의 다단계 문제를 시간 역순으로 고려하십시오. At the last stage ${\displaystyle t=T-1}$, a realization ${\displaystyle \xi _{[T-1]}=(\xi _{1},\dots ,\xi _{T-1})}$ of the random process is known and ${\displaystyle x_{T-2}}$ has been chosen. 따라서 다음과 같은 문제를 해결해야 한다.

${\displaystyle {\begin{array}{lrclr}\max \limits _{x_{T-1}&E[U(W_{T}) \xi _{[T-1]]]&\\\\text{w_{w_{w_}}{pubject}}{data.T}&=&\sum _{i=1}^{n}\xi _{i}x_{i-1}\&\sum _{i=1}x_{n1}x_{n1}x_{T-1}&w_\&x_{T-1}\&geq&0\end}}}}}:{i={i=1}$

where ${\displaystyle E[U(W_{T}) \xi _{[T-1]}]}$ denotes the conditional expectation of ${\displaystyle U(W_{T})}$ given ${\displaystyle \xi _{[T-1]}}$. The optimal value of the above problem depends on ${\displaystyle W_{T-1}}$ and ${\displaystyle \xi _{[T-1]}}$ and is denoted ${\displaystyle Q_{T-1}(W_{T-1},\xi _{[T-1]})}$.

마찬가지로, ${\displaystyle \mathrm{단계}}$ $t{\displaystyle }$= T${\displaystyle }$- ${\displaystyle 2}$,${\displaystyle }$…${\displaystyle }$, 1 ${\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}}}$

최적의 값은 $Q{\displaystyle {}_{}}$ ${\displaystyle t_{}{W}_{}}$ t ,${\displaystyle {}_{}{}_{}}$[ ${\displaystyle t_{}}$ ${\displaystyle {]}_{}}$) ${\displaystyle Q_{t}(W_{t},\xi$ $_$${t$ $마지막$으로 단계 t${\displaystyle }$= ${\displaystyle 0}$ ${\displaysty$ t$=0}$에서 문제를 해결한다$.$

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

단계별 독립 랜덤 공정

$프로세스{\displaystyle {}_{}}$ general t ${\${t$}$의 일반적인 분포에서는 이러한 동적 프로그래밍 방정식을 해결하기 어려울 수 있다$.$ The situation simplifies dramatically if the process ${\displaystyle \xi _{t}}$ is stagewise independent, i.e., ${\displaystyle \xi _{t}}$ is (stochastically) independent of ${\displaystyle \xi _{1},\dots ,\xi _{t-1}}$ for ${\displaystyle t=2,\dots ,T}$. In this case, ${\displaystyle {해당}_{}}$ 조건부 기대는 무조건적인 기대치가 되고, $함수{\displaystyle }$ Q t ${\displaystyle {}_{}{W}_{}}$ t${\displaystyle {}_{}}$) ${\displaystyle Q_{t}(W_{t}),$${\displaystyle t}$= ${\displaystyle 1}$, ${\displaystyle \dots ,}$ ${\displaystyle \mathrm{T}}$ -${\displaystyle }$1 ${\displaysty$ t$=1,\dots,T-1}$은 $\xi {\displaystyle {}_{}}$[ ${\displaystyle t_{}}$ ${\displaystyle {]}_{}}$ ${\$에 의존하지 않는다$$$.$ 즉, $Q{\displaystyle {}_{}}$ ${\displaystyle T_{}}$- ${\displaystyle 1_{}}$( ${\displaystyle W_{}}$ ${\displaystyle {\mathrm{T}}_{}}$- 1${\displaystyle {}_{}}$) ${\displaystyle Q_{T-1}(W_{T-1})$이$$ 문제의 최적 값이다.

${\displaystyle {\begin{array}{lrclr}\max \limits _{x_{T-1}&E[U(W_{T})]\\\\text{대상}&W_{{w_{w_{w_{w_}}}}{{w_}}}}}}{{{}}}}}}}}}}}}}}}}}T}&=&\sum _{i=1}^{n}\xi _{i}x_{i-1}\&\sum _{i=1}x_{n1}x_{n1}x_{T-1}&w_\&x_{T-1}\&geq&0\end}}}}}:{i={i=1}$

및 $Q{\displaystyle {}_{}}$ ${\displaystyle t_{}}$( ${\displaystyle {}_{}}$ ${\displaystyle t_{}}$) ${\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}}}$

$t{\displaystyle }$= ${\displaystyle T}$- ${\displaystyle 2}$,${\displaystyle }$… ${\displaystyle 1}$ ${\displaystyle t=T-2,\dots,$1}의 경우$.$

소프트웨어 도구

모델링 언어

모든 이산 확률적 프로그래밍 문제는 모든 대수적 모델링 언어로 표현될 수 있으며, 결과 모델이 각 단계에서 이용할 수 있는 정보의 구조를 존중하는지 확인하기 위해 명시적이거나 암묵적인 비예측성을 수동으로 구현한다. 일반적인 모델링 언어에 의해 생성된 SP 문제의 한 예는 상당히 크게 증가하는 경향이 있으며(시나리오 수에 선형적으로), 그 매트릭스는 이 종류의 문제에 내재된 구조를 상실하며, 그렇지 않으면 특정 분해 알고리즘에 의해 해결 시점에 악용될 수 있다. SP용으로 특별히 설계된 언어의 모델링 확장자가 나타나기 시작한다. 자세한 내용은 다음을 참조하십시오.

• AIMMS - SP 문제의 정의 지원
• EMP SP(가연성 프로그래밍을 위한 확장 수학적 프로그래밍) - 확률적 프로그래밍을 용이하게 하기 위해 만들어진 GAMS 모듈(모수 분포의 키워드, 위험에서의 가치 및 예상 부족량과 같은 위험 조치 포함)
• SAMPL - 확률적 프로그램을 표현하도록 특별히 설계된 MEMP 확장 세트(우연 제약 조건, 통합된 기회 제약 조건 및 강력한 최적화 문제에 대한 구문 포함)

그들은 모두 SMPS 인스턴스 수준 형식을 생성할 수 있으며, 이는 문제의 구조를 해결사에게 전달하는 비중복적인 형태로 전달된다.

참고 항목

• 상관격차
• 확률적 프로그래밍을 위한 EMP
• 위험시 진입성 값
• 포트SP
• SAMPL 대수 모델링 언어
• 시나리오 최적화
• 확률적 최적화
• 우연성 제약 포트폴리오 선택

참조

추가 읽기

• 존 R. 버지와 프랑수아 V. 루보. 확률론적 프로그래밍 소개 1997년 뉴욕 스프링거 버랙
• Kall, Peter; Wallace, Stein W. (1994). Stochastic programming. Wiley-Interscience Series in Systems and Optimization. Chichester: John Wiley & Sons, Ltd. pp. xii+307. ISBN 0-471-95158-7. MR 1315300.
• G. Ch. Pflug: 확률적 모델의 최적화. 시뮬레이션과 최적화 사이의 인터페이스. 클루워, 도드레흐트, 1996년
• 안드라스 프레코파 확률적 프로그래밍. Kluwer 학술 출판사, Dordrecht, 1995.
• Andrzej Ruszzzzynski and Alexander Shapiro (eds.) (2003) Stochastic Programming. 운영 연구 및 관리 과학 핸드북, 10권, 엘스비에
• Shapiro, Alexander; Dentcheva, Darinka; Ruszczyński, Andrzej (2009). Lectures on stochastic programming: Modeling and theory (PDF). MPS/SIAM Series on Optimization. Vol. 9. Philadelphia, 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. W. Wallace와 William T. Ziemba (eds) (2005) Stochastic Programming의 적용. 최적화 5에 관한 MPS-SIAM 북 시리즈
• King, Alan J.; Wallace, Stein W. (2012). Modeling with Stochastic Programming. Springer Series in Operations Research and Financial Engineering. New York: Springer. ISBN 978-0-387-87816-4.

외부 링크

• 확률형 프로그래밍 커뮤니티 홈 페이지