Двойная регуляризация рекурсий Риккати для оптимального управления внутренней точки

Основная информация

• 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
• Дата публикации: 15 октября 2025 г. (arXiv v2)
• Ссылка на статью: https://arxiv.org/abs/2509.16370

Аннотация

В данной статье выводятся замкнутые расширения рекурсий Риккати для решения двойной регуляризации задачи LQR (включая последовательную и параллельную версии). Авторы показывают, как использовать эти методы для решения общих ограниченных, невыпуклых, дискретных по времени задач оптимального управления с помощью регуляризованного метода внутренней точки, гарантируя, что каждый шаг является направлением убывания расширенной барьерно-лагранжевой функции. Статья содержит реализацию с лицензией MIT на C++ и JAX.

Исследовательский контекст и мотивация

Основная проблема

Основная проблема, которую решает данное исследование, заключается в эффективном решении невыпуклых дискретных по времени задач оптимального управления с ограничениями равенства и неравенства. Традиционные методы сталкиваются со следующими проблемами при решении таких задач:

1. Проблемы вычислительной эффективности: Стандартные методы внутренней точки требуют решения крупномасштабных линейных систем при работе с задачами оптимального управления, что приводит к высокой вычислительной сложности
2. Численная нестабильность: Традиционные методы могут проявлять численную нестабильность при стремлении параметра регуляризации к нулю
3. Сложность параллелизации: Существующие методы затрудняются в полном использовании ресурсов параллельных вычислений

Важность проблемы

Задачи оптимального управления имеют широкое применение в робототехнике, аэрокосмической промышленности, автономном вождении и других областях. Эффективное решение таких задач критически важно для систем управления в реальном времени, особенно в сценариях, требующих обработки сложных ограничений.

Ограничения существующих методов

1. Алгоритм DDP: Хотя это наиболее часто используемый метод на практике, как однократный метод стрельбы он не может независимо выполнять горячий старт траектории состояния
2. Стандартные методы LQR: Применимы только к линейным системам без ограничений или с простыми ограничениями
3. Существующие методы внутренней точки: Такие как универсальные решатели IPOPT, не могут полностью использовать структурные особенности задач оптимального управления

Основные вклады

1. Теоретический вклад: Выведены замкнутые расширения рекурсий Риккати для решения двойной регуляризации задачи LQR, включая последовательную и параллельную версии
2. Алгоритмическое инновация: Предложен регуляризованный метод внутренней точки, гарантирующий направление убывания, с использованием расширенной барьерно-лагранжевой функции в качестве функции достоинства
3. Численная стабильность: Разработан алгоритм, численно стабильный при δ→0, способный восстановить стандартный алгоритм LQR
4. Параллельный алгоритм: Реализован алгоритм с временной сложностью O(log N) для параллельных вычислений на основе ассоциативных сканирований
5. Программный вклад: Предоставлена реализация с открытым исходным кодом на C++ и JAX, поддерживающая эффективные операции разреженной линейной алгебры

Подробное описание методов

Определение задачи

Рассмотрим дискретную по времени задачу оптимального управления:

$\min_{x_0,u_0,\ldots,x_N} \sum_{i=0}^{N-1} f_i(x_i, u_i) + f_N(x_N)$

При ограничениях:

• Начальное состояние: $x_0 = s_0$
• Ограничения динамики: $x_{i+1} = d_i(x_i, u_i), \forall i \in \{0,\ldots,N-1\}$
• Ограничения равенства: $c_i(x_i, u_i) = 0, \forall i \in \{0,\ldots,N-1\}$
• Ограничения неравенства: $g_i(x_i, u_i) \leq 0, \forall i \in \{0,\ldots,N-1\}$
• Терминальные ограничения: $c_N(x_N) = 0, g_N(x_N) \leq 0$

Структура регуляризованного метода внутренней точки

Расширенная барьерно-лагранжева функция

Определим барьерно-лагранжеву функцию: $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;\mu,\eta) = L(x,s,y,z;\mu) + \frac{\eta}{2}(\|c(x)\|^2 + \|g(x)+s\|^2)$

Решение линейной системы

На каждой итерации необходимо решить линейную систему: $\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: $\begin{bmatrix} P & C^T \\ C & -\delta I \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = -\begin{bmatrix} s \\ c \end{bmatrix}$

где $\delta > 0$ — параметр регуляризации, матрица $P$ имеет блочно-диагональную структуру, $C$ содержит матрицы Якоби ограничений динамики.

Последовательный алгоритм

Обратная рекурсия

Определим ключевые переменные:

• $V_i = \frac{1}{\delta}(F_i - I)$: аппроксимация функции стоимости
• $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)

Прямая рекурсия

Восстановление оптимальной траектории через закон управления $u_i = K_i x_i + k_i$ и уравнение переходов состояния.

Параллельный алгоритм

Параллелизация с помощью ассоциативного сканирования

Использование ассоциативного сканирования для достижения временной сложности O(log N):

1. Функции стоимости на интервалах: Определение $V_{i \to j}(x_i, x_j)$, представляющей функцию стоимости с этапа i до j
2. Правила композиции: Установление операций композиции функций стоимости на интервалах, удовлетворяющих ассоциативности
3. Параллельные вычисления: Параллельное вычисление всех $V_{i \to N+1}$ посредством обратного ассоциативного сканирования

