확률최적화

1. 개요 Introduction

불확실성은 거의 모든 의사결정 환경에 존재한다. 어떤 응용에서는 불확실성이 최적 결정에 미치는 영향이 작을 듯하여 안전하게 무시할 수 있다. 다른 환경에서는 최적해가 불확실성의 존재에 의해 크게 좌우될 것이 처음부터 분명하므로, 불확실성을 문제의 수학적 정식화에 명시적으로 반영하고 싶어진다. 느슨하게 말해 확률최적화(stochastic optimization)는, 이러한 확률적 요소를 포함하는 수학적 모형의 최적해를 특성화하거나 계산하기 위해 개발된 수학적·계산적 도구들의 집합이다.

수학적 관점에서 확률최적화에는 두 가지 주요 분야가 있다. 첫째는 확률제어(stochastic control)로, 최적화 해가 본질적으로 ‘무한차원’(또는 매우 높은 차원)인 최적화 문제를 다룬다. 둘째는 유한차원(finite-dimensional) 확률최적화로, 관련 문헌의 상당 부분이 (유한차원) 결정변수 벡터의 최적값을 수치적으로 계산하는 지능적 ‘탐색(search)’ 방법에 초점을 둔다.

2. 확률제어와 동적계획법 Stochastic Control & Dynamic Programming

관련된 개념을 보이기 위해 단일 제품 재고(inventory) 문제를 생각하자. 재고 보유 비용, 고객 수요를 충족하지 못하는 비용, 추가 발주 비용이 든다. 이 시스템의 주된 불확실성의 원천은 보유 제품에 대한 고객 수요의 예측 불가능성이다. 자연스러운 정식화는 수요가 알려진 분포를 갖는 확률과정을 따른다고 가정하는 것이다. 시각 t에 재고가 x일 때, 관리자는 주어진 시간지평에 걸친 기대비용을 최소화하도록 시각 t에 발주할 주문량 y^*(t, x)를 계산하고자 한다. t와 x의 함수로서 y^*(t, x)를 결정하는 것은 무한차원 최적화 문제이며, 최적 y^*(·)가 최적 정책(optimal policy, 최적 제어)을 결정한다.

고려하는 시스템의 동역학이 마르코프적이면, 최적 제어는 보통 동적계획원리(dynamic programming)로 특성화할 수 있다. 일반적 아이디어는, 시각 t의 마르코프 상태가 x일 때 결정지평의 끝까지 시스템을 운용하는 최소비용(또는 최대수익)으로 정의되는 가치함수 V(t, x)로 작업하는 것이다. 그러면 동적계획원리를 써서 V가 만족하는 이른바 해밀턴–야코비–벨만(HJB) 방정식을 세울 수 있고, V가 주어지면 최적 제어는 대체로 쉽게 계산된다.

이 아이디어를 위 재고 모형에 적용해 보자. 재고 x 보유의 기간당 비용을 h(x), 크기 y 주문의 비용을 c(y), 고객 수요를 (즉시) 충족하지 못하는 비용을 p, 기간 i의 고객 수요를 D_i라 하자. 주문 배송기간이 1이고, D_i가 독립이며(적절한 마르코프 구조를 유도), 결정지평이 [0, T]이면 다음이 성립한다.

다음 ‘종료조건(terminal condition)’을 따른다.

여기서 V(i, x)는 시각 i의 재고가 x일 때 시각 T까지 시스템을 운용하는 최소비용이다. HJB 방정식은 T에서 시작해 i에 대해 후방 반복(backward iteration)하는 일련의 T개 1차원 최적화로 풀 수 있다. V(i, x)가 계산되면, y^*(i, x)는 (1)의 우변을 최소화하는 임의의 값으로 둘 수 있다. 따라서 이 설정에서 최적 제어의 계산은 간단하다.

