2025-11-23T02:40:16.760420

Dual-Regularized Riccati Recursions for Interior-Point Optimal Control

Sousa-Pinto, Orban
We derive closed-form extensions of Riccati's recursions (both sequential and parallel) for solving dual-regularized LQR problems. We show how these methods can be used to solve general constrained, non-convex, discrete-time optimal control problems via a regularized interior point method, while guaranteeing that each step is a descent direction of an Augmented Barrier-Lagrangian merit function. We provide MIT-licensed implementations of our methods in C++ and JAX.
academic

내부점 최적제어를 위한 이중 정규화 Riccati 재귀

기본 정보

  • 논문 ID: 2509.16370
  • 제목: Dual-Regularized Riccati Recursions for Interior-Point Optimal Control
  • 저자: João Sousa-Pinto, Dominique Orban
  • 분류: math.OC cs.MS cs.RO cs.SY eess.SY
  • 발표 시간: 2025년 10월 15일 (arXiv v2)
  • 논문 링크: https://arxiv.org/abs/2509.16370

초록

본 논문은 이중 정규화 LQR 문제를 풀기 위한 Riccati 재귀의 폐쇄형 확장(순차 및 병렬 버전 포함)을 유도한다. 저자들은 정규화 내부점법을 통해 이러한 방법을 사용하여 일반적인 제약, 비볼록, 이산시간 최적제어 문제를 풀 수 있음을 보여주며, 각 단계에서 증강 배리어-라그랑주 함수의 하강 방향을 보장한다. 논문은 C++ 및 JAX의 MIT 라이선스 구현을 제공한다.

연구 배경 및 동기

핵심 문제

본 연구가 해결하고자 하는 핵심 문제는 등식 및 부등식 제약을 가진 비볼록 이산시간 최적제어 문제를 효율적으로 풀 수 있는 방법이다. 기존 방법들은 다음과 같은 과제를 안고 있다:

  1. 계산 효율성 문제: 표준 내부점법은 최적제어 문제를 처리할 때 대규모 선형 시스템을 풀어야 하므로 계산 복잡도가 높다
  2. 수치 안정성: 정규화 매개변수가 0으로 수렴할 때 기존 방법이 수치적 불안정성을 보일 수 있다
  3. 병렬화의 어려움: 기존 방법은 병렬 계산 자원을 충분히 활용하기 어렵다

문제의 중요성

최적제어 문제는 로봇공학, 항공우주, 자동주행 등 다양한 분야에서 광범위하게 적용된다. 이러한 문제를 효율적으로 풀 수 있는 능력은 실시간 제어 시스템에 매우 중요하며, 특히 복잡한 제약을 처리해야 하는 경우에 그러하다.

기존 방법의 한계

  1. DDP 알고리즘: 실무에서 가장 널리 사용되는 방법이지만, 단일 사격(single-shooting) 방법으로서 상태 궤적을 독립적으로 따뜻하게 시작할 수 없다
  2. 표준 LQR 방법: 무제약 또는 단순 제약의 선형 시스템에만 적용 가능하다
  3. 기존 내부점법: IPOPT 같은 범용 솔버는 최적제어 문제의 구조적 특성을 충분히 활용할 수 없다

핵심 기여

  1. 이론적 기여: 이중 정규화 LQR 문제를 풀기 위한 폐쇄형 Riccati 재귀 확장 유도 (순차 및 병렬 버전)
  2. 알고리즘 혁신: 증강 배리어-라그랑주 함수를 merit 함수로 사용하여 하강 방향을 보장하는 정규화 내부점법 제안
  3. 수치 안정성: 정규화 매개변수 δ→0일 때 수치적으로 안정적인 알고리즘 설계로 표준 LQR 알고리즘 복구 가능
  4. 병렬화 알고리즘: 결합 스캔(associative scans)을 기반으로 O(log N) 병렬 시간 복잡도의 풀이 알고리즘 구현
  5. 소프트웨어 기여: 효율적인 희소 선형대수 연산을 지원하는 C++ 및 JAX 오픈소스 구현 제공

방법 상세 설명

