OSQP求解器中的非负约束问题分析与解决方案

问题背景

在使用OSQP求解器解决二次规划问题时，开发者经常会遇到一个常见但令人困惑的现象：尽管在问题设置中明确指定了变量的非负约束，但最终求解结果中仍然出现了负值。这种情况尤其在使用C++接口结合Eigen库时更为明显。

技术原理分析

OSQP(Operator Splitting Quadratic Program)是一种基于算子分裂方法的二次规划求解器。它通过ADMM(交替方向乘子法)算法来求解形如以下形式的优化问题：

最小化 (1/2)xᵀPx + qᵀx
约束条件 l ≤ Ax ≤ u

当我们需要对变量施加非负约束时，通常的做法是通过设置A矩阵为单位矩阵，并指定l=0、u=+∞来实现x≥0的约束。

负值出现的原因

1. 求解精度限制：OSQP作为迭代求解器，只能保证解在设定的容差范围内满足约束条件。当解向量的范数较大时，相对误差可能导致某些分量出现负值。

2. 收敛标准：OSQP使用相对和绝对容差作为收敛标准。当‖r‖ ≤ ε_abs + ε_rel * max(‖Ax‖,‖z‖)时即认为收敛，其中r是残差。这意味着对于大范数解，允许的约束违反量也较大。

3. 数值稳定性：ADMM算法在求解过程中需要平衡原始可行性和对偶可行性，这可能导致某些约束不能严格满足。

解决方案比较

1. 调整容差参数：

   • 减小ε_abs和ε_rel可以降低约束违反量
   • 但会增加计算时间和可能无法收敛的风险

2. 启用抛光(Polish)功能：

   • 尝试在收敛后寻找更高精度的解
   • 但并非总能成功，如案例中所示

3. 手动后处理：

   • 对负值进行截断(设为0)
   • 简单有效，但可能轻微影响其他约束的满足程度

4. 问题重构：

   • 对变量进行缩放，使解向量范数接近1
   • 可以提高数值稳定性，但需要额外处理

工程实践建议

1. 对于严格需要非负解的应用，建议组合使用以下方法：

   • 设置适度的容差(如ε_abs=1e-6, ε_rel=1e-6)
   • 启用抛光功能
   • 对结果进行后处理截断

2. 监控求解器的状态输出，特别是：

   • 原始残差(pri res)
   • 对偶残差(dua res)
   • 解向量的范数

3. 当问题规模较大时，考虑使用预处理或变量缩放来改善数值特性。

与其他求解器的对比

值得注意的是，不同求解器处理约束的方式存在差异。例如MATLAB的quadprog可能采用内点法，其数值特性与基于ADMM的OSQP不同。这解释了为什么同一问题在不同求解器中可能表现出不同的约束满足程度。

结论

OSQP求解器中出现负值是一个与算法特性和数值计算相关的正常现象。通过理解其工作原理并合理配置参数，开发者可以在保证求解效率的同时，有效控制约束违反的程度。对于严格要求非负解的应用，适当后处理是可靠且实用的解决方案。