그러나 더 현실적인 다제품(multiproduct) 재고 설정에서는 문제가 생긴다. 여러 제품이 있으면 고객이 (현재 없는) 한 제품을 다른 제품으로 대체할 수 있어, 한 제품의 최적 주문량이 다른 제품들의 현재 재고수준에 의존한다. 자연스러운 마르코프 상태변수는 x = (x₁, …, x_l)(l은 제품 수)이 되고, V(i, x)를 (1)의 다제품 유사식으로 계산해야 한다. 이는 보통 수치적으로, x를 이산화하여 수행해야 한다. l이 크면 이산화 값의 수가 폭발하여 이른바 차원의 저주(curse of dimensionality)가 생기고, 실용적으로 많은 확률제어 문제를 수치적으로 다루기 어렵게 만든다.

그럼에도 HJB 방정식을 해석적 또는 수치적으로 풀 수 있는 흥미로운 문제군이 많다. 확률제어는 수리금융, 파산이론, 대기행렬이론 등에 성공적으로 적용되었다. 이 제어문제들의 공통점은, (순간) 행동의 선택이 순간 동역학과 순간 비용을 모두 바꾼다는 것이다. 유한지평 결정문제에서 나오는 HJB 방정식은 늘 (1)의 후방 재귀 구조를 갖는다. 무한지평으로 넘어가도, 목표가 할인비용 또는 정상상태(steady-state) 비용의 최소화라면 상당한 다루기 쉬움이 유지된다. 이런 무한지평 설정에서 V를 계산하는 방법으로는 축차(가치) 반복, 정책 반복, 선형계획법이 있다.

연속시간 확률제어에서는, 특히 연속 상태공간에서 미묘한 점이 생긴다. 어떤 문제에서는 거의 모든 시간 동안 제어가 행사되지 않고, 제어가 ‘측도 0’인 시간집합에서만 일어난다. 제어자가 가끔 시스템을 (불연속적으로) 점프시킬 수 있는 경우가 그 예다. 동적계획원리는 여전히 적용되지만 HJB 방정식이 이 거동을 적절히 반영해야 하며, 이러한 특이제어(singular control) 문제가 그렇다.

3. 유한차원 최적화와 지능적 탐색 Finite-dimensional Optimization & Search

앞서 말한 확률최적화의 둘째 주요 분야는, 유한차원 최적화 문제에서 최적값을 찾는 지능적 탐색이다. 이런 탐색은 보통 수치적으로 구현되며 결정변수의 수가 작거나 중간 규모일 때 가장 성공적이다. 이러한 최적화 문제는, 분석가가 처음부터 시스템을 작은 수의 파라미터로 매개되는 특정 제어군에서 고른 정책으로 제어하기로 결정할 때 자주 생긴다. 예컨대 위 재고 설정에서 이른바 (s, S) 정책 — 재고 위치가 s 미만일 때마다 S로 채우도록 주문하는 정책 — 으로 제어를 한정할 수 있다(사실 HJB로부터 최적 제어가 정확히 이 형태임을 보일 수 있다). 이런 정책이 주어지면, 기대비용을 최소화하는 s와 S의 값을 수치적으로 계산하는 일만 남는다.

몬테카를로 시뮬레이션이 거의 임의의 복잡한 확률모형을 다룰 수 있는 능력을 가졌으므로, 시뮬레이션 기반 최적화(simulation-based optimization)가 이런 문제를 푸는 인기 있는 수단이 되었다. θ = (θ₁, …, θ_d)를 결정변수 벡터라 하자. θ의 가능집합이 연속체이면 확률근사(stochastic approximation) 방법이 폭넓게 매력적이다. 확률근사는, 적당한 조건 아래 문제의 최적자로의 수렴이 보장되는 수열 (θ_n)을 생성하는 반복 절차다. 구체적으로 d = 1이고 목표가 다음 기대값을 최소화하는 것이라 하자.

그러면 반복은 다음 점화식으로 생성된다.

