ogier's blog

认识你的美

首页 归档 标签 关于

面试中遇到的ILQR算法相关问题

2024-12-12 11 min read # 时空联合 # 优化

为什么ilqr中只需要对前馈项k进行缩放，反馈K不需要：

(1) 理论基础：

  • 反馈增益K是基于局部线性化的最优反馈策略，它反映了在当前轨迹附近系统对状态偏差的最优响应方式
  • 这种局部特性使得K在小范围内保持有效性，不需要额外缩放

(2) 稳定性考虑：

δu = Kδx + d

  • K项确保了闭环系统的局部稳定性
  • 如果对K进行缩放，可能会破坏这种稳定性保证

(3) 实际效果：

  • 前馈项d主导着轨迹的大尺度更新
  • 反馈项Kδx主要起到局部校正作用
  • 在实践中，只缩放d就能有效控制搜索步长

为什么ilqr中会出现黑塞矩阵的奇异性问题

几个主要原因：

(1) 系统结构导致：

Rk=luu+BkTVk+1BkR_k=l_{uu}+B_k^TV_{k+1}B_k

  • 如果控制输入之间存在线性相关性，B_k的列向量可能线性相关
  • 这会导致R_k接近奇异

(2) 优化问题特性：

  • 某些控制维度对目标函数的影响很小时
  • 代价函数在某些方向上几乎是平的
  • 这会导致黑塞矩阵中出现接近零的特征值

(3) 数值计算问题：

  • 在迭代过程中，由于数值累积误差
  • 可能导致计算出的黑塞矩阵不再正定

数学表达： 当黑塞矩阵H的条件数很大时：

κ(H)=λmaxλmin≫1\kappa(H)=\frac{\lambda_{max}}{\lambda_{min}}\gg1

其中λ表示特征值，这种情况下求逆会不稳定。

所以需要正则化：

Hreg=H+μIH_{reg}=H+\mu I

确保：

λmin(Hreg)≥μ>0\lambda_{min}(H_{reg})\geq\mu>0

关于使用BFGS代替黑塞矩阵的优缺点：

优点：

(1) 计算效率：

  • 避免了直接计算复杂的二阶导数
  • 使用梯度信息递归更新，计算量小

(2) 数值稳定性：

  • BFGS保证近似黑塞矩阵正定
  • 天然避免了奇异性问题

(3) 内存效率：

  • 可以使用L-BFGS等限存版本
  • 适合大规模优化问题

缺点：

(1) 收敛特性：

  • 收敛速度可能比真实黑塞矩阵慢
  • 需要更多迭代次数

(2) 局部性：

Bk+1=Bk−BkskskTBkskTBksk+ykykTykTskB_{k+1} = B_k - \frac{B_k s_k s_k^T B_k}{s_k^T B_k s_k} + \frac{y_k y_k^T}{y_k^T s_k}

  • 只利用局部梯度信息构建近似
  • 可能捕捉不到全局曲率信息

(3) 初始化敏感：

  • 需要好的初始黑塞矩阵估计
  • 否则前期收敛较慢

建议使用场景：

  1. 当系统规模较大，计算真实黑塞矩阵开销很大时
  2. 当优化问题结构良好，梯度信息丰富时
  3. 当实时性要求高，允许轻微性能损失时

数学表达： 真实黑塞矩阵和BFGS近似的关系：

lim⁡k→∞∥Bk−∇2f(x∗)∥=0\lim_{k\to\infty}\|B_k-\nabla^2f(x^*)\|=0

但收敛速度：

  • 真实黑塞矩阵：二次收敛
  • BFGS：超线性收敛

在实际应用中，可以考虑：

  1. 混合策略：
  • 前几次迭代使用真实黑塞矩阵建立良好的初始近似
  • 后续使用BFGS更新
  1. 自适应切换：
  • 监控优化进展
  • 在需要时切换回真实黑塞矩阵
  1. 正则化结合：
  • 对BFGS近似也添加适当正则化
  • 进一步提高数值稳定性

SQP ilqr DDP之间的关系：

  1. 基本算法特点与联系

