Last-iterate Convergence of ADMM on Multi-affine Quadratic Equality Constrained Problem
Yutong Chao, Michal Ciebielski, Jalal Etesami, Majid Khadiv · 2026
Read Last-iterate Convergence of ADMM on Multi-affine Quadratic Equality Constrained Problem by Yutong Chao, Michal Ciebielski, Jalal Etesami, Majid Khadiv (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-11919.txt.
Introduction
Chao and co-authors prove that ADMM converges on a class of non-convex problems with multi-affine quadratic equality limits. Such problems show up in robot locomotion planning and neural network training. Though non-convex overall, they turn convex when all but one variable is held fixed. Under mild assumptions, the authors prove last-iterate convergence. When the non-convexity stays within set bounds, they further show a linear convergence rate. Robot locomotion examples back the theory.
Catalog record
| CREATOR | Yutong Chao, Michal Ciebielski, Jalal Etesami, Majid Khadiv |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 99849 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.11919
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Last-iterate Convergence of ADMM on Multi-affine Quadratic Equality Constrained Problem Yutong Chao, Michal Ciebielski, Jalal Etesami, Majid Khadiv Abstract 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. 1 Introduction Non-convex optimization serves as a fundamental concept in modern machine learning, such as reinforcement learning 71 ; 66 and large language models 43 ; 32 . The non-convexity in these applications may arise from the objective function, the constraint set, or both. Finding a solution to a non-convex problem is, in general, NP-hard 33 . As a step to manage this complexity, a common practice is to study problems with additional structural assumptions under which particular solvers, such as gradient-based methods, are guaranteed to converge to an optimizer. Subsequently, various relaxations of the objective and/or constraints have been proposed to transform the original problem into a more tractable problem. For instance, the objective function has been studied under assumptions such as weak strong convexity 44 , restricted secant inequality 79 , error bound 11 , and quadratic growth 52 . On the other hand, optimization problems with various types of non-linear constraints have been investigated, such as quadratically constrained quadratic programs (QCQP) 3 ; 19 , geometric programming (GP) 9 ; 70 , mixed-integer nonlinear programming (MINLP) 35 ; 54 , and equilibrium constraints problem 75 ; 58 . Recently, there has been growing interest in analyzing non-convex optimization problems with specific block structures, driven by their broad range of applications. Although such problems are generally non-convex, they often exhibit convexity or related properties when all but one block of variables is fixed. Various structural properties of these problems have been studied, including multi-convexity in minimization settings 72 ; 56 ; 46 , PL-strongly concave 25 , and PL-PL 15 ; 12 in min-max formulations. Motivated by two well-known applications in robotics, in this work, we study multi-affine equality-constrained optimization problems (see Problem in equation 1 ). Figure 1: Examples of locomotion and manipulation settings, (left) Solo 24 and (right) Trifinger 69 In particular, locomotion and manipulation problems in robotics (Figure 1 ) involve intermittent contact interactions with the world. Due to the hybrid nature of these interactions, generating dynamically-consistent trajectories for such systems leads to a set of non-convex problems, which remains an open challenge. In general, the problem of planning through contact is handled in two ways; contact-implicit and contact-explicit. The first approach directly incorporates the complementarity constraints arising from the contacts, either by relaxing them within the problem formulation 61 or at the solver level 51 . While this approach has recently shown considerable promise in practice 30 ; 2 ; 34 , providing convergence guarantees remains an open problem due to the presence of multiple sources of non-convexity. The second approach handles contact in the trajectory optimization problem by casting it as a mixed-integer optimization 16 ; 63 . In this approach, the hybrid nature of interaction is explicitly taken into account with integer variables, and thus, a combinatorial search is required to decide over the integer decision variables, while the continuous trajectory optimization problem ensures the kinematic and dynamic feasibility of the problem. This approach has also shown great success in recent years in both locomotion 50 ; 60 ; 1 and contact-rich manipulation tasks 27 ; 64 ; 80 . The optimization problem in the contact-explicit setting exhibits additional interesting structure. In particular, the dynamics can be decomposed into underactuated and actuated components 68 . This implies that, to generate a feasible force trajectory, the kinematics can be abstracted away. Assuming the robot can produce any desired contact force, it is sufficient to consider only the Newton-Euler dynamics to generate dynamically consistent trajectories for the robot’s center of mass (CoM) in locomotion and for the object’s CoM in manipulation. Interestingly, in this setting, the non-convexity in the dynamics has a special form, namely it is multi-affine 26 . This renders the trajectory optimization problem a multi-affine equality-constrained optimization problem. These types of problems also appear in other applications such as matrix factorization 45 ; 13 , graph theory, and neural network training process 62 ; 77 . Recent work has exploited this structure to solve the problem using methods such as block coordinate descent 55 and the alternating direction method of multipliers (ADMM) 48 . In constrained optimization problems with linearly separable constraints, ADMM is an efficient and reliable algorithm 39 ; 17 ; 74 . Notably, its variants are driving the success of many machine learning applications involving optimization problems with linear constraints and convex objectives 57 ; 49 ; 29 as well as those with non-convex objectives 8 ; 31 ; 67 ; 37 ; 76 . However, not all of these works provide convergence guarantees, and those that do either rely on additional assumptions or establish weaker forms of convergence. For instance, 8 considered the problem \min f(x)+\phi(z) subject to Ax=z , where \phi is proper and lower semicontinuous (LSC), h is differentiable and L -smooth. They proved last-iterate convergence to a KKT point under the KL property (see Definition 2.5 ) and assuming access to a proximal solver, i.e., \arg\min_{z}\{\phi(z)+\langle y^{k},Ax^{k}-z\rangle+\frac{r}{2}\|Ax^{k}-z\|^{2}+\frac{1}{2}\|z-z^{k}\|^{2}\}. A similar assumption is made by 76 . However, this requirement is quite restrictive when g is nonconvex and the constraints are nonlinear. In fact, their guarantees no longer hold when the constraint set includes nonlinear relations, such as \{x_{1}x_{2}+x_{3}+z=0\} . The next table presents a comparison of existing ADMM approaches. Table 1: Comparison with previous work Ref. Blocks Objective Assumptions Constraints Convergence 8 =2 f(x)+\phi(z) f : smooth, \phi : LSC Linear Last iterate assuming \alpha -PL 67 \geq 2 f(x)\!+\!\sum_{i=1}^{n}I_{i}(x_{i})+\phi(z) f : smooth, \phi : smooth f+\phi: coercive Linear Avg. iterate 37 =2 f(x)+\phi(z) f : smooth, \phi : convex, nonsmooth Convex, bounded Best iterate 76 \geq 2 \sum_{i=1}^{n}f_{i}(x_{i})+{\color[rgb]{0,0,1}h}_{i}(x_{i}) f_{i} : smooth, bounded derivative, h_{i}: nonsmooth, h_{n}: convex Linear Avg. iterate Our Work \geq 2 f(x)+\sum_{i=1}^{n}I_{i}(x_{i})+\phi(z) f : strongly convex, smooth, \phi : strongly convex, smooth Multi-affine, unbounded Last iterate Naturally, it is important to understand the limitations of ADMM in settings with nonlinear constraints, such as multi-affine equality-constrained 67 ; 78 ; 4 . 18 studied general nonlinear equality-constrained nonconvex optimization but imposed additional structural assumptions to ensure regularity, such as full column rank of the constraint Jacobian. They also relied on backtracking strategies to solve each subproblem. Furthermore, they established convergence rates under the assumption that the objective satisfies the \alpha -PL property. 36 focused on proximal ADMM methods for general nonlinear dynamics constraints. However, they only provide the best-iterate convergence between two iterates and fail to provide convergence rate related to the stationary point.