用李群构造法解决带互补约束的二次规划问题
Complementarity by Construction: A Lie-Group Approach to Solving Quadratic Programs with Linear Complementarity Constraints
- 基于李群结构设计约束满足的优化方法
- 新求解器Marble在多个基准测试中表现优异
- 适合需要高精度互补约束求解的机器人任务
机器人任务常需同时处理连续动态与离散事件（如抓取和行走中的接触变化），这些场景可用线性互补二次规划（LCQP）建模。尽管表达能力强，但LCQP是非凸的，现有求解器有限且易失效。本文发现，在无穷小松弛下，互补约束构成李群结构，据此提出一种流形上优化方法：通过数值稳定的良好重收缩映射参数化约束，使约束自动满足。由此构建的开源求解器Marble（C++实现，支持Julia和Python接口）在基准测试中表现良好，能解决若干现有方法无法收敛的机器人问题。
原文摘要 · Abstract (English)
Many problems in robotics require reasoning over a mix of continuous dynamics and discrete events, such as making and breaking contact in manipulation and locomotion. These problems are locally well modeled by linear complementarity quadratic programs (LCQPs), an extension to QPs that introduce complementarity constraints. While very expressive, LCQPs are non-convex, and few solvers exist for computing good local solutions for use in planning pipelines. In this work, we observe that complementarity constraints form a Lie group under infinitesimal relaxation, and leverage this structure to perform on-manifold optimization. We introduce a retraction map that is numerically well behaved, and use it to parameterize the constraints so that they are satisfied by construction. The resulting solver avoids many of the classical issues with complementarity constraints. We provide an open-source solver, Marble, that is implemented in C++ with Julia and Python bindings. We demonstrate that Marble is competitive on a suite of benchmark problems, and solves a number of robotics problems where existing approaches fail to converge.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。