Global Convergence of a Line-Search Filter Differential Dynamic Programming Method

기술 요약: 라인 서치 필터 미분 동적 계획법(DDP) 방법의 전역 수렴성

문제 정의
본 논문은 상태 및 제어에 대한 비선형 등식 제약 조건과 시스템 동역학이 존재하는 이산 시간 유한 시계열 최적 제어 문제(OCP)를 해결하는 과제를 다룬다. Mayne과 Jacobson이 제안한 미분 동적 계획법(DDP)은 알려진 국소 이차 수렴성을 가진 무제약 OCP를 위한 잘 확립된 방법이지만, 제약이 있는 문제에 적용할 경우 전역 수렴성 보장이 결여되는 경우가 많다. 순차 이차 계획법(SQP) 또는 프라이멀-듀얼(primal-dual) 정식화에 기반한 기존의 제약 DDP 변형들은 종종 국소 수렴 결과는 제공하지만 전역 분석은 누락한다. 본 연구가 목표로 하는 구체적인 공백은 Xu 등이 제안한, 일반적인 비선형 계획법(NLP) 필터 방법인 Wächter와 Biegler의 방식을 DDP 프레임워크에 적응시킨 라인 서치 필터 방법인 FilterDDP에 대한 엄격한 전역 수렴성 증명이 부족하다는 점이다.

방법론
저자들은 라인 서치 필터 절차를 DDP 구조와 통합한 FilterDDP 알고리즘의 공식적인 분석을 제안한다. 핵심 방법론은 일반적인 NLP 필터 방법에서 사용되는 감쇄 뉴턴 단계(damped Newton step)를 두 단계로 구성된 DDP 특화 시험점 생성 과정으로 대체하는 것이다:

1. 후방 재귀(Backward Recursion): 가치 함수 근사치와 라그랑주 승수(Lagrange multipliers)의 재귀적 업데이트. 이 단계는 섭동된 헤시안(perturbed Hessians)을 계산하고 선형 시스템을 풀어 제어, 승수, 상태에 대한 업데이트 방향($\zeta, \beta, \psi, \omega$)을 결정한다.
2. 전방 시뮬레이션(Forward Simulation): 계산된 업데이트와 단계 크기 $\alpha$를 기반으로 새로운 궤적을 생성하는 시뮬레이션 단계. 결정적으로, 이 단계는 DDP의 고유한 특성인 모든 반복(iteration)에서 동역학 제약 조건($x_{t+1} = f(x_t, u_t)$)이 충족되도록 보장한다.

알고리즘은 라그랑지안의 감소(목적 함수 척도)와 제약 위반 척도 사이의 균형을 맞추는 필터 메커니즘을 사용하여 시험점을 수용한다. 단계 수용 기준에는 라그랑지안 또는 제약 위반에 대한 충분한 감소 조건, "L-type" 반복을 위한 Armijo 유형 조건, 그리고 단계 크기가 너무 작아지거나 제약 자코비안(Jacobian)의 계수가 부족해질 때 호출되는 타당성 복구(feasibility restoration) 단계가 포함된다.

주요 기여
본 연구의 주요 기여는 FilterDDP 알고리즘의 전역 수렴성을 확립한 것이다. 저자들은 DDP의 특정 후방-전방 절차가 일반 NLP의 전역 수렴 분석에서 확립된 Wächter와 Biegler의 분석적 특성을 동일하게 만족함을 입증함으로써 이를 달성했다.

이 기여의 주요 기술적 단계는 다음과 같다:

• 단계의 등가성: DDP의 후방 재귀와 전방 시뮬레이션이 전역 수렴 분석의 관점에서 볼 때, OCP의 KKT 조건에 적용된 감쇄 뉴턴 단계와 동일하게 작동함을 증명함.
• 보조정리 도출: 업데이트 규칙을 제한하고, 비최적 가용 지점에 대한 하강 특성을 확립하며, 업데이트 규칙이 국소적으로 필터 기준(라그랑지안 및 제약 위반)을 선형화함을 보여주는 일련의 보조정리(Wächter와 Biegler의 연구 내 Lemma 1~3에 대응)를 확립함.
• 내부 점 확장(Interior Point Extension): 장벽 내부 점 방법(barrier interior point method)을 통해 부등식 제약 조건(특히 $u_t \geq 0$)을 처리하도록 전역 수렴 분석을 확장함. 이는 헤시안 근사를 적응시키고, 반복 횟수가 부등식 경계로부터 일정 거리 이상 유지되도록 하여 장벽 목적 함수와 그 도함수가 계속 정의되도록 보장하는 과정을 포함함.

결과
등식 제약 조건에 대한 표준적인 정칙성 및 매끄러움 가정(Assumptions G)과 장벽 확장에 대한 가정(Assumptions B) 하에서, 본 논문은 다음의 수렴성을 증명한다:

1. 타당성(Feasibility): FilterDDP에 의해 생성된 반복 시퀀스의 극한점들은 타당하다. 즉, 제약 위반 척도 $\theta(w_k)$는 $k \to \infty$일 때 0으로 수렴한다.
2. 최적성(Optimality): 반복 시퀀스가 유계(bounded)라면, 제약된 OCP에 대한 1차 최적 조건(KKT 조건)을 만족하는 적어도 하나의 극한점이 존재한다. 이는 투영된 기울기 성분의 노름으로 정의된 임계도(criticality measure) $\chi(w_k)$의 하한(limit inferior)이 0임을 보여줌으로써 입증된다.
3. 장벽 수렴성: 내부 점 확장과 관련하여, 반복 횟수가 부등식 제약의 경계로부터 균등하게 떨어져 있음이 증명되어, 최적화 과정 전반에 걸쳐 장벽 정식화의 유효성을 보장한다.

의의 및 주장
본 논문은 FilterDDP의 실질적인 성공과 엄격한 이론적 보장 사이의 간극을 공식적으로 메움으로써 그 의의를 주장한다. 저자들은 FilterDDP의 국소 이차 수렴성은 이미 확립되었으나(단계 수용 기준을 무시했을 때), 전역 수렴 분석은 누락되어 있었다고 언급한다. Wächter와 Biegler의 분석을 채택함으로써, 본 논문은 DDP 구조가 필터 방법의 전역 수렴 특성을 저해하지 않으며, 오히려 후방-전방 재귀가 일반 NLP 문맥에서의 뉴턴 단계와 동일한 역할을 효과적으로 수행함을 보여준다.

저자들은 이 분석이 타당성 복구 단계가 성공적으로 종료된다는 가정과 알고리즘이 비-KKT 지점에서 조기에 중단되지 않는다는 가정에 의존한다는 점을 겸허히 명시한다. 또한, (단계 수용 기준을 무시하지 않는) 빠른 국소 수렴성을 확립하는 것은 여전히 미해결 과제로 남아 있음을 밝히며, 향후 연구를 위해 일반적인 NLP에서 사용되는 것과 유사한 2차 보정 단계(second-order correction step)가 필요할 수 있음을 시사한다. 본 논문은 새로운 응용 사례나 실험적 벤치마크를 제안하기보다는 알고리즘의 이론적 수렴 특성에 엄격히 집중한다.