확률적 계획법

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

확률적 계획법은 불확실한 상황에서 최적의 의사 결정을 내리기 위한 수학적 방법론으로, 다양한 확률적 프로그래밍 기법과 2단계 확률 계획법, 결정론적 등가, 시나리오 생성 등의 개념을 포함한다. 이는 시나리오 기반 방법, 확률적 정수 프로그래밍, 확률 제약 프로그래밍, 확률적 동적 계획법 등 다양한 방법론을 통해 불확실성을 다룬다. 확률적 계획법은 생물학, 경제, 금융 공학 등 여러 분야에 응용되며, 특히 금융 공학에서는 포트폴리오 최적화 문제 해결에 활용된다.

더 읽어볼만한 페이지

최적화 알고리즘 및 방법 - 신뢰 영역
신뢰 영역 방법은 비선형 최적화에서 함수의 모델을 신뢰할 수 있는 영역 내에서만 사용하여 최적화를 수행하는 방법으로, 다양한 분야에서 전역 최적해를 찾기 위한 도구로 활용된다.
최적화 알고리즘 및 방법 - 탐욕 알고리즘
탐욕 알고리즘은 각 단계에서 가장 좋아 보이는 선택을 하는 알고리즘 설계 패러다임으로, 최적 부분 구조와 탐욕 선택 속성을 가진 문제에 최적의 해를 보장하며, 다익스트라, 프림, 크루스칼 알고리즘 등에 사용된다.

확률적 계획법
개요
분야	수학, 컴퓨터 과학, 운영 과학
하위 분야	최적화, 확률론
관련 항목	확률적 제어
상세 정보
목적	불확실성이 존재하는 환경에서의 최적화 문제 모델링

2. 확률적 프로그래밍의 방법론

시나리오 기반 방법, 확률적 정수 프로그래밍, 확률 제약 프로그래밍, 확률적 동적 계획법, 마르코프 결정 과정, 벤더스 분해 등 다양한 확률적 프로그래밍 방법이 개발되었다.^[5]

2단계 확률 계획법의 기본 개념은 결정을 내릴 때 사용 가능한 데이터를 기반으로 해야 하며, 미래의 관측에 의존할 수 없다는 것이다. 2단계 공식은 확률 계획법에서 널리 사용되며, 일반적인 2단계 확률 계획법 문제는 다음과 같이 표현할 수 있다.

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

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

$\min_{y}\{ q(y,\xi) \,|\,T(\xi)x+W(\xi) y = h(\xi)\}.$

고전적인 2단계 선형 확률 계획법 문제는 다음과 같이 공식화할 수 있다.

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

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

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

위 공식에서 $x\in \mathbb{R}^n$ 은 1단계 의사 결정 변수 벡터, $y\in \mathbb{R}^m$ 은 2단계 의사 결정 변수 벡터, $\xi(q,T,W,h)$ 는 2단계 문제의 데이터를 포함한다. 1단계에서는 불확실한 데이터 $\xi$ 의 실현이 알려지기 전에 "현시점" 결정을 내려야 한다. 2단계에서는 $\xi$ 가 실현된 후 최적화 문제를 해결하여 행동을 최적화한다.

1단계에서는 1단계 결정 비용 $c^Tx$ 과 (최적) 2단계 결정의 예상 비용을 최소화한다. 2단계 문제는 불확실한 데이터가 공개되었을 때 최적 행동을 설명하는 최적화 문제로 볼 수 있다. 또는 그 해를 $Wy$ 항이 $Tx\leq h$ 시스템의 불일치를 보상하고 $q^Ty$ 가 이 보상 비용인 보상 조치로 간주할 수 있다.

2단계 문제는 목적 함수와 제약 조건이 선형이므로 ''선형''이다. 1단계 문제가 정수라면, 실행 가능한 집합이 이산적이 되도록 정수 제약 조건을 추가할 수 있다. 필요한 경우 비선형 목적 함수와 제약 조건을 통합할 수도 있다.^[5]

확률적 선형 계획법은 고전적인 2단계 확률적 계획법의 한 প্রকার이다. 확률적 LP는 여러 기간의 선형 계획법(LP) 모음으로 구성되며, 각 LP는 동일한 구조를 가지지만 약간 다른 데이터를 갖는다. $k^{번째}$ 시나리오의 $k^{번째}$ 2단계 LP는 다음과 같다.

$\begin{array}{lccccccc}\text{최소화} & f^T x & + & g^T y & + & h_k^Tz_k & & \\\text{제약 조건} & Tx & + & Uy & & & = & r \\& & & V_k y & + & W_kz_k & = & s_k \\& x & , & y & , & z_k & \geq & 0\end{array}$

