확률적 문제 해결 기법

확률적 선형계획법의 개요

확률적 선형계획법은 불확실성을 다루는 선형계획법의 확장이다. 여기서 불확실성은 주로 제약 조건이나 목적 함수의 계수에서 발생하며, 이러한 불확실성을 고려하여 최적해를 구하는 것이 목표다. 확률적 문제 해결 기법은 여러 가지가 있으며, 그 중 가장 많이 사용되는 방법들은 확률적 제약 조건(stochastic constraints)과 확률적 목적 함수(stochastic objective function)를 기반으로 한다.

확률적 문제 정의

확률적 선형계획 문제는 다음과 같이 정의할 수 있다. 기본적인 선형계획 문제는 다음의 형태를 가진다:

$\text{minimize } \mathbf{c}^\top \mathbf{x}$

$\text{subject to } \mathbf{A}\mathbf{x} \leq \mathbf{b}, \quad \mathbf{x} \geq 0$

여기서 $\mathbf{c}$ , $\mathbf{A}$ , $\mathbf{b}$ 는 고정된 값들이다. 하지만 확률적 선형계획 문제에서는 이러한 값들 중 일부가 확률 변수로 바뀌며, 다음과 같은 문제 형태가 된다:

$\text{minimize } \mathbb{E}[\mathbf{c}^\top \mathbf{x}]$

$\text{subject to } \mathbb{P}(\mathbf{A} \mathbf{x} \leq \mathbf{b}) \geq \alpha, \quad \mathbf{x} \geq 0$

여기서 $\mathbb{E}[\cdot]$ 는 기대값을 의미하며, $\mathbb{P}(\cdot)$ 는 확률을 나타낸다. $\alpha$ 는 일정 수준 이상의 신뢰도를 나타내는 값이다.

확률적 문제 해결의 접근 방식

샘플링 방법 (Sampling Methods)
샘플링 기반 접근 방식은 확률적 변수들을 여러 샘플로 추출하여 해당 샘플에 대해 문제를 해결하는 방법이다. 각 샘플에 대해 선형계획 문제를 풀고, 이를 기반으로 최적해를 추정한다. 이 과정은 다음과 같이 수행된다:
확률적 변수 $\mathbf{A}$ 와 $\mathbf{b}$ 의 분포에서 여러 샘플 $\mathbf{A}_i$ 와 $\mathbf{b}_i$ 를 추출한다.
각 샘플 $i$ 에 대해 다음과 같은 선형계획 문제를 해결한다:

$\text{minimize } \mathbf{c}^\top \mathbf{x}$

$\text{subject to } \mathbf{A}_i \mathbf{x} \leq \mathbf{b}_i, \quad \mathbf{x} \geq 0$

각 샘플에서의 해 $\mathbf{x}_i$ 들을 기반으로 최적해를 추정한다.
확률적 제약 조건의 변환
확률적 제약 조건 $\mathbb{P}(\mathbf{A} \mathbf{x} \leq \mathbf{b}) \geq \alpha$ 는 직접적으로 풀기 어렵기 때문에, 이를 결정론적 제약 조건으로 변환해야 한다. 가장 일반적인 방법은 확률적 제약 조건을 기대값 조건이나 VaR(Value-at-Risk) 또는 CVaR(Conditional Value-at-Risk)로 변환하는 것이다. 예를 들어:
기대값 조건
확률적 제약 조건을 기대값으로 근사하는 방법은 다음과 같다:

$\mathbf{A}_{\text{mean}} \mathbf{x} \leq \mathbf{b}_{\text{mean}}$

 여기서 $\mathbf{A}_{\text{mean}}$과 $\mathbf{b}_{\text{mean}}$은 각각 확률적 변수들의 기대값이다.

VaR (Value-at-Risk)
특정 확률 수준에서 발생할 수 있는 최대 손실을 제약 조건으로 설정하는 방법이다. $\alpha$ 수준에서의 VaR는 다음과 같이 정의된다:

$\mathbb{P}(\mathbf{A} \mathbf{x} > \mathbf{b}) = 1 - \alpha$

CVaR (Conditional Value-at-Risk)
VaR를 초과하는 손실의 평균을 제약 조건으로 설정하는 방법이다. CVaR는 다음과 같이 정의된다:

$\text{CVaR}_{\alpha} = \mathbb{E}[\mathbf{A} \mathbf{x} \mid \mathbf{A} \mathbf{x} > \text{VaR}_{\alpha}]$

확률적 목적 함수의 처리

확률적 목적 함수를 다루는 방법은 확률적 제약 조건과 유사하게, 기대값 기반 접근 또는 리스크 기반 접근을 사용할 수 있다. 이때, 목적 함수에 포함된 확률적 요소가 선형적인 경우에는 비교적 쉽게 해결이 가능하지만, 비선형적인 경우 더 복잡한 방법론이 필요하다.

