非线性规划中的差分动态规划（DDP）算法进阶题
字数 3414 2025-12-07 14:50:16

非线性规划中的差分动态规划（DDP）算法进阶题

让我们来探讨一个在最优控制和非线性规划中常用的算法——差分动态规划（Differential Dynamic Programming, DDP）。这个算法特别适合求解具有非线性动态约束的优化问题，例如机器人轨迹优化。我将通过一个具体题目，带你理解DDP的原理和步骤。

题目描述

假设我们有一个离散时间系统，其状态方程为：

\[x_{t+1} = f(x_t, u_t) \]

其中 \(x_t \in \mathbb{R}^n\) 是状态，\(u_t \in \mathbb{R}^m\) 是控制输入，\(f\) 是非线性函数。目标是找到控制序列 \(u_0, u_1, \dots, u_{T-1}\)，最小化总代价函数：

\[J = \ell_T(x_T) + \sum_{t=0}^{T-1} \ell_t(x_t, u_t) \]

这里 \(\ell_t\) 是阶段代价，\(\ell_T\) 是终端代价。

例如，设 \(n=2, m=1\)，具体形式为：

  • 动态方程：\(x_{t+1} = \begin{bmatrix} x_{t,1} + 0.1 x_{t,2} \\ x_{t,2} + 0.1 u_t \end{bmatrix}\)
  • 阶段代价：\(\ell_t(x_t, u_t) = 0.5 (x_{t,1}^2 + x_{t,2}^2 + u_t^2)\)
  • 终端代价：\(\ell_T(x_T) = 10 (x_{T,1}^2 + x_{T,2}^2)\)
  • 初始状态：\(x_0 = [1, 1]^T\)，时间步数 \(T=20\)。

我们需要用DDP算法求解最优控制轨迹。

解题步骤

1. 理解DDP的核心思想

DDP是一种迭代方法，在当前控制序列的附近进行二次近似，然后求解一个局部线性二次调节器（LQR）问题来更新控制。每次迭代包含：

  • 前向模拟：用当前控制序列 rollout 得到状态轨迹。
  • 反向传播：从最后一刻开始，计算代价函数的二次近似，并求解局部最优反馈律。
  • 前向更新：用新的反馈律重新模拟轨迹，得到改进的控制序列。

关键点是利用动态规划的递归结构，但不直接对原问题求解，而是对其二阶近似求解。

2. 算法详细步骤

步骤 2.1：初始化

  • 猜测一个初始控制序列 \(\bar{u}_0, \dots, \bar{u}_{T-1}\)（例如全零）。
  • 设置迭代次数上限（如 50 次）和容忍度（如代价变化小于 \(10^{-6}\)）。

步骤 2.2：前向模拟（Rollout）
用当前控制序列 \(\bar{u}_t\) 和动态方程 \(x_{t+1} = f(x_t, \bar{u}_t)\) 计算状态轨迹 \(\bar{x}_0, \dots, \bar{x}_T\)，并记录总代价 \(J\)。

步骤 2.3：反向传播（Backward Pass）
从 \(t=T\) 到 \(t=0\) 递归计算：

  1. 定义扩展代价函数（Action-Value Function）：

\[ Q_t(\delta x, \delta u) = \ell_t(\bar{x}_t + \delta x, \bar{u}_t + \delta u) + V_{t+1}(f(\bar{x}_t + \delta x, \bar{u}_t + \delta u)) \]

其中 \(V_{t+1}\) 是下一时刻的值函数（初始时 \(V_T(x) = \ell_T(x)\)）。

  1. 对 \(Q_t\) 进行二阶泰勒展开：
    • 计算梯度 \(Q_x, Q_u\) 和 Hessian 矩阵 \(Q_{xx}, Q_{xu}, Q_{ux}, Q_{uu}\)（在 \(\delta x=0, \delta u=0\) 处）。
    • 展开形式：