Композиция аффинных функций

Преобразование прямой рекурсии в композицию аффинных функций: $x_{i+1} = M_i x_i + m_i$

Использование ассоциативного сканирования для параллельной композиции всех аффинных преобразований, достигая O(log N) параллельного прямого распространения.

Технические инновации

1. Проектирование численной стабильности: Переопределение параметров для избежания численных проблем при $\delta \to 0$
2. Гарантия направления убывания: Теоретическое доказательство того, что направление поиска является направлением убывания расширенной барьерно-лагранжевой функции
3. Структурированное решение: Полное использование временной структуры задачи оптимального управления, избегание решения крупномасштабных плотных линейных систем
4. Проектирование параллелизации: Эффективная параллелизация на основе ассоциативного сканирования из функционального программирования

Экспериментальная установка

Детали реализации

Статья предоставляет две реализации:

1. Реализация на C++:
   • На основе фреймворка SIP (Simple Interior Point)
   • Поддержка интеграции разреженного решателя QDLDL
   • Избегание динамического выделения памяти во время выполнения
   • Поддержка пользовательских решателей KKT-системы
2. Реализация на JAX:
   • Поддержка автоматического дифференцирования
   • Ускорение на GPU/TPU
   • Полный набор модульных тестов

Методы верификации

• Верификация корректности алгоритма на случайных примерах, удовлетворяющих требуемым условиям положительной определённости
• Проверка согласованности со стандартным алгоритмом LQR при $\delta = 0$
• Тестирование численной стабильности

Результаты экспериментов

Верификация корректности

Статья проверяет корректность алгоритма следующим образом:

1. Теоретическая верификация: При $\delta = 0$ алгоритм деградирует в стандартный алгоритм LQR
2. Численная верификация: Верификация корректности решения на случайно сгенерированных тестовых примерах
3. Модульное тестирование: Реализация на JAX включает полный набор модульных тестов

Гарантия направления убывания

Теорема 1.2 доказывает, что при $\Delta x \neq 0$ или $\Delta s \neq 0$ производная по направлению удовлетворяет: $D(A(\cdot,\cdot,y,z;\mu,\eta);(\Delta x,\Delta s))(x,s) < 0$

Это гарантирует глобальную сходимость алгоритма.

Анализ сложности

• Последовательный алгоритм: Временная сложность O(N)
• Параллельный алгоритм: Параллельная временная сложность O(log N)
• Пространственная сложность: O(N), линейно зависит от размера задачи

Связанные работы

Основные направления исследований

1. Классические методы LQR: Калман (1960) впервые вывел рекурсию Риккати
2. Применение методов внутренней точки: Рао и др. (1998) впервые применили методы внутренней точки к предсказательному управлению моделью
3. Параллельное LQR: Särkkä и García-Fernández (2021) предложили первый параллельный алгоритм LQR с временной сложностью O(log N)
4. Структурированные решатели: Недавние работы, такие как FATROP, исследуют структурированную обработку ограничений

Преимущества данной работы

1. Теоретическая полнота: Предоставляет полный теоретический анализ и гарантии сходимости
2. Численная стабильность: Решает проблему численной нестабильности при стремлении параметра регуляризации к нулю
3. Практичность: Предоставляет полную реализацию с открытым исходным кодом
4. Универсальность: Может обрабатывать общие невыпуклые задачи оптимального управления с ограничениями

Выводы и обсуждение

Основные выводы

1. Успешно выведены замкнутые расширения рекурсий Риккати для двойной регуляризации задачи LQR
2. Установлена связь с регуляризованным методом внутренней точки, гарантирующая сходимость алгоритма
3. Реализован эффективный алгоритм с параллельной временной сложностью O(log N)
4. Предоставлена численно стабильная и практичная реализация с открытым исходным кодом

Ограничения

1. Ограничение типов ограничений: Метод в основном применим к задачам, которые можно преобразовать в форму LQR
2. Требование положительной определённости: Алгоритм требует предположения о положительной определённости матрицы Гессиана
3. Практическая производительность: Статья не содержит сравнения производительности на крупномасштабных практических задачах

Направления будущих исследований

1. Расширение на более общие ограничения: Обработка ограничений пути и более сложных терминальных ограничений
2. Адаптивная регуляризация: Разработка стратегий адаптивного выбора параметра регуляризации
3. Верификация на практических приложениях: Проверка эффективности метода на практических приложениях, таких как управление робототехникой

Глубокая оценка

Преимущества

1. Значительный теоретический вклад: Впервые объединены двойная регуляризация и рекурсии Риккати с полным теоретическим анализом
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

Общая оценка: Это отличная статья с выдающимся теоретическим вкладом и явными техническими инновациями. Авторы успешно внедрили технику двойной регуляризации в рекурсии Риккати, не только сохраняя численную стабильность, но и достигая эффективной параллелизации. Хотя в области верификации на практических приложениях есть место для улучшения, её теоретическая ценность и вклад в открытый исходный код делают её важным прогрессом в области численных методов оптимального управления.