작업 정의

다음의 이산시간 최적제어 문제를 고려한다:

min⁡x0,u0,…,xN∑i=0N−1fi(xi,ui)+fN(xN)\min_{x_0,u_0,\ldots,x_N} \sum_{i=0}^{N-1} f_i(x_i, u_i) + f_N(x_N)

제약 조건:

  • 초기 상태: x0=s0x_0 = s_0
  • 동역학 제약: xi+1=di(xi,ui),∀i∈{0,…,N−1}x_{i+1} = d_i(x_i, u_i), \forall i \in \{0,\ldots,N-1\}
  • 등식 제약: ci(xi,ui)=0,∀i∈{0,…,N−1}c_i(x_i, u_i) = 0, \forall i \in \{0,\ldots,N-1\}
  • 부등식 제약: gi(xi,ui)≤0,∀i∈{0,…,N−1}g_i(x_i, u_i) \leq 0, \forall i \in \{0,\ldots,N-1\}
  • 종료 제약: cN(xN)=0,gN(xN)≤0c_N(x_N) = 0, g_N(x_N) \leq 0

정규화 내부점법 프레임워크

증강 배리어-라그랑주 함수

배리어-라그랑주 함수를 다음과 같이 정의한다: L(x,s,y,z;μ)=f(x)−μ∑ilog⁡(si)+yTc(x)+zT(g(x)+s)L(x,s,y,z;\mu) = f(x) - \mu\sum_i \log(s_i) + y^T c(x) + z^T(g(x) + s)

증강 버전: A(x,s,y,z;μ,η)=L(x,s,y,z;μ)+η2(∥c(x)∥2+∥g(x)+s∥2)A(x,s,y,z;\mu,\eta) = L(x,s,y,z;\mu) + \frac{\eta}{2}(\|c(x)\|^2 + \|g(x)+s\|^2)

선형 시스템 풀이

각 반복에서 다음 선형 시스템을 풀어야 한다: [P0CTGT0S−1Z0IC0−1ηI0GI0−1ηI][ΔxΔsΔyΔz]=−∇L(x,s,y,z;μ)\begin{bmatrix} P & 0 & C^T & G^T \\ 0 & S^{-1}Z & 0 & I \\ C & 0 & -\frac{1}{\eta}I & 0 \\ G & I & 0 & -\frac{1}{\eta}I \end{bmatrix} \begin{bmatrix} \Delta x \\ \Delta s \\ \Delta y \\ \Delta z \end{bmatrix} = -\nabla L(x,s,y,z;\mu)

이중 정규화 LQR 문제

변수 소거를 통해 내부점법의 선형 시스템을 이중 정규화 LQR 문제로 변환한다: [PCTC−δI][xy]=−[sc]\begin{bmatrix} P & C^T \\ C & -\delta I \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = -\begin{bmatrix} s \\ c \end{bmatrix}

여기서 δ>0\delta > 0은 정규화 매개변수이고, 행렬 PP는 블록 대각 구조를 가지며, CC는 동역학 제약의 야코비안을 포함한다.

순차 알고리즘

후진 재귀

주요 변수를 다음과 같이 정의한다:

  • Vi=1δ(Fi−I)V_i = \frac{1}{\delta}(F_i - I): 값 함수 근사
  • vi=1δ(fi+ci)v_i = \frac{1}{\delta}(f_i + c_i): 오프셋 벡터

재귀 공식:

G_i = B_i^T W_{i+1} B_i + R_i
H_i = B_i^T W_{i+1} A_i + M_i^T
h_i = r_i + B_i^T g_{i+1}
K_i = -G_i^{-1} H_i
k_i = -G_i^{-1} h_i
V_i = A_i^T W_{i+1} A_i + Q_i + H_i^T K_i
v_i = q_i + A_i^T g_{i+1} + H_i^T k_i
W_i = (I + \delta V_i)^{-1} V_i
g_i = v_i + W_i(c_i - \delta v_i)

전진 재귀

제어 법칙 ui=Kixi+kiu_i = K_i x_i + k_i와 상태 전이 방정식을 통해 최적 궤적을 복구한다.

