Дискретное ДП и численные методы

Аналитические решения задач оптимального управления возможны лишь для специальных структур (LQR, задача Рамсея с Кобб-Дугласом, задача Мертона). Большинство практических задач — нелинейные, многомерные, с дискретными решениями — приходится решать численно. Существует два больших семейства методов: дискретное динамическое программирование (через уравнение Беллмана) и прямые методы траекторной оптимизации (через нелинейное программирование). Их сравнение — важнейший практический вопрос.

Дискретное динамическое программирование

Задача: max Σ_{t=0}^{T−1} r(x_t, u_t) + V_T(x_T) при x_{t+1} = f(x_t, u_t), x_t ∈ S, u_t ∈ U.

Здесь S — множество состояний (например, |S| = 100), U — множество действий, r — мгновенная награда.

Алгоритм обратной индукции.

1. Инициализация: V_T(x) задано для всех x ∈ S (терминальная ценность).
2. Для t = T−1, T−2, ..., 0 и каждого x ∈ S: V_t(x) = max_{u ∈ U} [r(x, u) + V_{t+1}(f(x, u))].
3. Оптимальная политика: u*(t, x) = argmax_u [r(x, u) + V_{t+1}(f(x, u))].

Сложность: O(T · |S| · |U|). При T = 100, |S| = 100, |U| = 10: 10⁵ операций — мгновенно.

Численный пример: задача о ранце во времени

Турист собирает грибы в течение T = 10 дней. Состояние x ∈ {0, 1, ..., 100} — кг в рюкзаке (≤ 100). Действие u ∈ {0, 1, ..., 5} — кг сегодня. Награда r(x, u) = √u · (1 + 0.01·(100 − x)) — больше радости от грибов, когда рюкзак пустой.

Через VFI получаем оптимальную политику: в первые дни брать по 5 кг, в последние — снижать темп. Численно V₀(0) ≈ 12.4 — суммарная радость за 10 дней.

Проклятие размерности

При непрерывных состояниях нужна сетка. При dim(x) = d и N точек на ось — |S| ~ N^d. Для d = 5, N = 50: |S| = 3·10⁸ — на грани вычислимости. Для d = 10 — недостижимо.

Это «curse of dimensionality» — фундаментальный барьер для табличного ДП. Преодоление — ключевая тема современных методов (приближённое ДП, обучение с подкреплением).

Приближённое ДП

1. Сеточная аппроксимация с интерполяцией. Дискретизуем S на нерегулярную сетку (плотнее в «интересных» областях). Между узлами интерполируем V линейно или сплайнами. Сложность снижается, но точность зависит от качества сетки.

2. Параметрическая аппроксимация (ADP/RL). Параметризуем V*(x; θ) — нейросеть, полиномы Чебышёва, радиальные базисные функции. Параметры θ обучаем из уравнения Беллмана через TD-обучение:

L(θ) = Σ [r(x, u) + V(x'; θ⁻) − V(x; θ)]² → min.

Это основа DQN (Deep Q-Network, Mnih 2015), AlphaGo, AlphaZero.

3. Метод Монте-Карло (MCTS). Случайные выборки траекторий + усреднение. AlphaGo комбинирует MCTS с нейросетевой аппроксимацией.

Прямые методы траекторной оптимизации

Транскрипция: Непрерывная задача → нелинейная программа (NLP).

Шаг 1: Дискретизация времени t_0, t_1, ..., t_N с шагом Δt. Шаг 2: Дискретизация динамики (Эйлер, RK4): x_{k+1} = x_k + Δt·f(x_k, u_k). Шаг 3: Целевая: min Σ L(x_k, u_k)·Δt + φ(x_N). Шаг 4: Ограничения: x(0) = x₀, x(N) = x_T, u_min ≤ u_k ≤ u_max.

Получается NLP с переменными {x_0, ..., x_N, u_0, ..., u_{N−1}} — всего (n + m)·(N + 1) − m переменных и динамические ограничения.

Решение NLP: IPOPT (interior point), SNOPT (SQP). Для гладких задач — масштабируется до тысяч переменных.

Псевдоспектральные методы: Аппроксимация траектории полиномами Чебышёва или Лежандра. Высокая точность для гладких решений (экспоненциальная сходимость). Пакеты: GPOPS-II, DIDO, PSOPT.

Сравнение подходов

Реальные применения

• Mars Curiosity & Perseverance. Планирование маршрута марсохода: дискретное ДП на сетке высот (DEM-карты с орбиты), стоимость — энергия + риск опрокидывания.
• Управление запасами Amazon. Многоуровневая модель (поставщик → склад → региональный центр → клиент) — гигантское ДП с приближённой функцией ценности.
• Беспилотный автомобиль. MPC (Model Predictive Control) с горизонтом 3-5 секунд: на каждом шаге решается NLP для выбора траектории. Скорость решения 10-50 Гц.
• Электросети. Оптимальное управление зарядкой электромобилей в умной сети — стохастическое ДП с сотнями тысяч агентов, решается через приближённые методы.

Задание. «Мягкая посадка» ракеты: высота h(t), скорость v(t), масса m(t), управление — тяга u(t) ∈ [0, u_max]. Уравнения: ḣ = v, v̇ = −g + u/m, ṁ = −α·u. Начальные: h(0) = 1000 м, v(0) = −100 м/с, m(0) = 10000 кг. Конечные: h(T) = 0, v(T) = 0. Минимизировать расход топлива m(0) − m(T) при g = 9.81, u_max = 200000 Н, α = 0.001. (а) Дискретизуйте на N = 100 шагов. (б) Решите NLP через scipy.optimize.minimize (метод 'SLSQP'). (в) Постройте графики h(t), v(t), m(t), u(t). (г) Объясните, почему оптимальная стратегия близка к bang-bang.