|
Last-iterate Convergence of ADMM on Multi-affine Quadratic Equality Constrained Problem |
Soundness: 3: good
Presentation: 4: excellent
Contribution: 3: good
Rating: 8: accept, good paper
Confidence: 3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked. |
The paper proves the convergence of a variant of the alternating direction method of multipliers (ADMM) for multi-affine quadratic equality constrained problems, which are non-convex. Assumptions are less restrictive than in prior work. Linear convergence rates are also proven. The ADMM scheme is evaluated on robotics locomotion problems.
The paper tackles an important and non-trivial problem: designing solvers with convergence guarantees for non-convex problems, with many applications. The paper is well-written throughout. Assumptions and results are clearly stated, discussed, and compared to other ones in the literature, which makes the contribution clear. Examples are instructive and show the necessity of assumptions. The ADMM scheme is tested on a non-trivial locomotion problem, and results validate the derived convergence rates.
The following limitations and suggestions are minor:
1) Application to locomotion: The proposed method can only handle the case with pre-defined contact sequences and timings. This limitation should be stated.
2) Section 5, baselines:
- Adding a sentence describing the baselines and their difference with the proposed ADMM scheme would strengthen the comparison.
- Computation times for solving the locomotion problem are not reported. It is unclear if the proposed method is faster and converges more robustly in practice than other tailored solvers for such problems.
3) Mathematical clarifications:
- On line 223, the dual variable $w$ has the wrong dimensions and should be in $\mathbb{R}^{n_c}$.
- In Definition 2.1, "such" => "such that". Also, "Moreover," should be replaced with an "and" for the definition to make sense. Also, it could be worth noting that quadratics ($C_i=I$) do not satisfy this assumption, so this assumption implies that the diagonal elements $(C_i)_{jj}$ are zero.
- Typo: in (18), instances of $\nabla A$ should be $\nabla_i A$.
- The first step of the proof of Theorem 3.2 states that second order differentiability of the Lagrangian at $(x^\star,z^\star,w^\star)$ implies strict feasibility in a neighborhood ("indicator functions are all zero for the points in that neighborhood"), which is correct. This assumption implies that $(x^\star,z^\star,w^\star)$ is in the strict interior of the set $\cap_i X_i$. This assumption can be strong and it would be worth discussing how to potentially relax it, e.g., with a refined assumption and analysis accounting for active constraints on the boundary of the $X_i$'s.
- On line 1199, $\alpha=1/2$ should be $\alpha=2$.
Please clarify Definition 2.1 and the assumption of second order differentiability of the Lagrangian in Theorem 3.2 (see my previous comment). |
Fully human-written |
|
Last-iterate Convergence of ADMM on Multi-affine Quadratic Equality Constrained Problem |
Soundness: 3: good
Presentation: 2: fair
Contribution: 2: fair
Rating: 4: marginally below the acceptance threshold
Confidence: 3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked. |
This paper studies the convergence of ADMM in multi-affine quadratic equality-constrained problems. Under certain assumptions, the main results include:
* A sublinear convergence rate of ADMM with general multi-affine quadratic constraints
* A linear convergence rate of ADMM when the constraints are close to linear constraints
Both results are stated in terms of last-iterate convergence.
Moreover, future results include experiments to explore the effect of multi-affine quadratic constraints on the convergence rate, comparisons with other optimization methods, and applications to locomotion problems in robotics.
* The results extend previous linear constraints to affine quadratic constraints, which is more practical than the previous setting where linear constraints are mainly discussed.
* The convergence results are in terms of last-iterate convergence, which is more interesting from a theoretical perspective.
* The discussion of the results in the locomotion problem in robotics is interesting and shows the practical use of the theoretical results.
My main concern lies in the use of **Assumption 2.3**, which requires that the functions $f(x)$ and $\phi(x)$ are both strongly convex, so the objective function discussed in the current work is a sum of two strongly convex functions and several indicator functions of convex and closed sets. This greatly constrains the degree of non-convexity of the objective function considered in this paper.
Moreover, the authors do not discuss how these convexity assumptions on $f(x)$ compare with those in previous works. For example, in the table at the top of page 3, this seems none of the related works need any convex assumptions on $f(x)$; does this mean that the other works do not require the same convexity assumptions as those used in the current paper?
Other problem:
* In line 97 and the table at the top of page 3, the "KL" should be "PL" as used in Definition 2.5 ?
* In the right part of Figure 5, the labels for each curve are missing.
* Whether the related works, especially the four related works presented in the table at the top of page 3, also require the strong convexity condition for $f(x)$?
* If they do not, what is the main difficulty of removing this assumption from the current work?
* As the authors stated in the abstract of the current paper, "Although these problems are generally non-convex, they exhibit convexity or related properties when all variables except one are fixed," could the authors provide further discussion on this point? For example, could you provide important real-world examples where such objective functions are used to model problems? |
Fully human-written |
|
Last-iterate Convergence of ADMM on Multi-affine Quadratic Equality Constrained Problem |
Soundness: 3: good
Presentation: 3: good
Contribution: 2: fair
Rating: 4: marginally below the acceptance threshold
Confidence: 4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. |
This paper analyses the convergence properties of the Alternating Direction Method of Multipliers (ADMM) when applied to multi-affine, quadratic, equality-constrained optimisation problems. Under assumptions including $L$-smooth and strongly convex objectives, as well as full-rank constraint matrices, the authors prove that ADMM converges to a stationary point at a rate of at least sublinear. When the nonlinearity in the constraints is sufficiently small relative to the linear components, they also prove linear convergence. These theoretical findings are applied to robotic locomotion trajectory optimisation, where centroidal dynamics lead to multi-affine constraints, and are experimentally validated.
- This paper clearly demonstrates the real-world applicability of centroidal dynamics in locomotion by highlighting how they give rise to multi-affine quadratic constraints.
- It provides comprehensive theoretical results and several meaningful extensions.
- The analysis makes novel contributions by establishing explicit conditions for linear convergence when nonlinear constraint coefficients are sufficiently small in relation to linear components.
The author needs to make a major revision to improve the quality. Some detailed comments are provided below.
- Although multi-affine quadratic constraints are generally challenging, the problem becomes affine when all but one variable block is fixed. ADMM can naturally exploit this structure, which appears to have a negligible effect on the analysis framework of classic ADMM. The convergence rate (Theorem 3.1) also basically follow the convergence analysis in [1] and the KL framework in [2]. (Here the PL property is a special case of KL).
- Several extensions of the main results appear incomplete:
- Although the main motivation is robotic applications, Corollaries 4.1 and 4.2 only guarantee convergence when certain assumptions about the functions are met. This means that, although problem (6) can be reformulated as (1), theoretical convergence is not fully assured, thereby limiting its practical application.
- The analysis of the approximated-ADMM (Algorithm 2) does not explicitly address the effect of approximation errors on convergence. Furthermore, in Theorem D.3, conditions P2 and P3 are assumed rather than proven, which weakens the theoretical support.
- Although each ADMM subproblem is strongly convex and smooth, a sufficiently large penlty parameter $\rho$ causes the term $\frac{\rho}{2}\|A(x)+Qz\|^2$ in the augmented Lagrange function to dominate. This increases the condition number of the Hessian of the subproblem, which can slow convergence or require high-precision solvers.
- The experimental evaluation lacks rigour and comprehensive baseline comparisons. Comparisons with existing methods (PADMM and IPDS-ADMM are designed for non-convex objectives) are limited to a few scenarios and omit standard benchmarks. Furthermore, since Algorithm 1 is only a classical ADMM, it should also be compared with ADMM methods designed for convex objectives [3,4].
- The paper provides incomplete practical guidance on parameter selection. While a 'sufficiently large $\rho$' is theoretically required, the paper provides no sensitivity analysis or practical tuning strategies, which hinders reproducibility.
- Some of the expressions are inaccurate. For example, on page 3, the description of [5] incorrectly states that $\phi$ is not smooth, and the objective in [6] does not match the original reference.
- It seems that the author is missing some key references, including [7,8], which also address nonconvex optimization with nonlinear equality constraints using ADMM. Since the constraints studied here are a special case of nonlinear equalities, it would be good to contextualize the work the authors have done with these important papers.
- The writing suffers from typographical and organizational issues:
- The cross-ref to expressions are inconsistent (for example, 'Equation (13)' on page 24, line 1244 vs. 'equation 34' on line 1260).
- The table on page 3 lacks a caption.
- On page 3, line 155, 'Assumption' should be pluralized as 'Assumptions'.
# References
[1] Gao, W., Goldfarb, D., & Curtis, F. E. (2020). ADMM for multiaffine constrained optimization. Optimization Methods and Software, 35(2), 257-303.\
[2] Guo, K., Han, D. R., & Wu, T. T. (2017). Convergence of alternating direction method for minimizing sum of two nonconvex functions with linear constraints. International Journal of Computer Mathematics, 94(8), 1653-1669.\
[3] Cai, X., Han, D., & Yuan, X. (2017). On the convergence of the direct extension of ADMM for three-block separable convex minimization models with one strongly convex function. Computational Optimization and Applications, 66(1), 39-73.\
[4] Tang, T., & Toh, K. C. (2024). Self-adaptive ADMM for semi-strongly convex problems. Mathematical Programming Computation, 16(1), 113-150.\
[5] Li, J., Ma, S., & Srivastava, T. (2024). A Riemannian alternating direction method of multipliers. Mathematics of Operations Research.\
[6] Yuan, G. (2025). ADMM for nonconvex optimization under minimal continuity assumption. ICLR.\
[7] El Bourkhissi, L., & Necoara, I. (2025). Convergence rates for an inexact linearized ADMM for nonsmooth nonconvex optimization with nonlinear equality constraints. Computational Optimization and Applications, 1-39.\
[8] Li, B., & Yuan, Y. X. (2025). Convergent Proximal Multiblock ADMM for Nonconvex Dynamics-Constrained Optimization. arXiv preprint arXiv:2506.17405.
Please see **Weakness**. |
Fully human-written |
|
Last-iterate Convergence of ADMM on Multi-affine Quadratic Equality Constrained Problem |
Soundness: 4: excellent
Presentation: 4: excellent
Contribution: 3: good
Rating: 6: marginally above the acceptance threshold
Confidence: 3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked. |
This paper shows that the classical ADMM procedure for optimization under equality constraints does converge to a local minimum when the constraints are multi-affine quadratic and the objective function satisfies some additional properties (including strong convexity plus some indicator functions). It further establishes a linear convergence rate when some additional assumptions are satisfied and shows applications to robotic locomotion.
The results obtained appear to be new: in particular, the convergence of ADMM under certain assumptions was proven in Guo et al. (2020) but without a convergence rate analysis. The simulation experiments with robots are limited but rather convincing.
I am not an optimization specialist, but the paper is interesting and well written, and a cursory look at the proofs indicates that they are reasonable (e.g., they go further than noting that the sequences are decreasing and bounded below, or that the difference between iterates converges to zero, which would not be sufficient). Given the wide use of ADMM in the community I think the paper is of interest to the ICLR community
Although the robotic experiments validate the assumptions made in the paper, it would be nice to discuss these further, for example Assumption 2.3 on the objective function, which seems rather restrictive, as well as their importance in practice.
See weaknesses above. |
Fully human-written |