Stochastic programming — 확률적 프로그래밍

확률적 프로그래밍 (영어: stochastic programming) — 모델의 일부 매개변수가 정확히 알려져 있지 않고 알려졌거나 추정된 확률 분포를 가진 확률 변수로 표현되는 불확실성 조건에서 최적화 문제를 해결하기 위한 모델과 방법을 개발하는 수학적 프로그래밍의 한 분야이다.

모든 데이터가 주어진 상수로 간주되는 결정론적 문제와 달리, 확률적 프로그래밍은 어떤 통계적 의미에서 최적인 해(또는 의사결정 정책)를 찾는 것을 목표로 한다. 가장 일반적으로 이는 목적 함수의 기댓값을 최소화하거나 최대화하는 것을 의미한다. 핵심 아이디어는 확률적 매개변수의 모든 가능한 실현에 대해 "평균적으로" 최선인 의사결정 정책을 찾는 것으로, 이는 유사한 조건에서 반복적으로 결정이 내려지는 문제(예: 재고 관리나 전력 시스템 관리)에 특히 중요하다.

문제의 수학적 정식화

일반적인 형태의 확률적 프로그래밍 문제는 다음과 같이 정식화할 수 있다: $\underset{x\in X}{\min }\mathbb{𝔼}[f(x,\xi )]$ 여기서:

• $x$ — 결정해야 할 제어 변수(결정)의 벡터.
• $X$ — 결정론적 제약 조건에 의해 정의되는 $x$의 허용 가능한 결정 집합.
• $\xi$ — 문제의 불확실한 매개변수(예: 수요, 가격, 기상 조건)를 나타내는 확률 벡터.
• $f(x,\xi )$ — 채택된 결정 $x$과 확률 벡터 $\xi$의 실현 모두에 의존하는 목적 함수.
• $\mathbb{𝔼}[\cdot ]$ — 벡터 $\xi$의 확률 분포에 대해 계산되는 기댓값 연산자.

다단계 확률적 모델의 기초가 되는 가장 중요한 원리는 비선행성 원리 (영어: non-anticipativity principle)이다. 이 원리는 어떤 단계에서 내려지는 결정이 그 시점까지 이용 가능한 정보에만 의존할 수 있으며 "미래를 내다볼" 수 없다는 것을 의미한다.

재결정권이 있는 2단계 문제

가장 일반적인 모델은 재결정권이 있는 2단계 확률적 프로그래밍 (영어: two-stage stochastic program with recourse)이다. 의사결정 과정은 두 단계로 나뉜다:

1. 1단계: "지금 여기에서"(here-and-now) 결정이 내려진다 — 벡터 $x$이 결정된다. 이 결정은 확률 벡터 $\xi$의 구체적인 실현이 알려지기 전에 이루어져야 한다.
2. 2단계: 확률적 사건이 발생한 후, 1단계 결정 $x$과 결과 $\xi$의 조합으로 인해 발생한 부정적 결과를 최소화하거나 유리한 기회를 활용하기 위한 수정 또는 보완 결정(recourse decision) — 벡터 $y(\xi )$이 내려진다.

수학적으로 2단계 확률적 선형 프로그래밍 문제는 다음과 같이 정식화된다: $\underset{x\in {\mathbb{ℝ}}^{n_1}}{\min }\{c^{T}x+{\mathbb{𝔼}}_{\xi }[Q(x,\xi )]\}$ 1단계 제약 조건: $Ax=b,x\ge 0$. 여기서 $Q(x,\xi )$은 보완 함수(recourse function)로, 2단계 문제의 최적값을 나타낸다: $Q(x,\xi )=\underset{y\in {\mathbb{ℝ}}^{n_2}}{\min }\{q(\xi {)}^{T}y\mid T(\xi )x+Wy=h(\xi ),y\ge 0\}$ 여기서 $\xi$은 매개변수 $q(\xi ),T(\xi )$과 $h(\xi )$를 포함하는 확률 벡터이고, $c,A,b$과 $W$는 결정론적 매개변수이다.

주요 성질 및 정리

• 볼록성: 이론의 근본적인 결과 중 하나는, 2단계 확률적 선형 프로그래밍 문제에서 기대 보완 함수 $Q(x)={\mathbb{𝔼}}_{\xi }[Q(x,\xi )]$가 볼록 함수라는 것이다. 이 성질은 매우 중요한데, 1단계 전체 문제가 볼록 프로그래밍 문제임을 보장하며, 이에 대해 효율적인 해법이 존재하고 전역 최적해와 지역 최적해가 일치하기 때문이다.
• 결정론적 등가 문제: 확률 벡터 $\xi$이 확률 $p_1,\dots ,p_K$을 가진 유한 개의 가능한 실현(시나리오) ${\xi }_1,\dots ,{\xi }_K$을 가지는 경우, 확률적 프로그래밍 문제를 하나의 큰 결정론적 최적화 문제로 재정식화할 수 있다. 이 경우 기댓값은 모든 시나리오에 대한 가중 합으로 대체된다. 그러나 이 문제의 크기는 시나리오 수에 따라 선형적으로 증가하므로, 이는 "차원의 저주"로 이어져 시나리오 수가 많을 경우 계산상 해결 불가능하게 된다.

강건 최적화와의 비교

확률적 프로그래밍은 불확실성 조건에서의 최적화에 대한 여러 접근법 중 하나이다. 강건 최적화와의 주요 차이점은 불확실성을 모델링하는 방식과 최적성 기준에 있다.

불확실성 조건에서의 최적화 접근법 비교

기준	확률적 최적화	강건 최적화
불확실성 표현	매개변수는 알려진 확률 분포를 가진 확률 변수	매개변수는 주어진 불확실성 집합에 속하며, 분포는 필요하지 않음
최적성 기준	목적 함수의 기댓값 최적화	최악의 시나리오에서의 최적화 (미니맥스)
해의 성격	"평균적으로" 최적인 정책으로, 드문 시나리오에서는 허용 불가능할 수 있음	모든 실현에 대해 허용 가능함이 보장된 해; 보수적일 수 있음

예시

• 신문 판매원 문제 (영어: newsvendor problem): 판매자가 정확한 미래 수요를 알지 못한 채 얼마나 많은 상품을 구입할지 결정해야 하는 고전적인 재고 관리 문제. 해는 과잉 재고로 인한 손실 위험과 부족으로 인한 기회 손실 위험 사이의 균형을 맞춘다.
• 농부 문제: 농부가 수확량에 영향을 미치는 미래 날씨를 알지 못한 채 전체 면적에서 여러 작물에 얼마나 많은 에이커를 배분할지 결정하는 문제. 날씨가 알려진 후, 농부는 수정 조치(예: 잉여분 판매 또는 시장에서 부족한 수확물 추가 구매)를 취할 수 있다.

같이 보기

• 수학적 프로그래밍
• 운용 과학
• 강건 최적화
• 동적 프로그래밍
• 제어 이론

각주

</references>