SQP (Sequential Quadratic Programming):

  • 是一种求解非线性约束优化问题的方法
  • 核心思想是将非线性优化问题在当前迭代点附近做二次近似
  • 每次迭代求解一个二次规划(QP)子问题

  • min⁡Δx12ΔxTHΔx+gTΔx s.t.c(x)+AΔx≤0\min_{\Delta x}\frac12\Delta x^TH\Delta x+g^T\Delta x\mathrm{~s.t.}\quad c(x)+A\Delta x\leq0

iLQR (iterative Linear Quadratic Regulator):

  • 专门用于解决轨迹优化问题的方法
  • 将非线性动力系统在轨迹附近线性化
  • 每次迭代求解LQR问题

  • min⁡ut∑t=0T−1(xtTQxt+utTRut) s.t.xt+1=Axt+But\min_{u_t}\sum_{t=0}^{T-1}(x_t^TQx_t+u_t^TRu_t)\mathrm{~s.t.}\quad x_{t+1}=Ax_t+Bu_t

DDP (Differential Dynamic Programming):

  • 是iLQR的扩展,考虑了二阶导数信息
  • 在轨迹附近做二次展开
  • 通过动态规划求解局部二次问题
  • Value function的二次近似:$$V(x,t)\approx\frac12xTV_{xx}x+V_xTx+V_0$$
  1. 算法之间的层级关系

这三种算法可以看作是一个逐步扩展的关系:

CopySQP(一般非线性优化)
  ↓
iLQR(针对轨迹优化的线性化)
  ↓  
DDP(考虑二阶信息的iLQR)
  1. 主要区别
  • 适用范围:
    • SQP: 通用非线性约束优化问题
    • iLQR: 主要用于轨迹优化和最优控制
    • DDP: 轨迹优化问题,但计算更精确
  • 计算复杂度:
    • SQP: 中等
    • iLQR: 较低
    • DDP: 较高(需计算二阶导数)
  • 收敛特性:
    • SQP: 在满足一定条件下具有二次收敛性
    • iLQR: 线性收敛
    • DDP: 在局部具有二次收敛性
  1. 具体应用场景

SQP适用于:

  • 一般非线性优化问题
  • 有显式约束的问题
  • 机器人运动规划的高层优化

iLQR适用于:

  • 机器人轨迹优化
  • 模型预测控制(MPC)
  • 连续时间系统控制

DDP适用于:

  • 高精度轨迹优化
  • 对实时性要求不高的离线优化
  • 需要考虑系统动力学二阶特性的场合
  1. 理论基础的联系

所有这些方法都基于以下共同的理论基础:

  • 泰勒展开近似
  • 迭代优化策略
  • 局部二次/线性近似
  • KKT条件

区别在于:

  • SQP关注约束处理
  • iLQR专注于动力学系统
  • DDP增加了二阶动态信息
  1. 计算效率对比

若问题规模为n,时间步长为T:

  • SQP: O(n³)每次迭代
  • iLQR: O(Tn)每次迭代
  • DDP: O(Tn³)每次迭代

这些算法的选择通常需要在精度和计算效率之间做权衡。

  1. 总结
  • 如果是一般非线性优化问题,优先考虑SQP
  • 如果是实时轨迹优化,优先考虑iLQR
  • 如果需要高精度且可以接受较高计算成本,考虑DDP

这三种算法各有特点和适用场景,在实际应用中经常需要根据具体问题特点来选择合适的算法。有时也会将它们结合使用,比如用SQP求解高层规划,用iLQR求解底层轨迹跟踪。

ilqr和SQP的速度对比：

主要关注iLQR相对于SQP速度更快的原因，以及它们在精度上的权衡。

  1. 速度差异的主要原因：

计算复杂度的来源：

SQP的主要计算开销：

  • 需要求解完整的QP子问题
  • 需要计算和更新Hessian矩阵
  • 处理一般非线性约束
  • 求解KKT系统的计算成本高