벡터 $x$ 와 $y$ 는 즉시 선택해야 하는 1단계 변수이다. 벡터 $z_k$ 는 후속 기간 변수를 포함한다. $Tx + Uy = r$ 제약 조건은 1단계 변수만 포함하며 모든 시나리오에서 동일하다. 다른 제약 조건은 이후 기간 변수를 포함하며, 불확실성을 반영하여 시나리오에 따라 다르다.

$k^{번째}$ 2단계 LP를 푸는 것은 불확실성이 없는 2단계에서 $k^{번째}$ 시나리오를 가정하는 것과 같다. 불확실성을 통합하려면, 다른 시나리오에 확률을 할당하고 해당 결정론적 등가를 풀어야 한다.

2. 1. 시나리오 기반 방법

불확실한 미래 상황을 여러 개의 시나리오(

\xi_1,\dots,\xi_K

)로 정의하고, 각 시나리오에 해당하는 확률 질량(

p_1,\dots,p_K

)을 가정하여 각 시나리오에 대한 최적해를 구한다. 이때, 첫 번째 단계 문제의 목적 함수에 있는 기댓값은 다음과 같은 합으로 표현할 수 있다.

E[Q(x,\xi)]=\sum\limits_{k=1}^{K} p_kQ(x,\xi_k)

\xi

가 무한하거나 매우 많은 수의 가능한 실현 값을 갖는 경우, 몬테카를로 시뮬레이션을 사용하여 시나리오 집합을 관리 가능한 크기로 줄이는 것이 일반적인 접근 방식이다. 독립적이고 동일하게 분포된(i.i.d 샘플) 표본 평균 근사(Sample Average Approximation, SAA) 방법은 몬테카를로 샘플링을 통해 시나리오를 생성하고, 이를 기반으로 최적화 문제를 해결한다. 랜덤 벡터

\xi

의

N

개의 복제본 샘플(

\xi^1,\xi^2,\dots,\xi^N

)을 생성할 수 있다고 가정하면, 샘플이 주어졌을 때 기대 함수

q(x)=E[Q(x,\xi)]

는 표본 평균으로 근사된다.

\hat{q}_N(x) = \frac{1}{N} \sum_{j=1}^N Q(x,\xi^j)

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

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

이 공식은 ''표본 평균 근사'' 방법으로 알려져 있으며, SAA 문제는 고려된 샘플의 함수이며, 각 시나리오

\xi^j

(

j=1,\dots,N

)이 동일한 확률

p_j=\frac{1}{N}

로 취해진다.

2. 2. 확률적 동적 계획법

확률적 동적 계획법은 시간에 따라 불확실성이 전개되는 상황에서 의사 결정을 모델링하는 방법이다. 마르코프 결정 과정(Markov Decision Process, MDP)은 확률적 동적 계획법의 특수한 경우이다.^[8]^[9]

확률적 동적 계획법은 행동생태학과 같은 분야에서 동물 행동을 모델링하는 데 자주 사용된다. 최적 섭식 이론, 생물학적 생활사의 조류의 둥지 떠나기 및 기생체 벌의 산란과 같은 전환에 대한 모델의 경험적 테스트는 이러한 모델링 기법이 행동 의사 결정의 진화를 설명하는 데 가치가 있음을 보여주었다. 이러한 모델은 일반적으로 2단계가 아닌 다단계이다.

확률적 동적 계획법은 불확실성 하에서의 의사 결정을 이해하는 데 유용한 도구이다. 불확실성 하에서의 자본 축적은 그 한 예시이며, 종종 자원 경제학자들이 날씨 등과 같은 불확실성이 발생하는 생물 경제적 문제를 분석하는 데 사용된다.

2. 3. 벤더스 분해 (Benders Decomposition)

확률적 선형 계획법에서 유한 개의 시나리오가 있는 경우, 이 문제는 대규모 선형 계획법 문제로 나타낼 수 있다. 이를 결정론적 등가 선형 계획법(deterministic equivalent linear program)이라고 하며, 줄여서 결정론적 등가(deterministic equivalent)라고도 한다. (엄밀히 말하면, 결정론적 등가는 최적의 1단계 결정을 계산하는 데 사용될 수 있는 모든 수학적 계획법을 의미한다. 따라서 2단계 비용을 닫힌 형식으로 표현할 수 있다면 연속 확률 분포에도 존재한다.)

예를 들어, 확률적 선형 계획법에 대한 결정론적 등가를 구성하기 위해 각 시나리오

k=1,\dots,K

에 확률

p_k

를 부여한다. 그리고 모든 시나리오의 제약 조건을 적용하여 목적 함수의 기대값을 최소화한다.

