非线性规划中的自适应差分动态规划(DDP)算法基础题
字数 3371 2025-11-04 08:32:42

非线性规划中的自适应差分动态规划(DDP)算法基础题

题目描述
考虑一个离散时间非线性动态系统的最优控制问题，该系统由以下方程描述：
状态方程：\(x_{k+1} = f(x_k, u_k)\)，其中 \(x_k \in \mathbb{R}^n\) 是状态向量，\(u_k \in \mathbb{R}^m\) 是控制向量，\(f\) 是一个非线性函数。
代价函数：\(J = \phi(x_N) + \sum_{k=0}^{N-1} L(x_k, u_k)\)，其中 \(\phi\) 是终端代价，\(L\) 是阶段代价，\(N\) 是时间总步数。
目标是找到控制序列 \(\{u_0, u_1, ..., u_{N-1}\}\) 来最小化总代价 \(J\)。这是一个典型的非线性规划问题，但由于其动态结构，常使用动态规划求解。差分动态规划(DDP)是一种利用动态规划原理并结合二阶近似的高效算法，特别适用于此类问题。自适应DDP则通过引入信赖域或步长控制机制来增强算法的鲁棒性和收敛性。

解题过程

第一步：问题理解与动态规划背景

  1. 核心思想：动态规划通过从最终时刻反向递推来求解最优控制。定义价值函数 \(V_k(x)\) 为从时刻 \(k\) 和状态 \(x\) 开始到终点的最小代价。
  2. 贝尔曼方程：\(V_k(x) = \min_u [ L(x, u) + V_{k+1}(f(x, u)) ]\)，边界条件 \(V_N(x) = \phi(x)\)。
  3. 挑战：对于非线性系统，贝尔曼方程通常无法解析求解。DDP通过局部二次近似来迭代求解。

第二步：DDP算法框架——二次近似

  1. 初始化：从一个初始控制序列 \(\mathbf{u}^0 = \{u^0_0, ..., u^0_{N-1}\}\) 开始，通过前向仿真得到名义状态轨迹 \(\mathbf{x}^0 = \{x^0_0, ..., x^0_N\}\)。
  2. 反向递推：从 \(k = N-1\) 到 \(k = 0\)，对价值函数 \(V_k(x)\) 和动态方程进行局部二次近似。
    • 令 \(Q_k(\delta x, \delta u)\) 为在名义轨迹点 \((x^0_k, u^0_k)\) 处的二阶近似：

\[ Q_k(\delta x, \delta u) = L(x^0_k + \delta x, u^0_k + \delta u) + V_{k+1}(f(x^0_k + \delta x, u^0_k + \delta u)) \]

  • 将其泰勒展开到二阶：

\[ Q_k(\delta x, \delta u) \approx Q_k^0 + Q_k^x \delta x + Q_k^u \delta u + \frac{1}{2} \begin{bmatrix} \delta x \\ \delta u \end{bmatrix}^T \begin{bmatrix} Q_k^{xx} & Q_k^{xu} \\ Q_k^{ux} & Q_k^{uu} \end{bmatrix} \begin{bmatrix} \delta x \\ \delta u \end{bmatrix} \]

 其中，$ Q_k^x $、$ Q_k^u $ 是梯度向量，$ Q_k^{xx} $、$ Q_k^{uu} $、$ Q_k^{xu} $ 是Hessian矩阵块（通过链式法则计算，涉及 $ f $、$ L $、$ V_{k+1} $ 的导数）。
  1. 最优控制更新：通过最小化 \(Q_k\) 得到控制修正量 \(\delta u^*_k\)。
    • 令 \(\frac{\partial Q_k}{\partial \delta u} = 0\)：\(Q_k^u + Q_k^{ux} \delta x + Q_k^{uu} \delta u = 0\)。
    • 解得：\(\delta u^*_k = - (Q_k^{uu})^{-1} (Q_k^u + Q_k^{ux} \delta x) = l_k + K_k \delta x\)，
      其中 \(l_k = - (Q_k^{uu})^{-1} Q_k^u\) 是反馈项，\(K_k = - (Q_k^{uu})^{-1} Q_k^{ux}\) 是增益矩阵。
  2. 价值函数更新：将 \(\delta u^*_k\) 代入 \(Q_k\)，得到价值函数的二次近似更新：

\[ \Delta V_k = -\frac{1}{2} l_k^T Q_k^{uu} l_k, \quad V_k^x = Q_k^x - K_k^T Q_k^{uu} l_k, \quad V_k^{xx} = Q_k^{xx} - K_k^T Q_k^{uu} K_k \]

第三步：自适应机制——信赖域与步长控制

  1. 问题：二次近似仅在局部有效，过大步长可能导致发散。自适应DDP引入信赖域约束 \(\|\delta u\| \leq \Delta\) 来限制控制更新幅度。
  2. 实现方式：在反向递推求解 \(\delta u^*_k\) 时，将其转换为带约束的优化问题：