\[ Q_t(\delta x, \delta u) \approx Q^0_t + Q_x^T \delta x + Q_u^T \delta u + \frac{1}{2} \delta x^T Q_{xx} \delta x + \delta x^T Q_{xu} \delta u + \frac{1}{2} \delta u^T Q_{uu} \delta u \]

 这里 $Q^0_t = \ell_t(\bar{x}_t, \bar{u}_t) + V_{t+1}(\bar{x}_{t+1})$。
  1. 求解局部最优反馈律：
    • 最小化 \(Q_t\) 得到 \(\delta u^* = k_t + K_t \delta x\)，其中：

\[ k_t = -Q_{uu}^{-1} Q_u, \quad K_t = -Q_{uu}^{-1} Q_{ux} \]

  • 注意：如果 \(Q_{uu}\) 不正定，需正则化（加单位矩阵的倍数）。
  1. 更新值函数的参数：
    • 计算 \(V_x = Q_x + K_t^T Q_{uu} k_t + K_t^T Q_u + Q_{ux}^T k_t\)
    • 计算 \(V_{xx} = Q_{xx} + K_t^T Q_{uu} K_t + K_t^T Q_{ux} + Q_{ux}^T K_t\)
      （这些公式可简化，常用的是 \(V_x = Q_x + K_t^T Q_{uu} k_t + K_t^T Q_u + Q_{ux}^T k_t\)，但实践中可直接用更紧凑的表达式。）

步骤 2.4：前向更新（Forward Pass）

  • 从 \(t=0\) 到 \(T-1\) 执行：

\[ u_t^{\text{new}} = \bar{u}_t + k_t + K_t (x_t - \bar{x}_t) \]

\[ x_{t+1} = f(x_t, u_t^{\text{new}}) \]

  • 计算新轨迹的总代价 \(J_{\text{new}}\)。

步骤 2.5：线搜索与接受准则

  • 如果 \(J_{\text{new}} < J\)，接受新轨迹，并用它作为下一次迭代的参考轨迹。
  • 如果 \(J_{\text{new}} \ge J\)，减小步长（例如乘以 0.5）并重新执行前向更新（仅修改 \(k_t\) 的缩放因子）。
  • 重复直到代价不再显著下降。

3. 应用到例子

对于给定的动态方程和代价函数，我们需要计算导数：

  • 动态方程的雅可比：

\[ f_x = \begin{bmatrix} 1 & 0.1 \\ 0 & 1 \end{bmatrix}, \quad f_u = \begin{bmatrix} 0 \\ 0.1 \end{bmatrix} \]

  • 代价的导数：

\[ \ell_x = [x_1, x_2]^T, \quad \ell_u = u, \quad \ell_{xx} = I_2, \quad \ell_{uu} = 1, \quad \ell_{xu} = 0 \]

终端代价 \(\ell_T\) 的导数类似。

然后按上述步骤迭代。通常经过 10-20 次迭代，代价会收敛到一个最小值，控制序列会使状态趋于零（因为代价函数惩罚状态和控制的大小）。

4. 关键细节

  • DDP 与一般非线性规划的区别：它利用了问题的时间结构，通过动态规划递归求解，而不是一次性处理所有变量。
  • 正则化：为了防止 \(Q_{uu}\) 奇异，可添加 \(\mu I\) 保证正定性。
  • 复杂度：每次迭代 \(O(T (n+m)^3)\)，比直接求解整个非线性问题（变量数 \(T \cdot m\)）更高效。

5. 直观理解

可以把 DDP 看作“在轨迹附近迭代地进行 LQR 设计”。每次改进局部近似，最终收敛到局部最优轨迹。它相当于牛顿法在最优控制问题中的推广，但利用了动态规划分解。

如果你愿意，我可以进一步给出这个例子的迭代数值结果，或讨论 DDP 与经典的序列二次规划（SQP）之间的联系与区别。