\begin{array}{lccccccccccccc}\text{최소화} & f^\top x & + & g^\top y & + & p_1h_1^\top z_1 & + & p_2h_2^Tz_2 & + & \cdots & + & p_Kh_K^\top z_K &  &  \\\text{제약 조건} & Tx & + & Uy &  &  &  &  &  &  &  &  & = & r \\&  &  & V_1 y & + & W_1z_1 &  &  &  &  &  &  & = & s_1 \\&  &  & V_2 y &  &  & + & W_2z_2 &  &  &  &  & = & s_2 \\&  &  & \vdots &  &  &  &  &  & \ddots &  &  &  & \vdots \\&  &  & V_Ky &  &  &  &  &  &  & + & W_Kz_K & = & s_K \\& x & , & y & , & z_1 & , & z_2 & , & \ldots & , & z_K & \geq & 0 \\\end{array}

각 시나리오

k

에 대해 후기 변수

z_k

의 다른 벡터를 가진다. 1기 변수

x

와

y

는 각 시나리오에서 동일하지만, 실현될 시나리오를 알기 전에 1기에 대한 결정을 내려야 하기 때문이다. 따라서

x

와

y

만 포함하는 제약 조건은 한 번만 지정하면 되지만, 나머지 제약 조건은 각 시나리오에 대해 별도로 설정해야 한다.

3. 2단계 확률 계획법

2단계 확률 계획법은 불확실성 하에서 의사 결정을 할 때 사용되는 방법이다. 이 방법의 핵심은 결정을 내릴 때 사용 가능한 데이터를 기반으로 해야 하며, 미래에 어떻게 될지 예측하는 것에 의존해서는 안 된다는 것이다. 2단계 공식은 확률 계획법에서 널리 사용된다.^[5]

2단계 확률 계획법은 크게 두 단계로 나뉜다. 첫 번째 단계에서는 불확실한 상황이 발생하기 전에 결정을 내린다. 두 번째 단계에서는 불확실성이 명확해진 후에, 첫 번째 단계에서 내린 결정에 대해 필요한 조치를 취한다. 이 방법의 목표는 첫 번째 단계의 비용과 두 번째 단계의 예상 비용을 더한 값을 최소화(또는 최대화)하는 것이다.

고전적인 2단계 선형 확률 계획법 문제는 다음과 같이 표현될 수 있다.^[5]

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

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

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

이 공식에서 $x$ 는 1단계 결정 변수, $y$ 는 2단계 결정 변수, $\xi$ 는 2단계 문제의 불확실한 데이터를 나타낸다. 1단계에서는 불확실한 데이터 $\xi$ 가 어떻게 될지 알기 전에 결정을 내려야 한다. 2단계에서는 $\xi$ 가 명확해진 후, 최적화 문제를 해결하여 행동을 조정한다.

1단계에서는 1단계 결정 비용 $c^Tx$ 와 2단계 결정의 예상 비용을 더한 값을 최소화하려고 한다. 2단계 문제는 불확실한 정보가 밝혀졌을 때 우리가 어떻게 행동해야 하는지를 나타내는 최적화 문제로 볼 수 있다. 또는, $Wy$ 항이 $Tx\leq h$ 시스템에서 발생할 수 있는 불일치를 보상하고, $q^Ty$ 가 이러한 보상에 드는 비용을 나타내는 것으로 이해할 수도 있다.

2단계 문제는 목적 함수와 제약 조건이 모두 선형 함수이기 때문에 '선형'이라고 불린다. 하지만, 반드시 선형일 필요는 없으며, 더 복잡한 형태를 가질 수도 있다. 예를 들어, 1단계 문제가 정수 값을 가져야 한다면, 정수 제약 조건을 추가하여 가능한 경우를 제한할 수 있다. 또한, 필요에 따라 선형이 아닌 목적 함수나 제약 조건을 사용할 수도 있다.^[5]

3. 1. 문제 정의

2단계 확률적 계획법의 기본 개념은 결정을 내릴 때 사용 가능한 데이터를 기반으로 해야 하며, 미래의 예측에 의존할 수 없다는 것이다. 2단계 공식은 확률적 계획법에서 널리 사용된다.

첫 번째 단계에서는 불확실성이 실현되기 전에 결정을 내린다. 두 번째 단계에서는 불확실성이 실현된 후, 첫 번째 단계의 결정에 대한 보상(recourse) 조치를 취한다. 목적 함수는 첫 번째 단계 비용과 두 번째 단계 비용의 기댓값을 최소화(또는 최대화)하는 것이다.^[5]

2단계 확률적 계획법 문제의 일반적인 공식은 다음과 같다.

:

\min_{x\in X}\{ g(x)= f(x) + E_{\xi}[Q(x,\xi)]\}

여기서

Q(x,\xi)

는 2단계 문제의 최적 값이다.

:

\min_{y}\{ q(y,\xi) \,|\,T(\xi)x+W(\xi) y = h(\xi)\}.

고전적인 2단계 선형 확률적 계획법 문제는 다음과 같이 표현할 수 있다.

:

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

여기서

Q(x,\xi)

는 2단계 문제의 최적 값이다.

:

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

위 공식에서

x\in \mathbb{R}^n

은 1단계 의사 결정 변수 벡터이고,

y\in \mathbb{R}^m

은 2단계 의사 결정 변수 벡터이며,

\xi(q,T,W,h)

는 2단계 문제의 데이터를 포함한다. 1단계에서 우리는 불확실한 데이터

\xi

의 실현이 알려지기 전에 "현재" 결정을 내려야 한다. 2단계에서는

\xi

의 실현 가능성이 확보된 후 적절한 최적화 문제를 해결하여 행동을 최적화한다.

1단계에서 우리는 1단계 결정의 비용

c^Tx

과 (최적) 2단계 결정의 예상 비용을 최소화한다. 2단계 문제는 불확실한 데이터가 공개되었을 때 우리의 최적 행동을 설명하는 최적화 문제로 볼 수 있다. 또는 그 해를 항

Wy

가 시스템

Tx\leq h

의 가능한 불일치를 보상하고

q^Ty

가 이 보상 조치의 비용인 보상 조치로 간주할 수 있다.

2단계 문제는 목적 함수와 제약 조건이 선형이기 때문에 ''선형''이다. 1단계 문제가 정수라면, 실행 가능한 집합이 이산적이 되도록 1단계 문제에 정수 제약 조건을 추가할 수 있다. 필요한 경우 비선형 목적 함수와 제약 조건을 통합할 수도 있다.^[5]

3. 2. 분포 가정

2단계 확률적 계획법에서는 불확실성을 나타내는 확률 변수의 분포가 알려져 있다고 가정한다. 이 분포는 다음의 여러 방법을 통해 추정할 수 있다.^[5]

과거 데이터: 과거 데이터가 존재하고, 그 분포가 미래에도 크게 변하지 않을 것이라고 예상되는 경우, 과거 데이터로부터 확률 변수의 분포를 추론할 수 있다.
경험적 분포: 표본의 경험적 분포를 확률 변수의 미래 값 분포에 대한 근사치로 사용할 수 있다.
베이즈 업데이트: 확률 변수에 대한 사전 모델이 있는 경우, 베이즈 업데이트를 통해 사후 분포를 얻을 수 있다.^[5]

3. 3. 시나리오 기반 접근법

확률 벡터 $\xi$가 유한한 수의 실현 값, 즉 "시나리오" $\xi_1, \dots, \xi_K$를 가지며, 각 시나리오에 해당하는 확률 $p_1, \dots, p_K$을 갖는다고 가정한다. 그러면 첫 번째 단계 문제의 목적 함수에 있는 기댓값은 다음과 같은 합으로 표현할 수 있다.

: $E[Q(x,\xi)]=\sum\limits_{k=1}^{K} p_kQ(x,\xi_k)$

그리고 두 단계 문제는 하나의 큰 선형 프로그래밍 문제로 공식화될 수 있다. 이를 원래 문제의 결정론적 등가라고 부른다.

$\xi$가 무한하거나 매우 많은 수의 가능한 실현 값을 갖는 경우, 표준 접근 방식은 이 분포를 시나리오로 나타내는 것이다. 이 접근 방식은 세 가지 주요 질문을 제기한다.

1. 시나리오 구성 방법

2. 결정론적 등가 해결 방법: CPLEX 및 GLPK와 같은 최적화기는 대규모 선형/비선형 문제를 해결할 수 있다. 위스콘신 대학교 매디슨에서 호스팅하는 NEOS 서버^[6]는 여러 최신 솔버에 대한 무료 액세스를 제공한다. 결정론적 등가의 구조는 벤더스 분해 또는 시나리오 분해와 같은 분해 방법^[7]을 적용하는 데 특히 적합하다.

3. "진정한" 최적값에 대해 얻은 솔루션의 품질을 측정하는 방법

이러한 질문들은 서로 연관되어 있다. 예를 들어, 구성된 시나리오 수는 결정론적 등가의 처리 가능성과 얻은 솔루션의 품질 모두에 영향을 미친다.

