Optimal bounds for numerical approximations of infinite horizon problems based on dynamic programming approach

기술 요약: 동적 계획법 접근법에 기반한 무한 시계 문제의 수치 근사법에 대한 최적 경계

문제 정의
본 논문은 $\mathbb{R}^n$ 내의 역학계에 의해 구동되는 무한 시계 최적 제어 문제의 수치 근사를 다룬다. 이러한 문제의 가치 함수(value function)는 1차 비선형 해밀턴-자코비-벨만(HAGB) 편미분 방정식의 점성 해(viscosity solution)로 특징지어진다. 다양한 근사 기법(유한 차분법, 세미-라그랑지안, 유한 체적법 등)이 존재하지만, 시간 및 공간 이산화를 모두 포함하는 완전 이산 방법(fully discrete methods)에 대해 엄격한 오차 경계를 설정하는 데에는 여전히 상당한 어려움이 남아 있다.

Falcone과 Ferretti [12] 및 기타 연구 [9, 11]를 참조하는 기존 문헌들은 완전 이산 세미-라그랑지안 방법의 오차 경계가 $O(k/h)$ 크기임을 명시하고 있다 (여기서 $h$는 시간 단계, $k$는 공간 격자 크기이다). 이 경계는 시간 단계 $h$가 감소함에 따라 $1/h$ 인자로 인해 오차가 악화됨을 시사한다. 그러나 저자들은 기존 문헌의 수치 실험(예: [4])에서 이러한 $1/h$ 거동이 관찰되지 않는다는 점에 주목하며, 이는 기존의 이론적 경계가 최적이 아님을 시사한다고 언급한다. 본 논문은 오차 분석을 재검토하여 더 타이트한 경계를 증명함으로써 이 불일치를 해결하는 것을 목표로 한다.

방법론
저자들은 개선된 오차 경계를 도출하기 위해 완전 이산 근사법에 대한 새로운 특징화를 제안한다. 방법론은 다음과 같이 진행된다:

1. 비용 범함수를 통한 재구성: 표준 동적 계획 원리에만 의존하는 대신, 저자들은 선형 보간 연산자 $I_k$를 각 시간 단계에서 시스템 역학 및 실행 비용에 적용한 완전 이산 비용 범함수 $\hat{J}_{h,k}$를 정의한다.
2. 해의 특징화: 정리 3은 완전 이산 가치 함수 $v_{h,k}$(이산 동적 계획 방정식에 의해 정의됨)가 가용한 제어 시퀀스의 공간에 대한 이 새로운 완전 이산 비용 범함수의 하한(infimum)과 정확히 일치함을 증명한다. 이는 [5]에서 사용된 반-이산(semi-discrete) 사례의 특징화와 유사하다.
3. 오차 분해: 오차 분석은 연속 비용 범함수 $\hat{J}$와 완전 이산 범함수 $\hat{J}_{h,k}$를 비교한다. 두 범함수의 차이는 연속 시스템 해 $y(t)$와 이산 보간 해 $\tilde{y}(t)$ 사이의 궤적 오차, 그리고 비용 및 역학 함수의 보간 오차를 분석함으로써 경계가 정해진다.
4. 정규성 가정: 분석은 제어 입력 $u(t)$에 대해 다음과 같은 다양한 정규성 가정을 고려한다:
   • 균등 연속(uniformly continuous) 제어 (유한한 수의 도약 불연속 허용).
   • 립시츠 연속(Lipschitz continuous) 제어.
   • 구간 상수(piecewise constant) 제어 (역학/비용 집합에 대한 볼록성 가정 하에).

주요 기여 및 결과

• 개선된 오차 경계: 본 논문의 주요 기여는 연속 가치 함수 $v$와 완전 이산 근사 $v_{h,k}$ 사이의 오차가 기존에 인용되었던 $O(k/h)$가 아니라 $O(h + k)$임을 증명한 것이다. 이는 1차 오일러 시간 이산화 및 피스 와이즈 리니어(piecewise linear) 공간 근사의 사용과 일치하는 시간 및 공간에 대한 1차 수렴성을 확립한다.
• 정리 4 (일반 경계): 시스템 역학 $f$와 비용 $g$에 대한 표준 립시츠 가정이 있고, $\lambda > L$ (여기서 $L$은 립시츠 상수로부터 유도된 상수)일 때, 오차는 다음과 같이 제한된다:
  $$|v(y) - v_{h,k}(y)| \leq C_1(h + k) + C_2 M_u$$
  여기서 $M_u$는 시간 간격 내에서의 제어의 진동(oscillation)을 측정한다.
• 정리 6 (립시츠 제어): 제어가 립시츠 연속인 경우, $M_u$는 $h$에 따라 스케일링되어 최적의 오차 경계인 $|v(y) - v_{h,k}(y)| \leq C(h + k)$를 갖는다.
• 정리 5 (균등 연속 제어): 제어가 단순히 균등 연속인 경우(유한한 도약을 허용하는 경우), $h, k \to 0$임에 따라 오차는 0으로 수렴하지만, 구체적인 속도는 연속성의 모듈러스(modulus of continuity)에 따라 달라진다.
• 구간 상수 제어 (정리 7): 유한 시계 문제를 위한 [6]의 논증을 무한 시계 문제로 적응시켜, 저자들은 $\{f(y,u), g(y,u)\}$ 집합에 대한 볼록성 가정(CA) 하에 수렴성을 증명한다. 그러나 이 적응은 무한 시계의 경우 더 약한 시간 수렴 속도를 초래한다:
  $$|v(y) - v_{h,k}(y)| \leq C_1(h + k) + C_2 (\log h)^2 h^{\frac{1}{1+\beta}}$$
  여기서 $\beta = \frac{\sqrt{n}L_f}{\lambda}$이다. 저자들은 이것이 무한 시계로 인해 유한 시계 결과와 비교했을 때 시간 수렴도에서 최대 절반 차수(half an order)의 손실을 나타낸다고 언급한다.

의의 및 주장
본 논문은 최적성 논증에 기반한 새로운 특징화가 실제 현장에서 관찰되는 수치적 거동을 성공적으로 설명한다고 주장한다. 즉, 기존 경계가 예측했던 $1/h$ 악화 현상이 나타나지 않는 이유를 밝혀낸다. $O(h+k)$ 경계를 증명함으로써, 저자들은 완전 이산 세미-라그랑지안 방법이 표준적인 정규성 가정 하에서 시간 및 공간에 대해 1차 수렴성을 달성함을 확인한다.

저자들은 최적성 논증에 뿌리를 둔 이 새로운 특징화가 현재 수렴 속도가 최적이 아닌 다른 유형의 해밀턴-자코비-벨만 방정식에도 적용될 잠재력이 있다고 겸손하게 제안한다. 그들은 립시츠 제어에 대해 1차 수렴성을 회복하지만, 더 약한 정규성(예: 지수 $\alpha$인 횔더 연속성)은 $O(h^\alpha)$의 수렴 속도를 나타내며, 무한 시계에 대한 구간 상수 제어 접근법은 유한 시계 결과에 비해 로그 페널티를 수반한다는 점을 명시적으로 밝힌다. 본 연구는 새로운 실험적 설정을 제안하는 것이 아니라, 해당 분야의 기존 오차 분석에 대한 이론적 교정을 제공하는 데 목적이 있다.