여기서 a > 0이고, W_n(θ_n)은 시뮬레이션으로 얻는 확률변수로 그 기대값이 도함수 α'(θ_n)에 근사적으로 같다는 성질을 갖는다. 즉 확률근사는, 결정변수의 함수로서 기대값의 매끄러움을 이용하여 도함수/기울기 정보로 반복한다.

W_n(θ_n)을 생성하는 가장 단순한 방법은 도함수에 대한 유한차분(finite difference) 근사로, 다음 형태를 취한다(h는 적당히 작게 선택).

여기서 Z_n(θ_n)과 Z_n(θ_n+h)는 각각 결정 파라미터 θ_n과 θ_n+h에 연관된 모형에서 적절히 시뮬레이션된다. (3)의 이러한 유한차분 구현을 키퍼–울포위츠(Kiefer–Wolfowitz) 절차라 한다.

편향 없는(unbiased) 도함수/기울기 추정량을 시뮬레이션할 수 있으면, 최적점으로의 수렴속도가 훨씬 빠른 확률근사를 얻을 수 있다. W(θ)를 다음을 만족하도록 생성하는 그러한 확률근사를 로빈스–먼로(Robbins–Monro) 절차라 한다.

이러한 편향 없는 추정량 W(θ)가 항상 이용 가능한 것은 아니지만, 편향 없는 시뮬레이션 가능 확률변수를 구성하는 두 가지 방법이 있다.

첫째 접근은 공통난수(common random numbers)를 써서, θ에 대해 충분히 매끄러운 Z(θ)의 실현값을 생성하여 편향 없음을 보장하는 것이다. 이산사건 시뮬레이션(통신망·생산시스템·재고 모형 등) 설정에서 이 방법은 무한소 섭동분석(infinitesimal perturbation analysis, IPA)으로 알려져 있다. 둘째 접근은, θ+h에서의 Z의 분포가 흔히 θ에서의 분포와 우도(likelihood)의 변화만큼만 다르다는 점을 이용한다. 즉 다음이 성립한다.

여기서 L(h)는 θ+h 아래 분포의 θ 아래 분포에 대한 상대적 우도를 기술하는 우도비(likelihood ratio)이다. 우도비 기울기 추정법(likelihood ratio gradient estimation, 점수함수법)이라 불리는 이 둘째 기법은 공통난수 접근보다 더 자주 적용 가능하다(다만 둘 다 적용될 때는 일반적으로 분산이 더 크다).

4. 반응표면법과 표본평균근사 Response Surfaces & Sample Average Approximation

연속 파라미터 최적화에 널리 쓰이는 또 다른 접근은 통계적 실험설계(experimental design)에 기원을 둔다. 기대값 α(θ)를 θ에 대한 저차 다항식(low-order polynomial)으로 모형화할 수 있다고 가정하고, (여러 θ 값에서 시뮬레이션한 데이터에 근거해) 회귀기반 방법으로 다항식 계수를 추정한다. 그런 다음 적합된 반응표면(fitted surface)의 최적자를 α(·)의 최적점 근사로 쓴다. 이 방법은 α(·)가 가정한 차수의 저차 다항식에 가까울 때 잘 작동하며, 때로 반복적으로 사용된다. 즉 근사 최적자를 구한 뒤 적절히 선택한 이웃에서 다시 시뮬레이션하여 국소적으로 새 반응표면을 보정하고, 거기서 새 근사 최적자를 계산한다.

많은 확률최적화 문제에서 결정변수가 연속이 아니라 이산적이다(예: 콜센터 상담원 수). 가능한 결정변수 조합 θ₁, …, θ_l의 수 l이 작으면, 최적 선택을 식별하는 데 최적시스템 선택(selection of best system) 방법이 자주 쓰인다. 이런 절차는 목적값이 가장 작거나(최소화의 경우) 표집 분산이 가장 큰 파라미터 벡터에 시뮬레이션 노력을 집중하려 한다. l이 큰 경우의 좋은 시뮬레이션 기반 절차는 현재 활발한 연구 영역이다.

