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

Yutong Chao, Michal Ciebielski, Jalal Etesami, Majid Khadiv
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:12916-12947, 2026.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-chao26a, title = {Last-iterate Convergence of {ADMM} on Multi-affine Quadratic Equality Constrained Problem}, author = {Chao, Yutong and Ciebielski, Michal and Etesami, Jalal and Khadiv, Majid}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {12916--12947}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/chao26a/chao26a.pdf}, url = {https://proceedings.mlr.press/v306/chao26a.html}, 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.} }
Endnote
%0 Conference Paper %T Last-iterate Convergence of ADMM on Multi-affine Quadratic Equality Constrained Problem %A Yutong Chao %A Michal Ciebielski %A Jalal Etesami %A Majid Khadiv %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-chao26a %I PMLR %P 12916--12947 %U https://proceedings.mlr.press/v306/chao26a.html %V 306 %X 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.
APA
Chao, Y., Ciebielski, M., Etesami, J. & Khadiv, M.. (2026). Last-iterate Convergence of ADMM on Multi-affine Quadratic Equality Constrained Problem. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:12916-12947 Available from https://proceedings.mlr.press/v306/chao26a.html.

Related Material