실제로 전문가의 의견을 바탕으로 시나리오를 구성할 수 있다. 구성된 시나리오의 수는 획득된 결정론적 등가물을 합리적인 계산 노력으로 해결할 수 있도록 비교적 적어야 한다. 몇 개의 시나리오만 사용하여 최적의 솔루션을 구해도, 단일 시나리오만 가정하는 솔루션보다 더 적응 가능한 계획을 제공하는 경우가 많다. 어떤 경우에는 시뮬레이션을 통해 그러한 주장을 확인할 수 있다. 이론적으로 획득된 솔루션이 합리적인 정확도로 원래 문제를 해결한다는 것을 보장하는 방법도 존재한다. 일반적으로 응용 프로그램에서 유일하게 실질적인 가치를 지니는 것은 ''1단계'' 최적 솔루션 $x^*$인데, 이는 거의 항상 무작위 데이터의 "실제" 실현이 구성(생성)된 시나리오 집합과 다르기 때문이다.

$\xi$가 $d$개의 독립적인 무작위 구성 요소를 포함하고, 각 구성 요소가 세 가지 가능한 실현(예: 낮음, 중간, 높음)을 갖는다고 가정하면, 총 시나리오 수는 $K=3^d$이다. 이러한 시나리오 수의 ''지수적 증가''는 합리적인 크기 $d$에서도 전문가 의견을 사용한 모델 개발을 매우 어렵게 만든다. $\xi$의 일부 무작위 구성 요소가 연속 분포를 갖는다면 상황은 더욱 복잡해진다.

3. 4. 확률적 선형 계획법 (Stochastic Linear Programming)

확률적 선형 계획법은 2단계 확률적 계획법의 특수한 경우로, 목적 함수와 제약 조건이 모두 선형 함수이다. 2단계 확률 계획법은 불확실성 하에서 의사 결정을 내리는 문제에 적용되며, 의사 결정은 두 단계로 나누어진다.

1단계: 불확실성이 실현되기 전에 결정을 내린다.
2단계: 불확실성이 실현된 후, 1단계에서 내린 결정을 바탕으로 추가적인 조치를 취한다.

2단계 선형 확률 계획법 문제는 다음과 같이 표현할 수 있다.

:

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

여기서

Q(x,\xi)

는 2단계 문제의 최적 값이며 다음과 같다.

:

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

$x$ 는 1단계 결정 변수 벡터
$y$ 는 2단계 결정 변수 벡터
$\xi$ 는 불확실성을 나타내는 확률 변수
$c, q, A, b, T, W, h$ 는 문제의 계수이다.

1단계에서는 1단계 결정의 비용

c^Tx

와 2단계 결정의 예상 비용

E_{\xi}[Q(x,\xi)]

을 최소화한다. 2단계에서는 불확실성이 실현된 후, 1단계 결정

x

와 실제 실현된

\xi

값을 바탕으로 최적의 2단계 결정

y

를 찾는다.

2단계 문제는 불확실성이 공개되었을 때 최적 행동을 설명하는 최적화 문제로 볼 수 있다. 또는 그 해를, 항

Wy

가 시스템

Tx\leq h

의 가능한 불일치를 보상하고

q^Ty

가 이 보상 조치의 비용인, 보상 조치로 간주할 수 있다.^[5]

확률적 선형 계획법은 여러 기간의 선형 계획법(LP) 모음으로 구성될 수 있으며, 각 LP는 동일한 구조를 가지지만 약간 다른 데이터를 갖는다.

3. 4. 1. 결정론적 등가 (Deterministic Equivalent)

유한 개의 시나리오가 있는 경우, 2단계 확률적 선형 계획법은 대규모 선형 계획법 문제로 모델링할 수 있다. 이 공식은 종종 결정론적 등가 선형 계획법(deterministic equivalent linear program)이라고 불리며, 결정론적 등가(deterministic equivalent)로 축약된다. 엄밀히 말하면 결정론적 등가란 최적의 1단계 결정을 계산하는 데 사용할 수 있는 모든 수학적 계획법을 의미하므로, 2단계 비용을 닫힌 형식으로 표현할 수 있는 경우 연속 확률 분포에도 존재한다.

예를 들어, 확률적 선형 계획법에 대한 결정론적 등가를 구성하기 위해, 각 시나리오

k=1,\dots,K

에 확률

p_k

를 할당한다. 그런 다음, 모든 시나리오의 제약 조건을 적용하여 목적 함수의 기대값을 최소화할 수 있다.

각 시나리오

k

에 대해 후기 변수

z_k

의 다른 벡터를 갖는다. 1기 변수

x

와

y

는 각 시나리오에서 동일하지만, 실현될 시나리오를 알기 전에 1기에 대한 결정을 내려야 하기 때문이다. 결과적으로,

x

와

y