# SQP的典型迭代过程
def sqp_iteration(x, constraints):
    # 1. 计算完整Hessian矩阵 - O(n³)操作
    H = compute_hessian(x)
    
    # 2. 计算所有约束的雅可比矩阵
    J = compute_jacobian(constraints)
    
    # 3. 求解完整的QP子问题 - 需要迭代求解器
    dx = solve_qp(H, J, constraints)
    
    return x + dx

iLQR的计算特点：

  • 仅处理动力学约束
  • 利用问题的特殊结构(时序性)
  • 使用Riccati递归来高效求解
  • 避免直接处理大规模矩阵
# iLQR的典型迭代过程
def ilqr_iteration(x_traj, u_traj):
    # 1. 前向传播 - O(T)操作
    x_new = forward_rollout(x_traj, u_traj)
    
    # 2. 反向传播计算控制更新 - O(T)操作
    K, k = backward_pass(x_new)
    
    # 3. 线性搜索更新轨迹 - O(T)操作
    x_next, u_next = forward_pass(K, k)
    
    return x_next, u_next
  1. 精度与速度的权衡：

iLQR的近似性：

iLQR确实做了一些近似：

  1. 只考虑动力学约束的线性化：

    f(xt+1,ut)≈Atxt+Btutf(x_{t+1}, u_t) \approx A_tx_t + B_tu_t

  2. 代价函数的二次近似：

    l(xt,ut)≈12[xtut]T[QtNtNtTRt][xtut]l(x_t,u_t) \approx \frac{1}{2}\begin{bmatrix}x_t\\u_t\end{bmatrix}^T\begin{bmatrix}Q_t & N_t\\N_t^T & R_t\end{bmatrix}\begin{bmatrix}x_t\\u_t\end{bmatrix}

SQP的精确性：

SQP保持了更多的问题结构：

  1. 完整的约束处理：

    c(x)+∇c(x)TΔx≤0c(x) + \nabla c(x)^T\Delta x \leq 0

  2. 更精确的二次近似：

    min⁡Δx12ΔxT∇2L(x,λ)Δx+∇f(x)TΔx\min_{\Delta x} \frac{1}{2}\Delta x^T \nabla^2L(x,\lambda)\Delta x + \nabla f(x)^T\Delta x

  3. 具体比较：

速度因素：

iLQR:
- 时间复杂度：O(T·n)
- 存储需求：O(T·n)
- 每次迭代快速

SQP:
- 时间复杂度：O(n³)
- 存储需求：O(n²)
- 每次迭代较慢

精度因素：

iLQR:
+ 对轨迹优化问题足够精确
- 难以处理一般约束
- 可能错过全局最优

SQP:
+ 可以达到很高精度
+ 可以处理一般约束
+ 在满足条件时可证明局部最优
  1. 为什么iLQR在轨迹优化中依然有效：
  1. 问题结构利用：
  • 利用系统动力学的特殊结构
  • 时序分解降低计算复杂度
  • Riccati方程提供高效求解
  1. 实践考虑：
  • 实时控制不需要极高精度
  • 轨迹优化通常只需要局部最优解
  • 快速迭代更适合在线应用
  1. 数学表达的差异：

iLQR的优化问题：

min⁡u0:T−1∑t=0T−1l(xt,ut)+lf(xT)\min_{u_{0:T-1}} \sum_{t=0}^{T-1} l(x_t,u_t) + l_f(x_T)

s.t.xt+1=f(xt,ut)\text{s.t.} \quad x_{t+1} = f(x_t,u_t)

SQP的优化问题：

min⁡xf(x)\min_x f(x)

s.t.c(x)≤0\text{s.t.} \quad c(x) \leq 0

h(x)=0h(x) = 0

  1. 具体算法上实车的建议(个人想法)：

建议：

  • 如果是轨迹优化问题且需要实时性：选择iLQR
  • 如果需要精确解且有复杂约束：选择SQP
  • 如果是实时MPC应用：可以考虑iLQR变体

实践中要注意的：

  • iLQR的速度优势主要来自问题结构的利用
  • 精度牺牲通常在实际应用中是可接受的
  • 可以通过增加迭代次数来提高iLQR精度
  • 在某些场景下可以混合使用两种方法
Powered by 抛瓦 RSS