BC-ADMM: A parallel decoupled non-convex constrained optimizer for robot applications

Abstract

Non-convex constrained optimizations are ubiquitous in robotic applications such as multi-agent navigation, UAV trajectory optimization, and soft robot simulation. As a common feature in these problems, the associated non-convex constraints, including collision constraints, inversion-free constraints, and strain limits, are also non-smooth with ill-defined gradients. It is well-known that such constraints are notoriously difficult to handle, for which off-the-shelf optimizers can fail catastrophically. Instead, prior works tend to design problem-specific optimizers that trade performance for robustness. To efficiently solve this problem class in a unified manner, we propose a variant of alternating direction method of multiplier (ADMM), called BC-ADMM. Over the past decade, ADMM has achieved great success in efficiently solving many large-scale (constrained) optimization problems by decoupling them into subproblems that can be solved in parallel. However, prior ADMM algorithms lack a convergence guarantee when handling a large number of non-convex constraints with loopy constraint graphs. Instead, our BC-ADMM relaxes each non-convex constraint into a bi-convex function, further breaking the constraint into two subproblems. We show that such relaxation leads to a variant of ADMM with convergence speed guarantees under appropriate parameter choices. We further provide a practical algorithm under much milder assumptions on the parameter choices, with convergence guarantees without a speed bound. Through numerical experiments in a row of four robotic applications, we show that BC-ADMM has faster convergence than conventional gradient descent and Newton’s method in terms of wall clock time.