병렬 알고리즘

결합 스캔 병렬화

O(log N) 병렬 시간 복잡도를 달성하기 위해 결합 스캔을 사용한다:

  1. 구간 값 함수: Vi→j(xi,xj)V_{i \to j}(x_i, x_j)를 단계 i에서 j까지의 값 함수로 정의
  2. 조합 규칙: 구간 값 함수의 조합 연산을 확립하여 결합성을 만족
  3. 병렬 계산: 역방향 결합 스캔을 통해 모든 Vi→N+1V_{i \to N+1}을 병렬로 계산

아핀 함수 조합

전진 재귀를 아핀 함수의 조합으로 변환한다: xi+1=Mixi+mix_{i+1} = M_i x_i + m_i

결합 스캔을 사용하여 모든 아핀 변환을 병렬로 조합하여 O(log N)의 병렬 전진 전파를 구현한다.

기술적 혁신점

  1. 수치 안정성 설계: 재매개변수화를 통해 δ→0\delta \to 0일 때의 수치 문제 회피
  2. 하강 방향 보장: 탐색 방향이 증강 배리어-라그랑주 함수의 하강 방향임을 이론적으로 증명
  3. 구조화된 풀이: 최적제어 문제의 시간 구조를 충분히 활용하여 대규모 조밀 선형 시스템 풀이 회피
  4. 병렬화 설계: 함수형 프로그래밍의 결합 스캔을 기반으로 효율적인 병렬화 구현

실험 설정

구현 세부사항

논문은 두 가지 구현을 제공한다:

  1. C++ 구현:
    • SIP (Simple Interior Point) 프레임워크 기반
    • QDLDL 희소 솔버 통합 지원
    • 런타임 동적 메모리 할당 회피
    • 사용자 정의 KKT 시스템 솔버 지원
  2. JAX 구현:
    • 자동 미분 지원
    • GPU/TPU 가속
    • 완전한 단위 테스트 포함

검증 방법

  • 필요한 양정부호성을 만족하는 무작위 샘플에서 알고리즘 정확성 검증
  • δ=0\delta = 0일 때 표준 LQR 알고리즘과의 일치성 검증
  • 수치 안정성 테스트

실험 결과

정확성 검증

논문은 다음과 같은 방식으로 알고리즘의 정확성을 검증한다:

  1. 이론적 검증: δ=0\delta = 0일 때 알고리즘이 표준 LQR 알고리즘으로 축퇴
  2. 수치적 검증: 무작위 생성 테스트 케이스에서 해의 정확성 검증
  3. 단위 테스트: JAX 구현에 완전한 단위 테스트 스위트 포함

하강 방향 보장

정리 1.2는 Δx≠0\Delta x \neq 0 또는 Δs≠0\Delta s \neq 0일 때 방향 도함수가 다음을 만족함을 증명한다: D(A(⋅,⋅,y,z;μ,η);(Δx,Δs))(x,s)<0D(A(\cdot,\cdot,y,z;\mu,\eta);(\Delta x,\Delta s))(x,s) < 0

이는 알고리즘의 전역 수렴성을 보장한다.

복잡도 분석

  • 순차 알고리즘: O(N) 시간 복잡도
  • 병렬 알고리즘: O(log N) 병렬 시간 복잡도
  • 공간 복잡도: O(N), 문제 규모와 선형 관계

관련 연구

주요 연구 방향

  1. 고전적 LQR 방법: Kalman (1960)이 처음 Riccati 재귀를 유도
  2. 내부점법 적용: Rao 등 (1998)이 처음 내부점법을 모델 예측 제어에 적용
  3. 병렬 LQR: Särkkä와 García-Fernández (2021)이 첫 번째 O(log N) 병렬 LQR 알고리즘 제안
  4. 구조화된 솔버: FATROP 등 최근 연구가 구조화된 제약 처리 탐색

본 논문의 상대적 장점

  1. 이론적 완전성: 완전한 이론 분석 및 수렴성 보장 제공
  2. 수치 안정성: 정규화 매개변수 수렴 시 수치 문제 해결
  3. 실용성: 완전한 오픈소스 구현 제공
  4. 일반성: 일반적인 비볼록 제약 최적제어 문제 처리 가능