기대값 기반 목적 함수
확률적 선형계획법에서 목적 함수가 확률 변수를 포함하는 경우, 가장 일반적인 방법은 기대값을 취하는 것이다. 즉, 확률적 목적 함수 $\mathbf{c}^\top \mathbf{x}$ 의 기대값을 최소화하는 문제는 다음과 같이 표현된다:

$\text{minimize } \mathbb{E}[\mathbf{c}^\top \mathbf{x}]$

여기서 $\mathbb{E}[\mathbf{c}]$ 는 $\mathbf{c}$ 의 기대값이다. 기대값을 사용하면, 불확실성에 대한 평균적인 성과를 최적화하는 해를 구할 수 있다. 하지만 이는 리스크를 충분히 고려하지 못할 수 있다.

VaR (Value-at-Risk) 기반 목적 함수
기대값 대신 VaR를 사용하는 방법은 특정 확률 수준에서 발생할 수 있는 최대 손실을 최소화하는 것이다. VaR를 이용한 확률적 목적 함수는 다음과 같이 설정된다:

$\text{minimize } \text{VaR}_{\alpha}(\mathbf{c}^\top \mathbf{x})$

이 방법은 불확실성에 대한 리스크를 어느 정도 반영하지만, VaR의 계산이 어렵고 복잡해질 수 있다.

CVaR (Conditional Value-at-Risk) 기반 목적 함수
VaR가 특정 수준에서의 손실만을 고려하는 반면, CVaR는 그 수준을 초과하는 손실에 대한 평균을 고려하는 방법이다. 확률적 선형계획법에서 CVaR를 최소화하는 문제는 다음과 같이 정의된다:

$\text{minimize } \text{CVaR}_{\alpha}(\mathbf{c}^\top \mathbf{x})$

이 방식은 VaR보다 리스크를 더 포괄적으로 다룰 수 있으며, 특히 극단적인 손실 상황을 잘 처리할 수 있다. CVaR는 다음과 같이 계산된다:

$\text{CVaR}_{\alpha} = \frac{1}{1 - \alpha} \int_{\alpha}^{1} \text{VaR}_{u} du$

확률적 문제 해결 기법의 알고리즘적 접근

확률적 선형계획 문제를 풀기 위해서는 일반적인 선형계획 문제를 풀 때와는 다른 알고리즘적 접근이 필요하다. 특히 확률적 제약 조건이나 목적 함수가 있는 문제를 결정론적 문제로 변환하거나, 확률 변수의 분포를 기반으로 샘플링하여 반복적으로 해결하는 방법이 사용된다.

시나리오 기반 접근법 (Scenario-Based Approach)
시나리오 기반 접근법은 확률적 변수들의 다양한 실현(scenarios)을 생성하여 각 시나리오에 대해 결정론적 문제를 풀고, 이를 기반으로 최적해를 도출하는 방법이다. 이 방법은 다음과 같은 단계로 이루어진다:
확률 변수의 분포에 따라 여러 시나리오를 생성한다.
각 시나리오에 대해 결정론적 선형계획 문제를 풀고, 해를 도출한다.
각 시나리오에서 도출된 해를 종합하여 최적해를 추정한다.
로버스트 최적화 (Robust Optimization)
로버스트 최적화는 확률적 변수들이 특정 범위 내에서 변동한다고 가정하고, 최악의 상황을 고려하여 해를 구하는 방법이다. 이 방법은 다음과 같은 문제로 정의된다:

$\text{minimize } \max_{\mathbf{c} \in \mathcal{U}} \mathbf{c}^\top \mathbf{x}$

여기서 $\mathcal{U}$ 는 $\mathbf{c}$ 가 가질 수 있는 불확실성 범위를 나타낸다. 이 방법은 불확실성에 강인한 해를 제공할 수 있지만, 보수적인 해가 도출될 수 있다는 단점이 있다.

샘플 평균 접근법 (Sample Average Approximation, SAA)

샘플 평균 접근법(SAA)은 확률적 선형계획 문제에서 확률 분포를 나타내는 샘플들을 사용하여 결정론적 문제로 변환하는 기법이다. 이를 통해 확률적 문제를 근사할 수 있으며, 샘플링 과정에서의 오차를 줄이는 데 유리하다. SAA의 기본 아이디어는 다음과 같다:

샘플링 과정
확률적 변수들의 분포에서 다수의 샘플을 생성한다. 예를 들어, $N$ 개의 샘플을 생성하여 다음과 같은 $N$ 개의 결정론적 문제로 변환할 수 있다:

