{"id":"054034d6-3417-420b-89c4-81a9db5208bc","arxiv_id":"2501.18503","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":1,"one_line_summary":"Piecewise-affine root-finding and global minimization in abs-normal form are shown equivalent to MLCP/LCP and LPCC/MILP problems, without requiring J nonsingularity.","lead":"New complementarity formulations turn root-finding and optimization of piecewise-affine functions in abs-normal form into standard mixed linear complementarity problems and linear programs with complementarity constraints, with fewer restrictions than prior work. The results extend automatic differentiation based piecewise-linearization and connect abs-normal forms to mature solvers like PATH.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Main root-finding theorem is sound; the load-bearing gap is Lemma 4.3, whose limit proof drops λc and λb and never justifies convergence of λz(x/λ).","rationale":"The reader's conditional verdict is appropriate. The central root-finding result, Theorem 3.1, is correct: I independently checked the definitions of ~c, ~b, ~L, ~Z, ~J, ~Y and the elimination of u in both directions, and the MLCP (3.4) and LCP (3.6) equivalences hold without requiring m=n or nonsingular J. The optimization equivalence in Theorem 4.1 also follows from the same construction. The only significant gap is Lemma 4.3, exactly as the reader identified: the horizon function's abs-normal form is asserted via a 'take the limit' argument that suppresses the λc and λb terms and does not justify convergence of λz(x/λ). Since Corollary 4.2 applies Theorem 3.1 to f∞+1, the existence-of-minimum test inherits this gap. This is a proof-completeness issue, not a demonstrated counterexample, so the correct disposition is to keep the paper conditional pending a rigorous proof of Lemma 4.3; no change to the reader's verdict is needed.","tokens_in":14401,"tokens_out":23365,"duration_ms":245311,"concrete_test":"Write out a complete proof of Lemma 4.3: for a fixed direction x not lying on any kink hyperplane, let z_λ solve z_λ=c+Z(x/λ)+L|z_λ|, fix the eventual sign pattern Σ, multiply by λ, and prove the limit ζ=lim_{λ↓0}λz_λ satisfies ζ=Zx+LΣζ=Zx+L|ζ| and f∞(x)=Jx+Y|ζ|; then extend to all ξ by continuity of both the horizon function and the candidate PL function. As a numerical cross-check, generate 1000 random abs-normal forms with n,s≤5 and verify that λf(d/λ) at λ=10^{-6} equals Jξ+Y|ζ| with ζ solving ζ=Zξ+L|ζ|, to tolerance 10^{-4}.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 3.1 survives scrutiny: the algebra in Definition 3.1 and both directions of the MLCP equivalence check out, with no hidden regularity assumption beyond strict lower triangularity of L. The genuinely load-bearing weak point is Lemma 4.3, on which Corollary 4.2's existence test (4.11) depends. Its proof asserts that along each ray there is a fixed sign pattern Σ and a fixed affine piece aᵀy+b, then claims λf(x/λ)=aᵀx for all sufficiently small λ; this is not exact unless b=0, and the correct statement is aᵀx+λb. The proof also does not establish that the scaled limit ζ=lim_{λ↓0} λz(x/λ) exists and satisfies ζ=Zx+L|ζ|, nor does it reconcile the pointwise ray limit with the inf-over-neighborhood definition of f∞ at kink directions. These omissions make Corollary 4.2 conditional rather than fully proven; I found no counterexample, and the lemma is very likely true, but the proof as written is incomplete.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops complementarity formulations for root-finding and global optimization of piecewise-affine functions expressed in abs-normal form. Under the standing structural assumption that the matrix L in the abs-normal form is strictly lower triangular, Theorem 3.1 characterizes roots of f as solutions of a mixed linear complementarity problem, and reduces to a linear complementarity problem plus a linear solve when the transformed matrix ~J is square and nonsingular. Theorem 4.1 characterizes global minima of a scalar-valued PA function as solutions of a linear program with complementarity constraints, and Corollary 4.1 gives a big-M MILP reformulation. Corollary 4.2 proposes an MLCP whose infeasibility certifies existence of a global minimum, relying on properties of the horizon function. The paper also reports a Julia implementation and numerical experiments comparing the new formulations with earlier abs-normal root-finding approaches.","tokens_in":14606,"tokens_out":9203,"duration_ms":87725,"significance":"If fully validated, the paper makes a useful and genuine extension of prior work: the root-finding reformulation in Theorem 3.1 removes the restrictions m=n and nonsingularity of J that appear in Proposition 2.1, while the proof is self-contained, algebraic, and free of fitted parameters. The constructions of ~J, ~Y, ~L, ~Z, ˇc, ˇS are explicit, and the LPCC/MILP reformulations for optimization are natural and potentially useful. The implementation is publicly available on GitHub, and the authors honestly note in Section 7 that the abs-normal forms in the examples were computed by hand rather than generated automatically. The principal weakness is the proof of Lemma 4.3, on which the existence test Corollary 4.2 depends; that lemma is very likely true, but the proof as written is incomplete. With that proof repaired, the paper would be a solid contribution to nonsmooth equation solving and optimization.","major_comments":[{"comment":"The proof of Lemma 4.3 is incomplete, and Corollary 4.2 therefore rests on an unjustified step. The proof fixes x and claims that for all sufficiently small lambda one has lambda f(x/lambda) = a^T x for a fixed affine piece a^T y + b; the correct expression is lambda f(x/lambda) = a^T x + lambda b, so the affine intercept does not disappear by the stated equality. More importantly, the proof does not show that zeta(lambda) := lambda z(x/lambda) converges as lambda tends to 0+, nor that the limit zeta satisfies zeta = Z xi + L |zeta|, nor that this ray limit coincides with the inf-over-neighborhood definition of the horizon function in Definition 4.1 at kink directions. Since Lemma 4.3 is the bridge between Lemma 4.2 and the MLCP (4.11), Corollary 4.2 is conditional on a repair. A proof can be supplied by recursive substitution: because L is strictly lower triangular, zeta(lambda) is defined row by row by zeta_i(lambda) = (Z xi)_i + sum_{j<i} L_ij |zeta_j(lambda)| + lambda c_i, and continuity at lambda = 0 gives the required limit; the neighborhood infimum can then be handled by the piecewise-linear structure of the limiting function.","section":"Section 4.2, Lemma 4.3"}],"minor_comments":[{"comment":"The step 'inf_{xi in X} f^infinity(xi) = 0 implies f^infinity(xi) >= 0 for each xi in X' is not immediate; as written it is not a direct consequence of the infimum being zero. The intended argument is that if f^infinity took a negative value at some xi in X, then positive homogeneity and 0 in int(X) would give negative values along the ray t xi inside X for all sufficiently small t > 0, contradicting inf = 0. This is easy to repair but should be stated.","section":"Section 4.2, Lemma 4.1"},{"comment":"The statement says 'where e in R^m denotes a vector of ones', but the inequalities w <= mu e and ~c + ~Z x + ~L w <= mu e involve vectors in R^s, not R^m. The symbol e should denote the vector of ones in R^s.","section":"Corollary 4.1"},{"comment":"The random instances are generated with J = I and Z = 0, so the numerical comparisons do not exercise the singular-J cases that distinguish the new root-finding result from the previous approach of Griewank et al. The reported CPU times are averages over 100 runs without standard deviations or success rates; adding these would make the empirical claims more informative.","section":"Section 6, Examples 5 and 6"},{"comment":"There is a typo in the sentence discussing Hegerhorst-Schultchen et al.: 'genearlized abs-normal form' should read 'generalized abs-normal form'.","section":"Section 2, paragraph on [12]"}],"recommendation":"major_revision","confidential_remarks":"The central algebraic theorems (Theorems 3.1 and 4.1) appear sound, and the paper's main claim is a genuine extension of earlier work. The only load-bearing gap is the proof of Lemma 4.3, which is likely true but needs a rigorous argument; once repaired, the paper should be suitable for publication. The numerical experiments are illustrative rather than exhaustive, but they are not the basis for my recommendation."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This paper does something genuinely useful. The key move is to exploit the strict lower triangularity of L in the abs-normal form via (I-L)^{-1}, which yields an MLCP root-finding formulation (3.4) that works for any piecewise-affine function, with no requirement that m=n or that J be nonsingular. That is a real improvement over Griewank et al.'s Proposition 2.1. When \\tilde J is nonsingular, the LCP reduction (3.6) is clean, and the algebra in Theorem 3.1 checks out: the 'only if' direction sets u=max(0,z), w=max(0,-z), and the 'if' direction reconstructs z from u-w. I found no hidden regularity assumptions. The optimization half is also new and correct: LPCC (4.8) for global minimization, the big-M MILP (4.9), and the existence test (4.11) via horizon functions. Theorem 4.1's proof is self-contained and fine. The paper is honest about what it does and does not do, and the citations are appropriate. Credit is due for the singular-J example, where the old formulation fails but the new one works.\n\nThe main soft spot is Lemma 4.3, on which Corollary 4.2 depends. The proof asserts that along each ray, after scaling, f behaves like a single affine piece with no constant term, then 'take the limit' to claim the horizon function has the same Z, L, J, Y with c and b removed. That is not justified as written. The constant term does not vanish under \\lambda f(x/\\lambda) unless you also drop \\lambda b, and the convergence of \\lambda z(x/\\lambda) to a \\zeta satisfying \\zeta = Z\\xi + L|\\zeta| is assumed rather than proved. The stress-test note is right. This makes the existence test conditional, though I would bet the lemma is true and the gap is repairable. It should be fixed before the result is used in proofs elsewhere.\n\nThe numerical study is a proof of concept, not a benchmark. It averages CPU times over 100 runs but reports no variance or seeds, and the scaling tests set J=I and Z=0, so the singular-J regime that motivated the new MLCP never appears in the scaling data. Example 3 is a lone singular-J instance. That is a minor criticism at this stage, but worth noting.\n\nThe citation pattern is solid. The derivations are self-contained; no fitted parameters enter the theory, and \\tilde J, \\tilde S are defined explicitly. I found no circularity or invented entities.\n\nBottom line: the core results are correct and genuinely extend the state of the art. The existence-of-minimum corollary needs a more careful proof, and the numerics could be more informative, but the paper deserves a serious referee. I would engage with it.","headline":"New complementarity formulations that actually remove the squareness/nonsingularity restrictions; the main theorems are sound, but the existence-of-minimum corollary leans on an under-proved lemma.","tokens_in":871,"tokens_out":871,"would_cite":true,"duration_ms":33035,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C33","90C26","49J52","65K05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Root-finding for piecewise-affine functions in abs-normal form is always equivalent to an MLCP, and optimization becomes an LPCC or MILP.","keywords":["piecewise-affine functions","abs-normal form","mixed linear complementarity problem","linear complementarity problem","linear program with complementarity constraints","horizon function","global optimization","nonsmooth optimization"],"falsifier":"Compute the horizon function $f^\\infty$ of a specific scalar piecewise-affine function directly from its affine pieces, then compare it with the abs-normal form $(Z,L,J,Y)$ with $c=b=0$ claimed by Lemma 4.3; a mismatch would invalidate the existence test (4.11). Alternatively, solve (3.4) for a piecewise-affine function where the MLCP has a solution $(x,w)$ but $f(x)\\neq 0$, which would refute Theorem 3.1.","tokens_in":14183,"feed_emoji":"🧮","tokens_out":10950,"duration_ms":82160,"temperature":0.7,"pith_summary":"The paper establishes that any piecewise-affine function written in abs-normal form—a standardized encoding as affine maps and absolute values—can be root-found by solving a standard mixed linear complementarity problem, with no need for the system to be square or its linear part nonsingular. A parallel construction turns global minimization of a scalar piecewise-affine function into a linear program with complementarity constraints, which becomes a mixed-integer linear program once bounds are known. The paper also provides a check for whether a global minimum exists, built on the function's horizon function. If these formulations are right, existing complementarity and MILP solvers can be applied directly to piecewise-affine systems from nonsmooth dynamics, ReLU networks, and contact mechanics.","feed_headline":"Piecewise-affine root-finding is always an MLCP","feed_subtitle":"A triangular abs-normal form turns piecewise-affine optimization into LPCCs, MILPs, and an existence check.","key_machinery":"The central object is the abs-normal form (2.1), which encodes a piecewise-affine function as $z = c + Zx + L|z|$ and $f(x) = b + Jx + Y|z|$, with $L$ strictly lower triangular. The key step is the change of variables $u = \\max(0,z)$ and $w = \\max(0,-z)$, so that $z = u - w$ and $|z| = u + w$. Strict lower triangularity makes $I-L$ unit lower triangular, so $u$ can be expressed explicitly as $\\tilde{c} + \\tilde{Z}x + \\tilde{L}w$, converting the recursive definition of $z$ into a complementarity condition $0 \\le w \\perp u \\ge 0$. This yields the MLCP of Theorem 3.1, and eliminating $x$ via $\\tilde{J}$ gives the LCP (3.6). The same machinery underlies the LPCC (4.8) and the existence check (4.11).","core_discovery":"The central claim is Theorem 3.1: under Assumption 2.1, $f(x)=0$ if and only if there exists $w$ for which $(x,w)$ solves the MLCP $$0 = \\tilde{b} + \\tilde{J}x + \\tilde{Y}w,\\quad 0 \\le w \\perp \\tilde{c} + \\tilde{Z}x + \\tilde{L}w \\ge 0,$$ with no requirement that $m=n$ or $J$ be nonsingular. When $m=n$ and $\\tilde{J}$ is nonsingular, roots correspond exactly to solutions of the LCP $0 \\le w \\perp \\check{c} + \\check{S}w \\ge 0$ together with $\\tilde{J}x = -\\tilde{b} - \\tilde{Y}w$. For optimization, Theorem 4.1 shows that $x^*$ is a global minimum of a scalar piecewise-affine $f$ if and only if $(x^*,w^*)$ solves the LPCC (4.8), and Corollary 4.2 shows that a global minimum exists exactly when the MLCP (4.11) built from the horizon function has no solution. The proof replaces the triangular system for $z$ by a complementarity system for the positive and negative parts $u,w$ of $z$.","pith_inferences":["Inference: If the abs-normal form is ever generated automatically for trained ReLU networks—the paper lists this as future work—the same reformulations would give a direct route from network parameters to equations solvable by mature complementarity software.","Inference: The strict lower triangularity of $L$ is inherited from the order in which absolute values are evaluated; a piecewise-affine function supplied in a differently ordered abs-normal form might require a reordering step before this machinery applies, since the formulas depend on this triangular structure.","Inference: The numerical comparison suggests that when $\\tilde{J}$ is nonsingular, the reduced LCP is the more scalable option, and a formal worst-case complexity analysis of the MLCP versus LCP formulations would help decide when to use each.","Inference: The horizon-function existence test and the minimization reformulation can be chained: first verify infeasibility of (4.11), then solve (4.8) or (4.9), yielding a complete global-optimization pipeline for abs-normal-form piecewise-affine functions."],"forward_implications":["Existing PATH and other LCP/MLCP solvers can be applied to piecewise-affine root-finding without the squareness and nonsingularity restrictions of the earlier approach.","When $\\tilde{J}$ is nonsingular, root-finding reduces to a smaller LCP followed by a linear solve, which the numerical examples show is faster than solving the full MLCP.","Minimizing a scalar piecewise-affine function becomes an LPCC, and, when a bound $\\mu$ is known, an MILP via a big-M reformulation with binary variables.","Whether a global minimum exists at all can be decided by testing infeasibility of the MLCP (4.11), an approach that relies on the horizon function inheriting the same $Z,L,J,Y$.","Any improvement in LCP, MILP, or LPCC solvers automatically improves computations with piecewise-affine functions expressed in abs-normal form."],"supporting_citations":[{"why":"Introduces the abs-normal form and the earlier complementarity root-finding method (Proposition 2.1) that this paper generalizes.","marker":"[9]"},{"why":"Develops the abs-normal form representation of piecewise-affine functions via piecewise-linearization, which this paper takes as input.","marker":"[10]"},{"why":"Supplies the standard properties of piecewise-affine functions and the recession/horizon function used in Lemma 4.1 and Lemma 4.3.","marker":"[22]"},{"why":"Provides the definition and homogeneity theorem for horizon functions used to characterize existence of minima.","marker":"[20]"},{"why":"Is the standard reference for LCP theory, including the Q-matrix and P-matrix concepts used in Corollary 3.1.","marker":"[3]"},{"why":"Defines the mixed complementarity problem and the PATH solver used to solve the MLCP/LCP formulations.","marker":"[4]"},{"why":"Establishes the LPCC framework that Theorem 4.1 plugs into for global minimization.","marker":"[13]"},{"why":"Provides the big-M integer-programming reformulation that Corollary 4.1 applies to turn the LPCC into an MILP.","marker":"[19]"}],"fun_headline_variants":["Piecewise-affine root-finding is always an MLCP","New MLCP formulation for nonsmooth root-finding","Complementarity unifies piecewise-affine root-finding and optimization","Always an MLCP: piecewise-affine root-finding without restrictions","From piecewise-affine to LPCC: a unified complementarity view"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the piecewise-affine function is supplied in abs-normal form with a strictly lower triangular matrix $L$, and that the horizon function inherits exactly the same $Z,L,J,Y$ with $c$ and $b$ removed—the step in Lemma 4.3 whose proof glosses over a limit of switching active pieces.","fun_headline_variants_meta":{"raw":{"variants":["Piecewise-affine root-finding is always an MLCP","New MLCP formulation for nonsmooth root-finding","Complementarity unifies piecewise-affine root-finding and optimization","Always an MLCP: piecewise-affine root-finding without restrictions","From piecewise-affine to LPCC: a unified complementarity view"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000302,"raw_usage":{"total_tokens":1774,"prompt_tokens":1011,"completion_tokens":763,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":627,"completion_tokens_details":{"reasoning_tokens":674}},"tokens_in":627,"tokens_out":763,"duration_ms":7242,"temperature":1.0,"reasoning_tokens":674,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T23:14:32.665076+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the horizon function $f^\\infty$ of a specific scalar piecewise-affine function directly from its affine pieces, then compare it with the abs-normal form $(Z,L,J,Y)$ with $c=b=0$ claimed by Lemma 4.3; a mismatch would invalidate the existence test (4.11). Alternatively, solve (3.4) for a piecewise-affine function where the MLCP has a solution $(x,w)$ but $f(x)\\neq 0$, which would refute Theorem 3.1.","supporting_citations":[{"cited_title":"Griewank, J.-U","cited_arxiv_id":null,"evidence_quote":"Introduces the abs-normal form and the earlier complementarity root-finding method (Proposition 2.1) that this paper generalizes."},{"cited_title":"Griewank, A","cited_arxiv_id":null,"evidence_quote":"Develops the abs-normal form representation of piecewise-affine functions via piecewise-linearization, which this paper takes as input."},{"cited_title":"Scholtes, Introduction to piecewise differentiable equations, SpringerBriefs in Optimization, Springer, New York, NY, 2012","cited_arxiv_id":null,"evidence_quote":"Supplies the standard properties of piecewise-affine functions and the recession/horizon function used in Lemma 4.1 and Lemma 4.3."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the definition and homogeneity theorem for horizon functions used to characterize existence of minima."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Is the standard reference for LCP theory, including the Q-matrix and P-matrix concepts used in Corollary 3.1."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the mixed complementarity problem and the PATH solver used to solve the MLCP/LCP formulations."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the LPCC framework that Theorem 4.1 plugs into for global minimization."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the big-M integer-programming reformulation that Corollary 4.1 applies to turn the LPCC into an MILP."}],"review_version":1}