결론 및 토의

주요 결론

  1. 이중 정규화 LQR 문제의 폐쇄형 Riccati 재귀 확장 성공적으로 유도
  2. 정규화 내부점법과의 연결 확립으로 알고리즘 수렴성 보장
  3. O(log N) 병렬 시간 복잡도의 효율적인 알고리즘 구현
  4. 수치적으로 안정적이고 실용적인 오픈소스 구현 제공

한계

  1. 제약 유형 제한: 방법은 주로 LQR 형태로 변환 가능한 문제에 적용
  2. 양정부호성 요구: 알고리즘은 헤시안 행렬의 양정부호성 가정 필요
  3. 실제 성능: 대규모 실제 문제의 성능 비교 부족

향후 방향

  1. 더 일반적인 제약으로 확장: 경로 제약 및 더 복잡한 종료 제약 처리
  2. 적응형 정규화: 정규화 매개변수 선택 전략 자동화 개발
  3. 실제 응용 검증: 로봇 제어 등 실제 응용에서 방법의 유효성 검증

심층 평가

장점

  1. 이론적 기여 현저: 이중 정규화 기법과 Riccati 재귀를 처음 결합하여 완전한 이론 분석 제공
  2. 알고리즘 설계 우아함: 최적제어 문제의 시간 구조를 교묘하게 활용
  3. 수치 고려 주의깊음: 특히 수치 안정성 문제에 주목
  4. 구현 품질 높음: 두 가지 언어의 고품질 오픈소스 구현 제공
  5. 병렬화 혁신: 결합 스캔 기반 병렬화 방법의 이론적, 실무적 가치

부족한 점

  1. 실험 검증 제한: 주로 이론 검증 및 단순 수치 테스트로 대규모 실제 문제 비교 부족
  2. 성능 분석 부족: 상세한 계산 시간 및 메모리 사용량 분석 없음
  3. 적용 범위 논의 부족: 어떤 유형의 최적제어 문제에 가장 적합한지에 대한 심층 논의 부족
  4. 매개변수 선택 지침 부족: 정규화 매개변수 선택 전략에 대한 논의 미흡

영향력

  1. 학술적 가치: 최적제어 수치 방법에 새로운 이론적 도구 제공
  2. 실용적 가치: 오픈소스 구현이 방법의 보급 및 응용 촉진
  3. 재현성: 상세한 알고리즘 설명 및 오픈소스 코드로 재현성 보장
  4. 영감 제공: 이중 정규화 아이디어가 다른 최적화 문제 풀이에 영감 제공 가능

적용 시나리오

  1. 실시간 제어 시스템: 빠른 풀이가 필요한 모델 예측 제어 응용
  2. 대규모 최적화: 긴 시간 영역을 가진 최적제어 문제
  3. 병렬 계산 환경: 다중 코어 또는 GPU 자원을 충분히 활용할 수 있는 응용 시나리오
  4. 제약 최적화: 복잡한 등식 및 부등식 제약을 처리해야 하는 제어 문제

참고문헌

논문은 해당 분야의 중요 문헌을 인용하고 있으며, 여기에는 다음이 포함된다:

  • Kalman (1960): 최적제어 이론 기초
  • Blelloch (1989): 결합 스캔의 병렬 알고리즘 이론
  • Särkkä & García-Fernández (2021): 병렬 LQR 알고리즘
  • Wächter & Biegler (2006): IPOPT 내부점법 솔버

종합 평가: 이는 이론적 기여가 두드러지고 기술 혁신이 명백한 우수한 논문이다. 저자들은 이중 정규화 기법을 Riccati 재귀에 성공적으로 도입하여 수치 안정성을 유지하면서도 효율적인 병렬화를 구현했다. 실제 응용 검증 측면에서는 개선의 여지가 있지만, 이론적 가치와 오픈소스 기여로 인해 최적제어 수치 방법 분야의 중요한 진전이 되었다.