만 포함하는 제약 조건은 한 번만 지정하면 되지만, 나머지 제약 조건은 각 시나리오에 대해 별도로 제공해야 한다.

3. 4. 2. 시나리오 생성 (Scenario Construction)

2단계 확률적 문제를 수치적으로 해결하기 위해, 확률 벡터

\xi

가 유한한 수의 가능한 실현 값, 즉 "시나리오"

\xi_1,\dots,\xi_K

를 가지며, 각 시나리오에 해당하는 확률 질량

p_1,\dots,p_K

을 갖는다고 가정한다.

\xi

가 무한하거나 매우 많은 수의 가능한 실현 값을 갖는 경우, 표준 접근 방식은 시나리오로 이 분포를 나타내는 것이다. 실제로 전문가의 미래에 대한 의견을 이끌어내 시나리오를 구성할 수 있다. 구성된 시나리오의 수는 획득된 결정론적 등가물을 합리적인 계산 노력으로 해결할 수 있도록 비교적 적어야 한다.

\xi

가

d

개의 독립적인 무작위 구성 요소를 포함하고, 각 구성 요소가 세 가지 가능한 실현(예: 낮음, 중간, 높음)을 갖는다면, 총 시나리오 수는

K=3^d

이다. 시나리오 수의 이러한 ''지수적 증가''는 합리적인 크기

d

에서도 전문가 의견을 사용한 모델 개발을 매우 어렵게 만든다.

몬테카를로 시뮬레이션을 사용하여 시나리오 집합을 관리 가능한 크기로 줄이는 것이 일반적인 접근 방식이다. 랜덤 벡터

\xi

의

N

개의 복제본 샘플

\xi^1,\xi^2,\dots,\xi^N

을 생성할 수 있다고 가정한다. 일반적으로 샘플은 독립적이고 동일하게 분포된(i.i.d.) 샘플으로 간주된다. 샘플이 주어지면 기대 함수

q(x)=E[Q(x,\xi)]

는 표본 평균으로 근사된다.

:

\hat{q}_N(x) = \frac{1}{N} \sum_{j=1}^N Q(x,\xi^j)

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

:

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

이 공식은 ''표본 평균 근사''(Sample Average Approximation, SAA) 방법으로 알려져 있다.^[6]^[7]

3. 4. 3. 통계적 추론 (Statistical Inference)

표본 평균 근사(SAA) 방법의 해는 통계적 추론을 통해 분석될 수 있다. 대수의 법칙에 따르면, 표본 평균 근사값은 표본 크기(

N

)가 무한대로 커짐에 따라 실제 값에 확률 1로 수렴한다.

중심 극한 정리에 의해, 고정된

x \in X

에 대해 표본 평균 추정량

\hat{g}_N(x)

는 점근적으로 정규 분포를 따른다. 즉, 큰

N

에 대해

\hat{g}_N(x)

는 평균

g(x)

와 분산

\frac{1}{N}\sigma^2(x)

를 갖는 정규 분포에 근사한다.

이를 통해

g(x)

에 대한

100(1-\alpha)

% 신뢰 구간을 다음과 같이 구성할 수 있다.

\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]

여기서

z_{\alpha/2}:=\Phi^{-1}(1-\alpha/2)

이고,

\Phi(\cdot)

는 표준 정규 분포의 누적 분포 함수이며,

\hat{\sigma}^2(x)

는

\sigma^2(x)

의 표본 분산 추정량이다.

\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

결론적으로,

g(x)

추정 오차는 확률적으로

O(\sqrt{N})

의 차수를 갖는다.

4. 응용 분야

확률적 계획법은 다양한 분야에 응용된다.
생물학확률적 동적 계획법은 행동생태학 등에서 동물 행동을 모델링하는 데 자주 사용된다.^[8]^[9] 최적 섭식 이론, 생물학적 생활사에서 조류의 둥지 떠나기, 기생체 벌의 산란 등과 같은 전환에 대한 모델의 경험적 테스트 결과, 이러한 모델링 기법이 행동 의사 결정의 진화를 설명하는 데 가치가 있는 것으로 나타났다.
경제확률적 동적 계획법은 불확실성이 존재하는 상황에서 의사 결정을 이해하는 데 유용한 도구이다. 불확실성 하에서의 자본 축적은 그 한 예시이며, 종종 자원 경제학자들이 날씨 등과 같은 불확실성이 발생하는 생물 경제적 문제를 분석하는 데 사용된다.
금융 공학다단계 확률적 계획법(Multi-stage stochastic programming)은 금융 공학, 특히 다단계 포트폴리오 최적화 문제 등에 적용된다.