\[ \min_{\delta u} Q_k(\delta x, \delta u) \quad \text{s.t.} \quad \|\delta u\| \leq \Delta_k \]

  • 通过调整信赖域半径 \(\Delta_k\) 来保证近似精度：计算实际代价减少量与预测减少量的比值 \(\rho\)：

\[ \rho = \frac{J_{\text{old}} - J_{\text{new}}}{\text{predicted decrease}} \]

  • 若 \(\rho\) 接近1（近似良好），则扩大 \(\Delta\)；若 \(\rho\) 很小（近似差），则缩小 \(\Delta\)。
  1. 前向仿真与迭代：用更新后的控制序列进行前向仿真，得到新轨迹和代价。根据 \(\rho\) 判断是否接受该次迭代，并调整 \(\Delta\) 用于下一次迭代。

第四步：算法流程总结

  1. 初始化：初始控制序列 \(\mathbf{u}^0\)，初始信赖域半径 \(\Delta^0\)。
  2. 迭代循环直到收敛：
    a. 前向仿真：用当前控制序列计算名义轨迹和代价 \(J_{\text{old}}\)。
    b. 反向递推：从 \(k = N-1\) 到 \(0\)，计算 \(Q\)-函数的导数和Hessian，在信赖域内求解 \(\delta u^*_k\)。
    c. 控制更新：\(u^{\text{new}}_k = u^0_k + \delta u^*_k\)。
    d. 新轨迹仿真：用 \(u^{\text{new}}_k\) 前向仿真，计算 \(J_{\text{new}}\)。
    e. 自适应调整：计算比值 \(\rho\)，根据 \(\rho\) 接受或拒绝更新，并调整 \(\Delta\)。
  3. 输出：最优控制序列和最小代价。

第五步：关键点与注意事项

  • 导数计算：需计算 \(f\) 和 \(L\) 的一阶和二阶导数，通常使用自动微分或数值差分。
  • 正定性：确保 \(Q_k^{uu}\) 正定，否则需正则化（如加单位矩阵）。
  • 收敛性：自适应机制保障全局收敛，但计算量较大。
  • 应用：适用于机器人轨迹规划、航天器控制等非线性动态优化问题。

通过以上步骤，自适应DDP将非线性规划问题转化为一系列局部二次规划问题，并利用信赖域自适应控制逼近精度，从而高效稳定地求解最优控制序列。

