{"id":"26b86632-b2fa-4f98-8612-927989017733","arxiv_id":"2505.21071","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":4,"one_line_summary":"A convex dual formulation of hierarchical least-squares programming with equality constraints, plus an ADMM solver that eliminates primal-dual variables from the matrix factorization.","lead":"This paper develops a dual, convex formulation for hierarchical least-squares problems with equality constraints and an ADMM solver for it. If correct, the method makes prioritized optimization differentiable and distributable, though slower than existing primal solvers.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1 does not justify dropping the θ terms: the convex QCLSP may be a relaxation, and the paper's own rank-deficient test (Fig. 2, §7) shows the dual solver reporting a lower level-5 objective (106.7) than the primal HLSP (110.5), which the claimed equivalence would forbid.","rationale":"The reader identified the weakest assumption as the unproved equivalence between the simplified convex QCLSP and the original hierarchy after dropping the θ terms; my analysis agrees and strengthens it. The paper's own rank-deficient experiment in §7 shows a discrepancy between the dual solver and the primal solver at level 5 (106.7 vs 110.5), which is exactly what would happen if the simplified problem is a relaxation rather than an equivalent reformulation. The proof of Theorem 1 is also internally incomplete: it relies on choosing θ_{l,k} to force equality in (16), but then the implemented convex program fixes θ = 0 and never enforces that the inequality is active. Since the θ variables are nonnegative and appear only in this constraint, the feasible sets of the full and simplified problems coincide in the variables (x, v, λ); however, the proof never shows that the simplified inequality, combined with the dual stationarity constraints (15), forces the lexicographic optimum rather than merely permitting a superset of x values. The recommended verdict remains CONDITIONAL: the paper should not be accepted until Theorem 1 is proved for the actual solved problem and the rank-deficient discrepancy in Fig. 2 is resolved, either by showing the primal solver is wrong or by confirming equivalence numerically. I do not recommend outright rejection based on the current evidence, because the discrepancy could in principle stem from a numerical bug in one of the solvers, but the burden is on the authors to settle it.","tokens_in":26345,"tokens_out":27030,"duration_ms":285475,"concrete_test":"Take the rank-deficient test instance of §7 (or a minimal 2-level example, e.g., A1 = [[1,0],[1,0]], b1 = [1,0]; A2 = [1,1], b2 = 0) and solve: (i) the primal lexicographic HLSP, (ii) the simplified convex QCLSP with θ = 0, and (iii) the full D-HLSP-E with θ ≥ 0 kept as variables. At the solutions, evaluate the left-hand sides of constraint (16) for each l < p. If for any level the simplified solution has a strictly negative left-hand side, or if (ii) or (iii) yields a strictly lower ||v_p||^2 than (i), the equivalence asserted in Theorem 1 fails and the central claim must be rejected.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that the simplified convex QCLSP of §4 is exactly equivalent to the equality-constrained lexicographic HLSP. This rests on Theorem 1, but the proof only shows that at a constructed primal solution one can choose θ_{l,k} ≥ 0 so that the strong-duality expression in (16) equals zero. The solver then drops all θ terms, leaving the inequality (v_l+\\hat b_l)^T(v_l+\\hat b_l) − \\hat b_l^T\\hat b_l + λ_l^T b_{∪l−1} ≤ 0. Since weak duality for the stacked subproblems is never established, this inequality can be strictly inactive (left-hand side negative). When it is negative, the level-l optimum is not enforced, so lower-priority slacks can be pushed below the true lexicographic optimum. This is consistent with §7, Fig. 2: in the rank-deficient sample, ||v_{E5}||^2 = 106.7 for D-HADM versus 110.5 for the primal solver NIPM. If the two problems were equivalent, the optimal lexicographic value at level 5 would be unique and identical. The paper's statement that the dual value is 'more accurate' is unsupported. Thus the proof gap is not merely cosmetic: the simplified dual is plausibly a relaxation, and the paper's own experiment is evidence of that.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper develops a dual formulation of lexicographic least-squares programming with equality constraints (D-HLSP-E), claiming that it is a single convex quadratically constrained least-squares program (QCLSP) equivalent to the sequential primal HLSP. The derivation in Sec. 4 builds a Lagrangian over all priority levels, extracts stationarity and duality-gap conditions, and then simplifies the problem by dropping the third-order terms involving the multipliers θ. Section 5 presents an ADMM solver (D-HADM) whose operator splitting eliminates the primal-dual variables from the matrix factorization, and App. B gives an interior-point counterpart (D-HIPM). The experiments in Sec. 7 compare D-HADM, D-HIPM, and the author's prior primal solver NIPM on randomized and rank-deficient problems, reporting that D-HADM is about one order of magnitude faster than D-HIPM while remaining 2–3 orders of magnitude slower than NIPM, with moderate accuracy. The paper also sketches a gradient computation in App. A as a basis for future differentiable and distributed applications.","tokens_in":26735,"tokens_out":51926,"duration_ms":460828,"significance":"If the claimed equivalence were rigorously established, the contribution would be significant: a differentiable, single-shot convex formulation of hierarchical least-squares would enable new modes of use (neural-network layers, distributed optimization), and the ADMM complexity reduction—factorizing only an n_x × n_x system instead of one including all primal-dual variables—is a genuine algorithmic idea. The paper is transparent about its limitations: Sec. 8 acknowledges the inability to handle inequality constraints and states that the dual solver is slower than primal solvers. The explicit gradient system in App. A and the honest comparison against the author's own solvers are also strengths. However, the equivalence claim is the load-bearing part of the paper, and it is not proven as written; the significance is therefore conditional on a substantial revision of the proof and on reconciling the experimental discrepancy reported in Sec. 7.","major_comments":[{"comment":"The proof of Theorem 1 does not establish the existence of nonnegative multipliers θ_{l,k} forcing the strong-duality equalities. Substituting the KKT identities into (12) shows that the claimed equality at level l requires Σ_{k<l} θ_{l,k} ||v*_{Ck}||² = λ^T_{l,C∪l−1} v*_{C∪l−1}, and the proof never verifies that the right-hand side is nonnegative or attainable with θ ≥ 0; the sentence that θ* is \"a free variable and has been chosen appropriately\" is exactly the assertion that needs proof. Moreover, g_p in (10) is the Lagrangian evaluated at a KKT point rather than an infimal dual function, so the weak-duality inequality invoked after (11) is not standard and is not proven. Since (12) is the basis for the duality constraint (16), Theorem 1 as stated does not support the claim that D-HLSP-E enforces zero duality gap at each priority level.","section":"Sec. 4, Theorem 1"},{"comment":"The transition from the full duality constraint (16), including the third-order term Σ_{k<l} θ_{l,k} v^T_{Ck} v_{Ck}, to the implemented QCLSP in which all θ terms are dropped is asserted rather than derived. The argument that θ_{l,k} is uncoupled and can be chosen freely only shows that θ acts as a slack variable in the full formulation; it does not show that the θ-free inequality (16) has the same feasible set or the same optimal value as the full constraint, nor that it remains tight enough to enforce the lexicographic optimum. The claim that θ = 0 favors strong duality in (12) is also not backed by an inequality analysis, since strong duality may require specific nonzero θ values or may be unattainable with θ ≥ 0. Consequently the abstract's assertion that the simplified D-HLSP-E is a convex QCLSP equivalent to the lexicographic HLSP is not established; at minimum, the authors need to prove that every minimizer of the θ-free problem attains the lexicographic optimal slack values at all higher-priority levels.","section":"Sec. 4, Eq. (16), convex simplification"},{"comment":"The rank-deficient experiment in Fig. 2 shows the dual solvers reporting ||v_{E5}||² = 106.7 while the primal solver NIPM reports 110.5. If the claimed equivalence held, the lexicographic optimal value at level 5 would be unique and both solvers should approach it; the text's statement that the dual values are \"more accurate\" has no stated ground truth, and it sits in tension both with Theorem 1 and with Table 1, which classifies D-HADM as \"less accurate.\" The authors should resolve this by reporting the level-by-level lexicographic subproblem values as a ground truth, or by attributing the gap to convergence tolerances and conditioning of the 1e-12-perturbed rank-deficient matrices with explicit evidence. As written, the experiment is consistent with the possibility that the simplified QCLSP is a relaxation, which would contradict the central claim.","section":"Sec. 7, Fig. 2"}],"minor_comments":[{"comment":"The subscript in \"with 2 = 1, . . . , p−1\" following Eq. (41) should read l = 1, and \"D-HADM aglorithm 1\" in Sec. 7 should read \"Algorithm 1.\"","section":"Sec. 5.3 and Sec. 7"},{"comment":"The experiments do not report the values of the stopping tolerance χ, the over-relaxation parameter α, the ρ-update parameters, or the stopping criteria used for D-HIPM; these should be specified for reproducibility, since the accuracy claims (\"moderate at levels of 1e-2\") depend on them.","section":"Sec. 7, experimental setup"},{"comment":"The differentiability claim is only supported by the linear system (55); differentiability of the solution map also requires conditions such as uniqueness of the KKT solution and a constraint qualification, which are not discussed. The QCLSP's inequality constraints can become active or inactive, and the authors should state the assumptions under which the gradient system is valid.","section":"App. A, gradient"},{"comment":"The application column of Table 1 lists D-HADM as \"less accurate,\" which is in tension with the Sec. 7 characterization of the dual solvers' values as \"more accurate\" in the rank-deficient sample; the relationship between these two statements should be clarified in the text.","section":"Table 1 and Sec. 7"}],"recommendation":"major_revision","confidential_remarks":"To the editor: Theorem 1 and the simplification step in Sec. 4 are the load-bearing parts of the paper and are not rigorous in the current form. I recommend major revision rather than rejection because the underlying idea appears salvageable: constraints (14) and (15) alone may inductively pin the higher-priority slack variables to their lexicographic optima, in which case the θ-free QCLSP could be equivalent to the hierarchy by a different argument than the one given. The ADMM elimination trick and the honest comparison with the author's own solvers are genuine contributions. The reported discrepancy in Fig. 2 must be resolved before acceptance; if the simplified formulation turns out to be a relaxation, the paper should be reframed as an approximate dual solver. The reliance on the author's own NIPM and D-HIPM as baselines is a citation-pattern concern, but the transparency about D-HADM being slower than NIPM mitigates it."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is worth reading for the algorithm and the honest experimental reporting, but the main theoretical claim does not hold up. The dual formulation of equality-constrained hierarchical least-squares, the variable-elimination trick that keeps the ADMM factorization size nx-by-nx, and the gradient formula in Appendix A are all genuine extensions of earlier dual HLP work in [30]. The experiments are internally consistent and show D-HADM roughly one order of magnitude faster than D-HIPM, with the admitted 2-3 order slowdown versus primal HLSP solvers stated plainly in the conclusion. That part is solid.\n\nThe soft spot is Theorem 1 and the step where the paper drops the θ terms. The proof constructs θ values to force zero duality gap level by level, but the simplified convex QCLSP used by the solver sets all θ to zero. The θ terms in (16) are nonnegative, so removing them makes the constraint weaker, not stronger. The result is a relaxation of the claimed exact equivalence. Nothing in the paper establishes weak duality for the stacked subproblems, and the rank-deficient test in Figure 2 is direct evidence: the dual solver reports ||v_E5||^2 = 106.7 against 110.5 for the primal solver. If the two problems were equivalent, the lexicographic optimum at level 5 would be identical. The paper calls the dual value 'more accurate,' but that is unsupported and is exactly what a relaxation would look like.\n\nThe equality-only restriction and the speed gap to primal solvers are honestly disclosed, so I do not fault the authors for those. The flaw is load-bearing: the abstract and contributions claim a convex program equivalent to the original hierarchical problem. The algorithmic machinery may still be useful as a differentiable heuristic, but that needs to be stated, with the equivalence claim removed or replaced by a proven bound.\n\nMy recommendation: send it to peer review, because the problem is real and the solver is a genuine engineering contribution, but the referee should require either a complete proof of the strong-duality equivalence or a reframing as a relaxation with numerical evidence. As written, the central theorem is not supported by the proof or the experiments.","headline":"The ADMM solver and gradient are real contributions, but the central equivalence claim is unproven and the paper's own experiments suggest the simplified dual is a relaxation, not an exact reformulation.","tokens_in":27177,"tokens_out":3045,"would_cite":false,"duration_ms":35150,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C20","90C46"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper establishes that equality-constrained hierarchical least-squares programs can be reformulated as a single convex, differentiable quadratically constrained least-squares program, and gives an ADMM solver that is about an order of…","keywords":["hierarchical least-squares programming","dual formulation","quadratically constrained least-squares","ADMM","equality constraints","differentiability","interior-point method"],"falsifier":"Compare the optimal level-wise slack norms produced by D-HLSP-E with those from a sequential primal HLSP solver on randomly generated equality-constrained hierarchies with linearly dependent constraint matrices; any instance where the two values diverge by more than solver tolerance would disprove the claimed equivalence.","tokens_in":26141,"feed_emoji":"📐","tokens_out":8367,"duration_ms":77792,"temperature":0.7,"pith_summary":"Hierarchical least-squares programming (HLSP) resolves stacked priority levels one after another, which is fast but makes the overall mapping non-differentiable. This paper tries to establish that, for equality constraints, the whole hierarchy can be re-expressed as one convex and differentiable quadratically constrained least-squares program (D-HLSP-E), so all priority levels are handled at once. That would matter because a differentiable HLSP can be embedded in neural networks and solved in distributed settings. The paper also develops an ADMM solver, D-HADM, and reports it is about one order of magnitude faster than the interior-point dual solver D-HIPM, though still slower than classical primal hierarchical solvers.","feed_headline":"Solve equality-constrained HLSPs as one convex program","feed_subtitle":"All priority levels handled at once as a differentiable QCLSP; new ADMM solver runs about 10x faster than the interior-point dual solver.","key_machinery":"The central object is D-HLSP-E: the dual formulation of an equality-constrained HLSP written as a convex quadratically constrained least-squares program. Its constraints are (i) the primal level equations $A_{E_l} x - b_{E_l} = v_{E_l}$, (ii) dual orthogonality conditions $A_{E_l}^T v_{E_l} + A_{E_{\\cup l-1}}^T \\lambda_{l,E_{\\cup l-1}} = 0$, and (iii) convex quadratic dual constraints $(v_{E_l}+\\hat b_{E_l})^T(v_{E_l}+\\hat b_{E_l}) \\le \\hat b_{E_l}^T\\hat b_{E_l} - \\lambda^T b$. The mechanism that makes the solver fast is ADMM operator splitting: split variables $z$ and $\\tilde\\lambda$ decouple the quadratic constraints and the primal-dual variables, so the substituted KKT system $K^\\rho_x x = -k^\\rho_x$ factorizes only in $x$, with each quadratic projection reduced to solving a cubic polynomial.","core_discovery":"The paper's central claim is that every equality-constrained HLSP is equivalent to a single convex QCLSP in which the primal variables, slack variables, and primal-dual variables (the dual variables of higher levels promoted to primal variables) appear together, and in which strong duality holds level by level. The paper supports this by deriving D-HLSP-E from the Lagrangian of a lexicographic hierarchy and proving (Theorem 1) that the duality gap can be closed at each level using free multipliers. It then shows that an ADMM implementation, D-HADM, can substitute the primal-dual variables out of the KKT system so that only a matrix on the primal variable $x$ needs factorization, and reports roughly an order-of-magnitude speedup over the interior-point dual solver D-HIPM on randomized hierarchies with up to ten priority levels and rank-deficient constraints.","pith_inferences":["Editorial inference: A natural testable extension is to verify whether the omitted $\\theta$ terms can change the optimal value in infeasible or rank-deficient cases; this would settle whether the convex QCLSP is exactly equivalent to the original hierarchy.","Editorial inference: The same operator-splitting idea could be applied to the dual of sparse hierarchical programs with $\\ell^0$/ $\\ell^1$ norms, where a linear dual already exists; the ADMM projection step would need a different scalar root-finding problem.","Editorial inference: The gradient linear system used in the appendix may be solvable by reusing factorizations from D-HADM, which would make neural-network integration computationally practical; the paper leaves that efficiency question open."],"forward_implications":["D-HLSP-E turns a lexicographic hierarchy into one convex QCLSP, so all priority levels are solved simultaneously rather than sequentially.","Because the dual program is differentiable, gradients with respect to problem data can be computed by solving a linear system, enabling HLSPs as layers in neural networks.","The ADMM formulation keeps matrix factorizations on the primal variable $x$ only, so the cost per iteration does not grow cubically with the number of primal-dual variables.","D-HADM is about one order of magnitude faster than the dual interior-point solver D-HIPM on the tested hierarchies with up to ten priority levels.","The dual formulation currently applies only to equality-constrained HLSPs; inequality constraints introduce non-convex complementary constraints that remain open."],"supporting_citations":[{"why":"Establishes the primal sequential nullspace-projection solver that D-HLSP-E is compared against.","marker":"[9]"},{"why":"Introduces the dual HLP whose quadratic extension this paper derives as D-HLSP-E.","marker":"[30]"},{"why":"Provides the primal interior-point HLSP solver used as a baseline in the evaluation.","marker":"[27]"},{"why":"Supplies the strong-duality and KKT conditions invoked in Theorem 1.","marker":"[4]"},{"why":"Supplies the ADMM framework and primal/dual residual definitions used by D-HADM.","marker":"[3]"},{"why":"Supplies the operator-splitting parameter updates, equilibration, and over-relaxation techniques adopted.","marker":"[32]"},{"why":"Provides the primal ADMM HLSP solver referenced for warm-start and embedded use.","marker":"[28]"}],"fun_headline_variants":["ADMM solves dual HLSP as one convex QCLSP","Dual HLSP becomes one differentiable convex program","10x faster ADMM for dual HLSP with equality constraints","One convex program for all HLSP priority levels"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof assumes the free $\\theta$ multipliers can always be chosen nonnegative to force strong-duality equalities level by level, and that dropping all $\\theta$ terms afterwards does not change the optimal value of the convex problem; the paper does not rigorously prove that last step.","fun_headline_variants_meta":{"raw":{"variants":["ADMM solves dual HLSP as one convex QCLSP","Dual HLSP becomes one differentiable convex program","10x faster ADMM for dual HLSP with equality constraints","One convex program for all HLSP priority levels"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000468,"raw_usage":{"total_tokens":2351,"prompt_tokens":984,"completion_tokens":1367,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":600,"completion_tokens_details":{"reasoning_tokens":1302}},"tokens_in":600,"tokens_out":1367,"duration_ms":9236,"temperature":1.0,"reasoning_tokens":1302,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T13:36:59.334204+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compare the optimal level-wise slack norms produced by D-HLSP-E with those from a sequential primal HLSP solver on randomly generated equality-constrained hierarchies with linearly dependent constraint matrices; any instance where the two values diverge by more than solver tolerance would disprove the claimed equivalence.","supporting_citations":[{"cited_title":"Hierarchical quadratic programming: Fast online humanoid-robot motion generation","cited_arxiv_id":null,"evidence_quote":"Establishes the primal sequential nullspace-projection solver that D-HLSP-E is compared against."},{"cited_title":"A weighted method for fast resolution of strictly hi- erarchical robot task specifications using exact penalty functions","cited_arxiv_id":null,"evidence_quote":"Introduces the dual HLP whose quadratic extension this paper derives as D-HLSP-E."},{"cited_title":"N ipm-hlsp: an efficient interior-point method for hierarchical least-squares programs","cited_arxiv_id":null,"evidence_quote":"Provides the primal interior-point HLSP solver used as a baseline in the evaluation."},{"cited_title":"Convex Optimization","cited_arxiv_id":null,"evidence_quote":"Supplies the strong-duality and KKT conditions invoked in Theorem 1."},{"cited_title":"Distributed optimization and statistical learning via the alternating direction method of multipliers","cited_arxiv_id":null,"evidence_quote":"Supplies the ADMM framework and primal/dual residual definitions used by D-HADM."},{"cited_title":"Stellato, G","cited_arxiv_id":null,"evidence_quote":"Supplies the operator-splitting parameter updates, equilibration, and over-relaxation techniques adopted."},{"cited_title":"Efficient Lexicographic Optimization for Prioritized Robot Control and Planning","cited_arxiv_id":"2403.09160","evidence_quote":"Provides the primal ADMM HLSP solver referenced for warm-start and embedded use."}],"review_version":1}