On the Practical Implementation of a Sequential Quadratic Programming Algorithm for Nonconvex Sum-of-squares Problems

本文提出了一种用于求解非凸平方和问题（SOS）的过滤线搜索算法，该算法通过求解二次子问题序列，在数值基准测试中显著减少了迭代次数并大幅降低了计算时间，从而弥补了现有非凸 SOS 程序缺乏高效解法的空白。

要点

这是一篇关于如何更高效地解决复杂数学难题的论文。为了让你轻松理解，我们可以把这篇论文的内容想象成**“在充满障碍的迷宫中寻找最佳路线”**的故事。

1. 背景：什么是“平方和”优化？

想象你是一位建筑师，你的任务是设计一座房子（数学模型），确保它非常坚固，永远不会倒塌（数学上称为“非负性”）。

• 传统方法（凸优化）： 如果地形是平坦的（凸问题），你只需要画一条直线就能找到最稳的基石。这很容易，现在的电脑算得飞快。
• 现实挑战（非凸问题）： 但现实世界充满了坑坑洼洼、悬崖和死胡同（非凸问题）。这时候，简单的直线行不通了。你需要在复杂的迷宫里摸索，既要避开悬崖（满足约束），又要找到最稳的基石（最小化成本）。

在控制工程（比如让无人机保持平衡、让机器人手臂灵活运动）中，很多数学问题都属于这种“复杂迷宫”。以前，解决这类问题就像盲人摸象，效率很低，甚至经常卡住。

2. 旧方法的困境：坐标下降法

以前，工程师们常用一种叫“坐标下降法”（Coordinate Descent）的策略。

• 比喻： 想象你在迷宫里，每次只能只动一根手指（比如只调整左边的墙，右边的墙不动），看看能不能走得更稳。如果稳了，再动下一根手指。
• 缺点： 这种方法太笨拙了！
  1. 你需要很多次尝试（迭代次数多）。
  2. 如果你一开始站的位置不对（初始猜测不好），你可能直接掉进坑里，根本动不了。
  3. 你需要自己把大迷宫拆成很多小迷宫，非常麻烦。

3. 新方案：带“过滤器”的二次规划

这篇论文提出了一种更聪明的算法，叫**“序列二次规划（SQP）+ 过滤器线搜索”。我们可以把它比作一位经验丰富的登山向导**。

A. 核心策略：看大局，走捷径（二次规划）

• 旧方法是“走一步看一步”，只盯着眼前的一小块地。
• 新方法是向导手里有一张地形图（二次模型）。他不仅能看到脚下的路，还能预测几步之后的地形。他直接计算出一条最佳冲刺路线，而不是像盲人一样乱撞。
• 效果： 这意味着他走的每一步都更有意义，需要的步数（迭代次数）大大减少。

B. 关键创新：过滤器（The Filter）

这是论文最精彩的部分。在爬山时，你可能会遇到两种情况：

1. 高度降低了（成本变好了，但可能离悬崖更近了）。
2. 离悬崖远了（安全性提高了，但高度可能暂时没变好）。

• 旧方法（惩罚函数）： 像是一个严厉的教官，规定“如果你离悬崖太近，我就给你加罚跑”。但教官很难拿捏这个“罚跑”的尺度，罚多了你跑不动，罚少了你还是会掉下去。
• 新方法（过滤器）： 像是一个智能的“双目标”过滤器。它不强迫你立刻完美，而是建立一个“黑名单”。
  • 如果你现在的状态（高度 + 安全距离）比黑名单里的任何一次尝试都要好（要么更高，要么更安全，或者两者兼顾），它就放行。
  • 如果不行，它就拒绝，让你换个方向。
  • 好处： 它不需要那个难搞的“罚跑尺度”，非常灵活，能接受暂时的“不完美”以换取长远的进步。

C. 安全网：可行性恢复（Feasibility Restoration）

如果向导发现前面路完全断了（数学上叫“不可行”），他不会直接放弃。

• 他会启动**“安全网模式”**：暂时忘掉“爬得更高”的目标，全力先把你从悬崖边拉回来，确保你站在安全的地方。一旦安全了，再重新规划路线。
• 这解决了旧方法一旦初始位置不好就彻底崩溃的问题。

4. 实际效果：快如闪电

论文作者用真实的控制工程问题（比如 F/A-18 战斗机的飞行控制、多关节机器人手臂）做了测试：

• 速度： 新方法比旧方法快得多。在某些复杂问题上，旧方法要跑几千次才能停下来，新方法只要几十次。
• 鲁棒性： 即使一开始给向导一个错误的起点（比如让他站在悬崖边），新方法也能把他拉回来并找到路；而旧方法直接“死机”了。
• 开源： 作者把这套算法做成了免费的软件（叫 CaΣoS），任何人都可以用。

总结

这篇论文就像是在说：

“以前我们在解决复杂的控制难题时，像是在泥潭里用勺子挖路，又慢又累。现在，我们发明了一辆带导航和自动避障系统的越野车。它不仅能预测路况（二次规划），还能灵活地平衡‘速度’和‘安全’（过滤器），甚至在陷车时能自动脱困（可行性恢复）。这让以前算不动的复杂工程问题，现在变得既快又稳。”

这对于让无人机飞得更稳、机器人动作更灵活、自动驾驶更安全，都有着巨大的推动作用。

技术摘要

这篇论文提出了一种针对非凸平方和（Sum-of-Squares, SOS）优化问题的实用算法，旨在解决控制工程等领域中因非凸性导致传统半定规划（SDP）无法直接求解的难题。

以下是该论文的详细技术总结：

1. 研究背景与问题陈述 (Problem)

