Stochastic dual dynamic programming (SDDP), the conventional stage-wise decomposition algorithm for large-scale multistage stochastic programs, approximates the value function by adding a supporting hyperplane at each iteration. In other words, SDDP is an algorithm that sequentially generates supporting hyperplane until converging to the solution. SDDP is known as a state-of-the-art method for solving multi-stage stochastic optimization problem, but it has a critical problem related to growing time complexity occurred by increasing size of subproblem as the algorithm progresses. Transformer is a sequence model that shows the best performance with an encoder-decoder structure based on attention mechanism. We propose a model that sequentially generates supporting hyperplanes to build piecewise linear lower bound for value function based on the structure of Transformer. Our model can decrease problem solving cost of SDDP without losing solution quality compared to original method across various multi-stage stochastic optimization problems.
다단 추계적 최적화 문제의 여러 해법 중 가장 보편적으로 활용되는 방법은 추계적 쌍대 동적 계획법이다. 추계적 쌍대 동적 계획법은 불확실한 상황에서 쌍대 변수를 활용하여 순차적으로 가치 함수의 받침 초평면을 찾고, 초평면의 집합인 조각별 선형 함수로 가치 함수를 근사한다. 이러한 방식은 하위 단계 문제의 크기를 증가시켜, 추계적 쌍대 동적 계획법의 시간 복잡도가 선형으로 늘게 된다. 시간 복잡도 문제로 인해 추계적 쌍대 동적 계획법을 대규모 문제에 적용하는 데 많은 어려움이 있다. 트랜스포머는 선도적인 순차 모형으로서 기계 번역, 음성 인식 등 다양한 분야에서 활용되고 있다. 이 연구에서는 트랜스포머를 활용하여 가치 함수의 받침 초평면을 순차적으로 생성하는 모델을 소개한다. 우리의 모델로 가치 함수를 근사하는 조각별 선형 함수를 짧은 시간 안에 생성할 수 있고 추계적 쌍대 동적 계획법보다 더 낮은 오차율의 근사 함수를 생성할 수 있다.