예를 들어 시간 $t=0$ 에 $n$ 개의 자산에 투자할 초기 자본 $W_0$ 가 있고, 시간 $t=1,\dots,T-1$ 에 포트폴리오를 재조정할 수 있다고 가정한다. 각 기간 $t$ 에 현재 자산 $W_t$ 를 $n$ 개의 자산에 재분배하는 결정을 내린다.

각 기간 $t=1,\dots,T$ 의 총 수익률은 확률 과정 $\xi_1,\dots,\xi_T$ 를 형성하는 $\xi_t=(\xi_{1t},\dots,\xi_{nt})$ 로 나타낸다. 시간 $t$ 에서의 결정 $x_t=(x_{1t},\dots,x_{nt})$ 는 시간 $t$ 까지의 확률 과정의 이력 $\xi_{[t]}=(\xi_{1},\dots,\xi_{t})$ 의 함수( $x_t=x_t(\xi_{[t]})$ )이다.

이러한 일련의 함수 $x_t=x_t(\xi_{[t]})$ , $t=0,\dots,T-1$ 는 의사 결정 과정의 "구현 가능한 정책"을 정의한다. 최종 목표는 마지막 기간의 자산에 대한 기대 효용을 최대화하는 것이다( $\max E[U(W_T)]$ ). 이는 다단계 확률적 계획법 문제로, 최적화는 모든 구현 가능하고 가능한 정책에 대해 수행된다.

4. 1. 생물학적 응용

확률적 동적 계획법은 행동생태학 등에서 동물 행동을 모델링하는 데 자주 사용된다.^[8]^[9] 최적 섭식 이론, 생물학적 생활사에서 조류의 둥지 떠나기, 기생체 벌의 산란 등과 같은 전환에 대한 모델의 경험적 테스트 결과, 이러한 모델링 기법이 행동 의사 결정의 진화를 설명하는 데 가치가 있는 것으로 나타났다. 이 모델들은 일반적으로 2단계가 아닌 다단계로 구성된다.

4. 2. 경제적 응용

확률적 동적 계획법은 불확실성이 존재하는 상황에서 의사 결정을 이해하는 데 유용한 도구이다. 불확실성 하에서의 자본 축적은 그 한 예시이며, 종종 자원 경제학자들이 날씨 등과 같은 불확실성이 발생하는 생물 경제적 문제를 분석하는 데 사용된다.

4. 3. 금융 공학

Multi-stage stochastic programming^영어(다단계 확률적 계획법)은 금융 공학, 특히 다단계 포트폴리오 최적화 문제 등에 적용된다.

시간

t=0

에

n

개의 자산에 투자할 초기 자본

W_0

가 있고, 추가 현금 투입 없이 시간

t=1,\dots,T-1

에 포트폴리오를 재조정할 수 있다고 가정한다. 각 기간

t

에 현재 자산

W_t

를

n

개의 자산에 재분배하는 결정을 내리는데, 초기 투자 금액은

x_0=(x_{10},\dots,x_{n0})

으로 표현된다. 이때 각 자산에 투자하는 금액

x_{i0}

는 음수가 아니어야 하며, 총 투자 금액은 초기 자본과 같아야 한다(

\sum_{i=1}^{n}x_{i0}=W_0

).

각 기간

t=1,\dots,T

의 총 수익률은

\xi_t=(\xi_{1t},\dots,\xi_{nt})

로 나타내며, 이는 확률 과정

\xi_1,\dots,\xi_T

를 형성한다. 시간

t=1

에 포트폴리오를 재조정할 때, 첫 번째 기간의 수익이 실현되므로 이 정보를 바탕으로 투자 금액

x_1=(x_{11},\dots,x_{n1})

을 결정한다. 즉, 시간

t=1

에서의 결정은

\xi_1

의 함수(

x_1=x_1(\xi_1)

)이다. 마찬가지로, 시간

t

에서의 결정

x_t=(x_{1t},\dots,x_{nt})

는 시간

t

까지의 확률 과정의 이력

\xi_{[t]}=(\xi_{1},\dots,\xi_{t})

의 함수(

x_t=x_t(\xi_{[t]})

)이다.

이러한 일련의 함수

x_t=x_t(\xi_{[t]})

,

t=0,\dots,T-1

는 의사 결정 과정의 "구현 가능한 정책"을 정의한다. 이 정책이 확률 1로 모델 제약 조건(비음수 제약 조건

x_{it}(\xi_{[t]})\geq 0

, 자산 균형 제약 조건

\sum_{i=1}^{n}x_{it}(\xi_{[t]}) = W_t

)을 만족하면 "가능"하다고 한다.

기간

t=1,\dots,T

에서 자산

W_t

는 이전 기간의 투자와 수익률에 의해 결정된다(

W_t = \sum_{i=1}^{n}\xi_{it} x_{i,t-1}(\xi_{[t-1]})

).