非线性规划中的差分动态规划（DDP）算法进阶题 让我们来探讨一个在最优控制和非线性规划中常用的算法——差分动态规划（Differential Dynamic Programming, DDP）。这个算法特别适合求解具有非线性动态约束的优化问题，例如机器人轨迹优化。我将通过一个具体题目，带你理解DDP的原理和步骤。 题目描述 假设我们有一个离散时间系统，其状态方程为： \[ x_ {t+1} = f(x_ t, u_ t) \] 其中 \(x_ t \in \mathbb{R}^n\) 是状态，\(u_ t \in \mathbb{R}^m\) 是控制输入，\(f\) 是非线性函数。目标是找到控制序列 \(u_ 0, u_ 1, \dots, u_ {T-1}\)，最小化总代价函数： \[ J = \ell_ T(x_ T) + \sum_ {t=0}^{T-1} \ell_ t(x_ t, u_ t) \] 这里 \(\ell_ t\) 是阶段代价，\(\ell_ T\) 是终端代价。 例如，设 \(n=2, m=1\)，具体形式为： 动态方程：\(x_ {t+1} = \begin{bmatrix} x_ {t,1} + 0.1 x_ {t,2} \\ x_ {t,2} + 0.1 u_ t \end{bmatrix}\) 阶段代价：\(\ell_ t(x_ t, u_ t) = 0.5 (x_ {t,1}^2 + x_ {t,2}^2 + u_ t^2)\) 终端代价：\(\ell_ T(x_ T) = 10 (x_ {T,1}^2 + x_ {T,2}^2)\) 初始状态：\(x_ 0 = [ 1, 1 ]^T\)，时间步数 \(T=20\)。 我们需要用DDP算法求解最优控制轨迹。 解题步骤 1. 理解DDP的核心思想 DDP是一种迭代方法，在 当前控制序列的附近 进行二次近似，然后求解一个局部线性二次调节器（LQR）问题来更新控制。每次迭代包含： 前向模拟 ：用当前控制序列 rollout 得到状态轨迹。 反向传播 ：从最后一刻开始，计算代价函数的二次近似，并求解局部最优反馈律。 前向更新 ：用新的反馈律重新模拟轨迹，得到改进的控制序列。 关键点是利用动态规划的递归结构，但 不直接对原问题求解 ，而是对其二阶近似求解。 2. 算法详细步骤 步骤 2.1：初始化 猜测一个初始控制序列 \(\bar{u} 0, \dots, \bar{u} {T-1}\)（例如全零）。 设置迭代次数上限（如 50 次）和容忍度（如代价变化小于 \(10^{-6}\)）。 步骤 2.2：前向模拟（Rollout） 用当前控制序列 \(\bar{u} t\) 和动态方程 \(x {t+1} = f(x_ t, \bar{u}_ t)\) 计算状态轨迹 \(\bar{x}_ 0, \dots, \bar{x}_ T\)，并记录总代价 \(J\)。 步骤 2.3：反向传播（Backward Pass） 从 \(t=T\) 到 \(t=0\) 递归计算： 定义扩展代价函数 （Action-Value Function）： \[ Q_ t(\delta x, \delta u) = \ell_ t(\bar{x}_ t + \delta x, \bar{u} t + \delta u) + V {t+1}(f(\bar{x}_ t + \delta x, \bar{u} t + \delta u)) \] 其中 \(V {t+1}\) 是下一时刻的值函数（初始时 \(V_ T(x) = \ell_ T(x)\)）。 对 \(Q_ t\) 进行二阶泰勒展开 ： 计算梯度 \(Q_ x, Q_ u\) 和 Hessian 矩阵 \(Q_ {xx}, Q_ {xu}, Q_ {ux}, Q_ {uu}\)（在 \(\delta x=0, \delta u=0\) 处）。 展开形式： \[ Q_ t(\delta x, \delta u) \approx Q^0_ t + Q_ x^T \delta x + Q_ u^T \delta u + \frac{1}{2} \delta x^T Q_ {xx} \delta x + \delta x^T Q_ {xu} \delta u + \frac{1}{2} \delta u^T Q_ {uu} \delta u \] 这里 \(Q^0_ t = \ell_ t(\bar{x} t, \bar{u} t) + V {t+1}(\bar{x} {t+1})\)。 求解局部最优反馈律 ： 最小化 \(Q_ t\) 得到 \(\delta u^* = k_ t + K_ t \delta x\)，其中： \[ k_ t = -Q_ {uu}^{-1} Q_ u, \quad K_ t = -Q_ {uu}^{-1} Q_ {ux} \] 注意：如果 \(Q_ {uu}\) 不正定，需正则化（加单位矩阵的倍数）。 更新值函数的参数 ： 计算 \(V_ x = Q_ x + K_ t^T Q_ {uu} k_ t + K_ t^T Q_ u + Q_ {ux}^T k_ t\) 计算 \(V_ {xx} = Q_ {xx} + K_ t^T Q_ {uu} K_ t + K_ t^T Q_ {ux} + Q_ {ux}^T K_ t\) （这些公式可简化，常用的是 \(V_ x = Q_ x + K_ t^T Q_ {uu} k_ t + K_ t^T Q_ u + Q_ {ux}^T k_ t\)，但实践中可直接用更紧凑的表达式。） 步骤 2.4：前向更新（Forward Pass） 从 \(t=0\) 到 \(T-1\) 执行： \[ u_ t^{\text{new}} = \bar{u}_ t + k_ t + K_ t (x_ t - \bar{x} t) \] \[ x {t+1} = f(x_ t, u_ t^{\text{new}}) \] 计算新轨迹的总代价 \(J_ {\text{new}}\)。 步骤 2.5：线搜索与接受准则 如果 \(J_ {\text{new}} < J\)，接受新轨迹，并用它作为下一次迭代的参考轨迹。 如果 \(J_ {\text{new}} \ge J\)，减小步长（例如乘以 0.5）并重新执行前向更新（仅修改 \(k_ t\) 的缩放因子）。 重复直到代价不再显著下降。 3. 应用到例子 对于给定的动态方程和代价函数，我们需要计算导数： 动态方程的雅可比： \[ f_ x = \begin{bmatrix} 1 & 0.1 \\ 0 & 1 \end{bmatrix}, \quad f_ u = \begin{bmatrix} 0 \\ 0.1 \end{bmatrix} \] 代价的导数： \[ \ell_ x = [ x_ 1, x_ 2]^T, \quad \ell_ u = u, \quad \ell_ {xx} = I_ 2, \quad \ell_ {uu} = 1, \quad \ell_ {xu} = 0 \] 终端代价 \(\ell_ T\) 的导数类似。 然后按上述步骤迭代。通常经过 10-20 次迭代，代价会收敛到一个最小值，控制序列会使状态趋于零（因为代价函数惩罚状态和控制的大小）。 4. 关键细节 DDP 与一般非线性规划的区别：它利用了问题的 时间结构 ，通过动态规划递归求解，而不是一次性处理所有变量。 正则化：为了防止 \(Q_ {uu}\) 奇异，可添加 \(\mu I\) 保证正定性。 复杂度：每次迭代 \(O(T (n+m)^3)\)，比直接求解整个非线性问题（变量数 \(T \cdot m\)）更高效。 5. 直观理解 可以把 DDP 看作“在轨迹附近迭代地进行 LQR 设计”。每次改进局部近似，最终收敛到局部最优轨迹。它相当于牛顿法在最优控制问题中的推广，但利用了动态规划分解。 如果你愿意，我可以进一步给出这个例子的迭代数值结果，或讨论 DDP 与经典的序列二次规划（SQP）之间的联系与区别。