어떤 응용에서는 결정문제를 이른바 확률선형계획(stochastic linear program)으로 정식화할 수 있다. 이런 정식화는 대규모 LP를 푸는 효율적 수치절차를 활용할 기회를 준다. 불확실성에 연관된 시나리오의 수가 작으면 이런 확률 LP를 정확히 풀 수 있다. 시나리오 수가 크거나 무한이면, 효율적 수치해법은 보통 시나리오 모집단에서 몬테카를로 표집(Monte Carlo sampling)을 한다.

참고 및 관련 표제어

부록. 이 글에 나온 용어 (배경지식 보충)

• 확률최적화 (stochastic optimization) — 불확실성이 들어간 모형의 기대값을 최적화(최소·최대)하는 수학적·계산적 도구의 총칭.
• 확률제어 (stochastic control) — 최적해가 정책 함수 전체인 무한차원 최적화 분야. 동적계획법/HJB가 도구.
• 가치함수 (value function) V(t, x) — 상태 x에서 끝까지 최적 운용했을 때의 최소비용(또는 최대수익).
• HJB 방정식 / 동적계획법 — 가치함수가 만족하는 후방 재귀식. 유한지평은 종료조건에서 거꾸로 푼다.
• 차원의 저주 (curse of dimensionality) — 상태변수 차원이 늘수록 계산량이 지수적으로 폭발하는 현상.
• 표본평균근사 (SAA, sample average approximation) — 기대 목적함수를 시뮬레이션 표본평균으로 바꿔 푸는 배치형 접근.
• 확률근사 (stochastic approximation) — 잡음 섞인 기울기 추정으로 최적점에 수렴하는 반복 절차(잡음 경사하강).
• 로빈스–먼로 (Robbins–Monro) — 편향 없는 기울기 추정량(E W = α')을 쓰는 빠른 확률근사.
• 키퍼–울포위츠 (Kiefer–Wolfowitz) — 기울기를 유한차분으로 추정하는 확률근사. 편향이 있어 더 느림.
• IPA / 우도비법 (likelihood ratio) — 편향 없는 기울기 추정을 만드는 두 기법: 무한소 섭동분석과 점수함수법.

한국보험시장 현황 Korea Market Practice

확률최적화는 국내 보험산업에서 K-ICS 내부모형 교정과 보험료율 산출 최적화에 직접 활용된다. IFRS17·K-ICS에서 요구하는 모형 모수는 관측 가능한 시장 가격과 내부 경험 통계를 동시에 적합해야 하므로, 목적함수가 비선형이고 잡음이 있는 불확실 최적화 문제 구조를 띤다. 확률경사하강법(SGD)과 SPSA 같은 확률적 기울기 추정 방법론이 ESG 교정과 준비금 파라미터 최적화에 응용된다.

보험료율 산출도 확률최적화의 관점에서 볼 수 있다. 손해율 목표, 손실비율 분포, 경쟁 시장 가격을 동시에 고려하는 요율 결정은 불확실한 미래 손실을 목적함수에 포함한 최적화 문제다. 자동차보험 참조요율 산출 과정에서 사용되는 GLM(일반화선형모형) 피팅도 우도 최대화라는 최적화 틀 위에 있으며, 부트스트랩을 통한 불확실성 정량화가 확률최적화의 실무 응용이다.

재보험 구조 최적화에서도 확률최적화가 쓰인다. 초과손실 재보험의 우선공제액(deductible)과 한도를 최적으로 설정하려면, 미래 대형 손실의 불확실 분포 아래에서 보험사 기대비용과 K-ICS 자본 절감을 동시에 최적화해야 한다. 이 문제는 해석해 없는 불확실 최적화 문제로, 시뮬레이션 기반 목적함수 값을 사용하는 무도함수(derivative-free) 탐색 알고리즘이 실용적이다.