최종 목표는 마지막 기간의 자산에 대한 기대 효용을 최대화하는 것이다(

\max E[U(W_T)]

). 이는 다단계 확률적 계획법 문제로, 최적화는 모든 구현 가능하고 가능한 정책에 대해 수행된다.

이 문제를 풀기 위해 동적 계획법 방정식을 사용할 수 있다. 시간 역순으로 문제를 고려하여, 각 단계에서 최적의 투자 결정을 내린다. 일반적인 경우 이 방정식을 풀기 어려울 수 있지만, 확률 과정

\xi_t

가 단계별로 독립적이면 문제가 단순화되어 조건부 기대값이 무조건부 기대값이 되고, 함수

Q_t(W_t)

가

\xi_{[t]}

에 의존하지 않게 된다.

5. 소프트웨어 도구

확률적 계획법 문제를 해결하기 위한 여러 소프트웨어 도구들이 개발되었다.

AIMMS: 확률적 계획법 문제 정의를 지원한다.
EMP SP: GAMS의 모듈로, 확률적 프로그래밍을 위한 기능을 제공한다. 여기에는 매개변수 분포, 확률 제약, VaR 및 기대 손실과 같은 위험 측정에 대한 키워드가 포함된다.
SAMPL: AMPL의 확장 세트로, 확률적 프로그램을 표현하기 위해 특별히 설계되었다. 확률 제약, 통합 확률 제약 및 강건 최적화 문제에 대한 구문을 포함한다.

이러한 언어들은 SMPS 인스턴스 레벨 형식을 생성하여 문제의 구조를 솔버에 효율적으로 전달할 수 있도록 돕는다.

5. 1. 모델링 언어

모든 이산 확률적 계획법 문제는 대수적 모델링 언어로 표현될 수 있으며, 각 단계에서 사용 가능한 정보의 구조를 준수하도록 명시적 또는 암묵적 비-예측성을 수동으로 구현한다.

일반적인 모델링 언어로 생성된 SP 문제의 인스턴스는 (시나리오 수에 선형적으로) 상당히 커지는 경향이 있으며, 해당 문제 클래스에 내재된 구조를 매트릭스가 잃게 된다. 그렇지 않으면 특정 분해 알고리즘으로 해결 시점에 활용할 수 있다.

SP를 위해 특별히 설계된 모델링 언어에 대한 확장이 나타나기 시작했다.

AIMMS - SP 문제의 정의를 지원한다.
EMP SP - 확률적 프로그래밍을 용이하게 하기 위해 생성된 GAMS의 모듈 (매개변수 분포, 확률 제약 및 VaR 및 기대 손실과 같은 위험 측정에 대한 키워드 포함).
SAMPL - 확률적 프로그램을 표현하기 위해 특별히 설계된 AMPL의 확장 세트 (확률 제약, 통합 확률 제약 및 강건 최적화 문제에 대한 구문 포함)

두 언어 모두 SMPS 인스턴스 레벨 형식을 생성할 수 있으며, 이는 문제의 구조를 중복되지 않는 형식으로 솔버에 전달한다.

참조

_[1] 서적 Lectures on stochastic programming: Modeling and theory http://www2.isye.gat[...] Society for Industrial and Applied Mathematics (SIAM) 2010-09-22
_[2] 서적 Introduction to Stochastic Programming https://doi.org/10.1[...] 2011
_[3] 서적 Applications of Stochastic Programming https://books.google[...]
_[4] 웹사이트 Stochastic Programming Community http://stoprog.org
_[5] 서적 A tutorial on Stochastic Programming http://www2.isye.gat[...]
_[6] 웹사이트 NEOS Server for Optimization http://www.neos-serv[...]
_[7] 서적 Stochastic Programming Elsevier
_[8] 서적 Dynamic modeling in behavioral ecology. Princeton University Press
_[9] 서적 Models of adaptive behaviour: an approach based on state Cambridge University Press
_[10] 간행물 Using Polynomial Approximations to Solve Stochastic Dynamic Programming Problems: or A "Betty Crocker " Approach to SDP. http://www.agecon.uc[...] University of California, Davis, Department of Agricultural and Resource Economics Working Paper
_[11] 서적 Lectures on stochastic programming: Modeling and theory http://www2.isye.gat[...] Society for Industrial and Applied Mathematics (SIAM) 2022-01-04
_[12] 서적 Introduction to Stochastic Programming https://doi.org/10.1[...] 2011
_[13] 서적 Applications of Stochastic Programming https://books.google[...]
_[14] 웹사이트 Stochastic Programming Community http://stoprog.org

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com