非线性规划中的自适应差分动态规划(DDP)算法基础题 题目描述 考虑一个离散时间非线性动态系统的最优控制问题，该系统由以下方程描述： 状态方程：\( x_ {k+1} = f(x_ k, u_ k) \)，其中 \( x_ k \in \mathbb{R}^n \) 是状态向量，\( u_ k \in \mathbb{R}^m \) 是控制向量，\( f \) 是一个非线性函数。 代价函数：\( J = \phi(x_ N) + \sum_ {k=0}^{N-1} L(x_ k, u_ k) \)，其中 \( \phi \) 是终端代价，\( L \) 是阶段代价，\( N \) 是时间总步数。 目标是找到控制序列 \( \{u_ 0, u_ 1, ..., u_ {N-1}\} \) 来最小化总代价 \( J \)。这是一个典型的非线性规划问题，但由于其动态结构，常使用动态规划求解。差分动态规划(DDP)是一种利用动态规划原理并结合二阶近似的高效算法，特别适用于此类问题。自适应DDP则通过引入信赖域或步长控制机制来增强算法的鲁棒性和收敛性。 解题过程 第一步：问题理解与动态规划背景 核心思想 ：动态规划通过从最终时刻反向递推来求解最优控制。定义价值函数 \( V_ k(x) \) 为从时刻 \( k \) 和状态 \( x \) 开始到终点的最小代价。 贝尔曼方程 ：\( V_ k(x) = \min_ u [ L(x, u) + V_ {k+1}(f(x, u)) ] \)，边界条件 \( V_ N(x) = \phi(x) \)。 挑战 ：对于非线性系统，贝尔曼方程通常无法解析求解。DDP通过局部二次近似来迭代求解。 第二步：DDP算法框架——二次近似 初始化 ：从一个初始控制序列 \( \mathbf{u}^0 = \{u^0_ 0, ..., u^0_ {N-1}\} \) 开始，通过前向仿真得到名义状态轨迹 \( \mathbf{x}^0 = \{x^0_ 0, ..., x^0_ N\} \)。 反向递推 ：从 \( k = N-1 \) 到 \( k = 0 \)，对价值函数 \( V_ k(x) \) 和动态方程进行局部二次近似。 令 \( Q_ k(\delta x, \delta u) \) 为在名义轨迹点 \( (x^0_ k, u^0_ k) \) 处的二阶近似： \[ Q_ k(\delta x, \delta u) = L(x^0_ k + \delta x, u^0_ k + \delta u) + V_ {k+1}(f(x^0_ k + \delta x, u^0_ k + \delta u)) \] 将其泰勒展开到二阶： \[ Q_ k(\delta x, \delta u) \approx Q_ k^0 + Q_ k^x \delta x + Q_ k^u \delta u + \frac{1}{2} \begin{bmatrix} \delta x \\ \delta u \end{bmatrix}^T \begin{bmatrix} Q_ k^{xx} & Q_ k^{xu} \\ Q_ k^{ux} & Q_ k^{uu} \end{bmatrix} \begin{bmatrix} \delta x \\ \delta u \end{bmatrix} \] 其中，\( Q_ k^x \)、\( Q_ k^u \) 是梯度向量，\( Q_ k^{xx} \)、\( Q_ k^{uu} \)、\( Q_ k^{xu} \) 是Hessian矩阵块（通过链式法则计算，涉及 \( f \)、\( L \)、\( V_ {k+1} \) 的导数）。 最优控制更新 ：通过最小化 \( Q_ k \) 得到控制修正量 \( \delta u^* _ k \)。 令 \( \frac{\partial Q_ k}{\partial \delta u} = 0 \)：\( Q_ k^u + Q_ k^{ux} \delta x + Q_ k^{uu} \delta u = 0 \)。 解得：\( \delta u^* _ k = - (Q_ k^{uu})^{-1} (Q_ k^u + Q_ k^{ux} \delta x) = l_ k + K_ k \delta x \)， 其中 \( l_ k = - (Q_ k^{uu})^{-1} Q_ k^u \) 是反馈项，\( K_ k = - (Q_ k^{uu})^{-1} Q_ k^{ux} \) 是增益矩阵。 价值函数更新 ：将 \( \delta u^* _ k \) 代入 \( Q_ k \)，得到价值函数的二次近似更新： \[ \Delta V_ k = -\frac{1}{2} l_ k^T Q_ k^{uu} l_ k, \quad V_ k^x = Q_ k^x - K_ k^T Q_ k^{uu} l_ k, \quad V_ k^{xx} = Q_ k^{xx} - K_ k^T Q_ k^{uu} K_ k \] 第三步：自适应机制——信赖域与步长控制 问题 ：二次近似仅在局部有效，过大步长可能导致发散。自适应DDP引入信赖域约束 \( \|\delta u\| \leq \Delta \) 来限制控制更新幅度。 实现方式 ：在反向递推求解 \( \delta u^* k \) 时，将其转换为带约束的优化问题： \[ \min {\delta u} Q_ k(\delta x, \delta u) \quad \text{s.t.} \quad \|\delta u\| \leq \Delta_ k \] 通过调整信赖域半径 \( \Delta_ k \) 来保证近似精度：计算实际代价减少量与预测减少量的比值 \( \rho \)： \[ \rho = \frac{J_ {\text{old}} - J_ {\text{new}}}{\text{predicted decrease}} \] 若 \( \rho \) 接近1（近似良好），则扩大 \( \Delta \)；若 \( \rho \) 很小（近似差），则缩小 \( \Delta \)。 前向仿真与迭代 ：用更新后的控制序列进行前向仿真，得到新轨迹和代价。根据 \( \rho \) 判断是否接受该次迭代，并调整 \( \Delta \) 用于下一次迭代。 第四步：算法流程总结 初始化 ：初始控制序列 \( \mathbf{u}^0 \)，初始信赖域半径 \( \Delta^0 \)。 迭代循环 直到收敛： a. 前向仿真 ：用当前控制序列计算名义轨迹和代价 \( J_ {\text{old}} \)。 b. 反向递推 ：从 \( k = N-1 \) 到 \( 0 \)，计算 \( Q \)-函数的导数和Hessian，在信赖域内求解 \( \delta u^ _ k \)。 c. 控制更新 ：\( u^{\text{new}}_ k = u^0_ k + \delta u^ _ k \)。 d. 新轨迹仿真 ：用 \( u^{\text{new}} k \) 前向仿真，计算 \( J {\text{new}} \)。 e. 自适应调整 ：计算比值 \( \rho \)，根据 \( \rho \) 接受或拒绝更新，并调整 \( \Delta \)。 输出 ：最优控制序列和最小代价。 第五步：关键点与注意事项 导数计算 ：需计算 \( f \) 和 \( L \) 的一阶和二阶导数，通常使用自动微分或数值差分。 正定性 ：确保 \( Q_ k^{uu} \) 正定，否则需正则化（如加单位矩阵）。 收敛性 ：自适应机制保障全局收敛，但计算量较大。 应用 ：适用于机器人轨迹规划、航天器控制等非线性动态优化问题。 通过以上步骤，自适应DDP将非线性规划问题转化为一系列局部二次规划问题，并利用信赖域自适应控制逼近精度，从而高效稳定地求解最优控制序列。