• 核心问题：SOS 优化是验证多项式非负性的有效框架。对于凸 SOS 问题，可以转化为半定规划（SDP）求解。然而，许多实际工程问题（如非线性系统的稳定性分析、不变性验证、控制律综合）在局部区域内表现为非凸 SOS 问题，无法直接使用凸 SDP 求解器。
• 现有方法的局限：
  • 目前处理非凸 SOS 的主流方法是迭代方案，如坐标下降法（Coordinate Descent, CD）。该方法将非凸问题分解为一系列凸子问题。
  • 缺点：缺乏收敛性保证（除非问题是拟凸的）；需要可行初始猜测；用户需手动将问题分解为子问题；对于非凸性较强的问题，可能需要大量迭代且性能不可预测。
  • 现有的非线性 SDP 求解器（如 PENLAB）开发停滞，不再适用。
• 目标：开发一种具有全局收敛策略、能高效处理约束违反、且无需可行初始猜测的实用算法。

2. 方法论 (Methodology)

作者提出了一种基于**序列二次规划（Sequential Quadratic Programming, SQP）结合滤波器线搜索（Filter Line Search）**的算法。

• 序列二次 SOS 规划：
  • 不同于之前的序列线性 SOS 方法，本文采用二次子问题。
  • 在每次迭代 $k$，基于当前候选解 $\xi_k$，构建并求解一个局部凸 SOS 二次子问题，以获得搜索方向 $\omega_k$。
  • 利用拟牛顿法（Quasi-Newton）框架，通过更新 Hessian 近似矩阵来加速局部收敛。
• 滤波器线搜索（Filter Line Search）：
  • 作为全局化策略，用于平衡目标函数值（成本）和约束违反度。
  • 优势：相比传统的惩罚函数法（Merit Functions），滤波器方法不需要调节惩罚参数，避免了数值不稳定性和额外的计算开销。
  • 机制：维护一个由“主导对”（目标值，约束违反度）组成的滤波器。如果新点能改善目标或减少约束违反（且不被滤波器阻挡），则被接受。
• 可行性恢复阶段（Feasibility Restoration Phase）：
  • 当步长过小或检测到不可行时，算法进入恢复阶段。
  • 该阶段旨在最小化约束违反度，使迭代点重新回到滤波器的可接受区域。
  • 引入了正则化项，防止恢复过程偏离当前解太远。
• 约束违反度评估（Constraint Violation Estimation）：
  • 针对 SOS 锥没有解析投影算子的问题，论文比较了三种方法：SOS 投影（SDP）、符号距离（Signed Distance）和采样法。
  • 选择：采用符号距离法，因为它在计算效率和准确性之间取得了最佳平衡，且无需在每次检查时求解完整的 SDP。
• 二阶修正（Second-Order Correction, SOC）：
  • 用于缓解 Maratos 效应（即大步长被拒绝导致的收敛缓慢），通过调整搜索方向进一步减少约束违反。

3. 主要贡献 (Key Contributions)

1. 收敛性分析：提供了序列二次 SOS 算法的局部收敛性证明。在正则性和连续性假设下，证明了算法具有线性、超线性甚至二次收敛速率。
2. 算法设计：针对 SOS 问题的特性设计了关键组件，包括高效的约束违反度检查（符号距离法）和专门的可行性恢复阶段。
3. 开源实现：将算法集成到开源软件 CaΣoS 中，提供了完整的实现和基准测试数据。
4. 实证验证：通过多个源自控制工程的基准测试，证明了该方法在迭代次数和计算时间上显著优于现有的坐标下降法。

4. 实验结果 (Results)

论文在多个非线性系统分析和控制设计问题上进行了基准测试，对比了提出的序列二次 SOS（SQ）方法与坐标下降法（CD）：

• F/A-18 飞行控制律区域吸引域（ROA）估计：
  • SQ 方法仅需 19 次迭代收敛，而 CD 在 100 次迭代内未收敛。
  • SQ 的总计算时间（52.5s）远少于 CD（277.3s）。
• N 连杆机器人臂 ROA 估计：
  • 随着状态维度 $n$ 增加，SQ 方法的优势更加明显。
  • 在“良好初始猜测”下，SQ 平均减少 60% 的迭代次数和 54% 的计算时间。
  • 在**“不良初始猜测”**（不可行初始点）下，CD 无法启动（需要可行初始点），而 SQ 结合可行性恢复阶段成功找到了可行解或最优解。
• 非线性系统控制综合：
  • 对于非仿射（non-control-affine）动力学系统，CD 难以直接处理，而 SQ 方法能直接求解。
  • 在航天器姿态控制合成中，SQ 在 1 分钟内收敛，而 CD 在 6 次迭代后失败。
• 可达性分析与 CBF/CLF 综合：
  • 在大规模问题（如 1756 个约束，9404 个决策变量）中，SQ 方法展现了良好的可扩展性，尽管线搜索中的约束检查占据了主要计算时间。

5. 意义与结论 (Significance)

• 突破非凸限制：该算法为非凸 SOS 问题提供了一种直接、鲁棒的求解途径，无需依赖可行初始猜测，克服了坐标下降法的局限性。
• 工程应用价值：显著降低了非线性控制系统（如稳定性分析、鲁棒控制、模型预测控制终端集设计）的计算成本，使得基于 SOS 的复杂系统分析更具实用性。
• 理论结合实践：不仅提供了理论上的局部收敛保证，还通过开源代码和详细基准测试展示了其在实际工程问题中的有效性。
• 未来方向：虽然全局收敛性分析留待未来工作，但该方法已为基于 SOS 的非线性系统分析与控制设计迈出了迈向更实用工具的重要一步。

总结：这篇论文通过引入序列二次规划框架和滤波器线搜索策略，成功解决了非凸 SOS 优化中的计算效率和鲁棒性问题，为控制工程领域提供了一种强有力的新工具。