Last-iterate Convergence of ADMM on Multi-affine Quadratic Equality Constrained Problem

In this paper, we study a class of non-convex optimization problems known as multi-affine quadratic equality constrained problems, which appear in various applications--from generating feasible force trajectories in robotic locomotion and manipulation to training neural networks. Although these problems are generally non-convex, they exhibit convexity or related properties when all variables except one are fixed. Under mild assumptions, we prove that the alternating direction method of multipliers (ADMM) converges when applied to this class of problems. Furthermore, when the "degree" of non-convexity in the constraints remains within certain bounds, we show that ADMM achieves a linear convergence rate. We validate our theoretical results through practical examples in robotic locomotion.

Many problems in robotics and machine learning require solving optimization problems with nonlinear constraints. For example, a walking or jumping robot must choose contact forces and body motions that obey physical dynamics. These constraints often make the problem non-convex, so standard algorithms may be hard to analyze. This paper studies a structured class of such problems where the constraints are multi-affine and quadratic. We prove that ADMM, a widely used optimization method, converges for this class under mild assumptions. We further show that when the nonlinear part of the constraints is sufficiently small, ADMM converges at a fast linear rate. Experiments on robotic locomotion examples support the theory.