$\text{minimize } \frac{1}{N} \sum_{i=1}^{N} \mathbf{c}_i^\top \mathbf{x}$

$\text{subject to } \mathbf{A}_i \mathbf{x} \leq \mathbf{b}_i, \quad \mathbf{x} \geq 0$

여기서 $\mathbf{A}_i$ 와 $\mathbf{b}_i$ 는 $i$ -번째 샘플에서 얻어진 확률적 변수들의 실현이다.

SAA 문제의 해결
샘플에서 얻어진 평균값을 기반으로 한 결정론적 문제를 해결한다. 이때 SAA 문제는 일반적인 선형계획 문제와 동일한 방식으로 해결할 수 있다.
해의 수렴성
샘플의 개수 $N$ 이 증가할수록 SAA 문제에서 도출된 해는 원래 확률적 문제의 최적해에 수렴한다. 이는 대수의 법칙에 따라 샘플 평균이 진정한 기대값에 수렴하는 성질에 기인한다. 따라서 충분히 많은 샘플을 사용할 경우 SAA 기법은 매우 유용한 해결 방법이 된다.
샘플링 오차
샘플 평균 접근법에서 중요한 점은 샘플링 오차를 줄이기 위해 충분히 많은 샘플을 사용하는 것이다. 샘플 개수가 적으면 최적해가 확률적 문제의 실제 해와 크게 달라질 수 있다. 이 문제를 해결하기 위해 Monte Carlo 기법을 사용하여 샘플 개수를 최적화하거나, 중요도 샘플링(Importance Sampling) 등을 통해 샘플의 질을 개선할 수 있다.

확률적 제약 조건의 처리 방법

확률적 제약 조건을 처리하는 여러 방법 중 가장 널리 사용되는 두 가지는 확률적 제약을 결정론적 제약으로 변환하는 것과, 제약 조건을 느슨하게 하여 더 유연한 해를 찾는 방법이다.

확률적 제약의 결정론적 근사
확률적 제약 조건을 처리하는 가장 간단한 방법은 이를 기대값 조건이나 신뢰 수준 조건으로 변환하는 것이다. 예를 들어, 다음의 확률적 제약 조건을:

$\mathbb{P}(\mathbf{A} \mathbf{x} \leq \mathbf{b}) \geq \alpha$

다음과 같이 결정론적 제약으로 근사할 수 있다:

$\mathbf{A}_{\text{mean}} \mathbf{x} \leq \mathbf{b}_{\text{mean}} + z_\alpha \sigma$

여기서 $\mathbf{A}_{\text{mean}}$ 과 $\mathbf{b}_{\text{mean}}$ 은 각각 확률적 변수들의 기대값이며, $z_\alpha$ 는 신뢰 수준 $\alpha$ 에 해당하는 표준 정규분포의 백분위수, $\sigma$ 는 확률적 변수들의 표준편차다.

안정성 기반 제약 조건
안정성 기반 접근은 확률적 제약 조건의 충족을 완화하는 방법이다. 즉, 확률적으로 제약을 만족시키기보다는, 일정 확률 수준에서 제약을 위반할 수 있는 여지를 남겨두는 것이다. 이 방법은 다음과 같이 표현될 수 있다:

$\mathbb{P}(\mathbf{A} \mathbf{x} \leq \mathbf{b}) \geq \alpha - \epsilon$

여기서 $\epsilon$ 은 허용 가능한 제약 위반 확률이다. 이를 통해 문제의 복잡성을 줄이고, 더 유연한 해를 찾을 수 있다.

로버스트 최적화와 확률적 선형계획법의 관계

확률적 선형계획법과 로버스트 최적화는 모두 불확실성을 처리하는 기법이지만, 두 방법의 접근 방식은 다르다. 확률적 선형계획법은 확률 분포에 따른 리스크를 최적화하는 반면, 로버스트 최적화는 모든 가능한 상황에서의 최악의 경우를 고려한다.

로버스트 최적화의 문제 형태

로버스트 최적화는 다음과 같은 문제 형태를 가진다:

$\text{minimize } \max_{\mathbf{c} \in \mathcal{U}} \mathbf{c}^\top \mathbf{x}$

여기서 $\mathcal{U}$ 는 불확실성 집합(uncertainty set)을 나타낸다. 로버스트 최적화는 모든 가능한 $\mathbf{c}$ 값에 대해 최악의 경우를 고려하여 해를 구한다.

확률적 선형계획법과의 차이점

로버스트 최적화는 주어진 불확실성 범위에서 최악의 경우를 고려하는 반면, 확률적 선형계획법은 확률 분포에 따라 리스크를 최소화한다. 두 방법은 각각의 장단점이 있으며, 문제의 특성에 따라 적절한 기법을 선택해야 한다.