Pith. sign in

REVIEW 1 major objections 4 minor 26 references

New complementarity formulations for root-finding and optimization of piecewise-affine functions in abs-normal form

T0 review · 1 major / 4 minor · reviewed 2026-08-09 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Root-finding for piecewise-affine functions in abs-normal form is always equivalent to an MLCP, and optimization becomes an LPCC or MILP.

desk verdict 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. read the letter →

arxiv 2501.18503 v1 pith:RBRJDXPN submitted 2025-01-30 math.OC cs.NAmath.NA

Yulan Zhang , Kamil A. Khan This is my paper · ORCID
classification math.OCcs.NAmath.NA MSC 90C3390C2649J5265K05
keywords piecewise-affinefunctionsabs-normalformmixedlinearcomplementarityproblemprogramwithconstraintshorizonfunctionglobaloptimizationnonsmooth
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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).

What would settle it

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.

Watch

Extended reading notes

Core claim

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$.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 4 minor

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.

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 (1)
  1. [Section 4.2, Lemma 4.3] 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.
minor comments (4)
  1. [Section 4.2, Lemma 4.1] 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.
  2. [Corollary 4.1] 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.
  3. [Section 6, Examples 5 and 6] 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.
  4. [Section 2, paragraph on [12]] There is a typo in the sentence discussing Hegerhorst-Schultchen et al.: 'genearlized abs-normal form' should read 'generalized abs-normal form'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the MLCP/LCP/LPCC equivalences are proved by explicit algebraic manipulation of the abs-normal form, with no fitted parameters, no load-bearing self-citations, and no target result assumed as an input.

full rationale

Theorem 3.1 is self-contained: it defines u=max(0,z) and w=max(0,-z), so z=u-w and |z|=u+w, substitutes these identities into (2.1), and applies Definition 3.1 to obtain (3.4); the converse reconstructs z from (3.7) and verifies (2.1). No regularity beyond strict lower triangularity of L is hidden, and no parameter is fitted to the roots being predicted. Theorem 4.1 uses the same bijection between x and w to prove equality of the original minimization and the LPCC (4.8), and Corollary 4.2 chains standard horizon-function facts from Rockafellar-Wets [20] and Scholtes [22] with Lemma 4.3. The only self-citation, [15], appears in a background sentence about automatic differentiation and does not support any theorem. Lemma 4.3's assertion that the horizon function has the same Z,L,J,Y with c and b removed is the least rigorous step: the proof says 'take the limit' while dropping the λb term and does not justify convergence of λz(x/λ). That is a proof gap or correctness risk, not a circular reduction, because the abs-normal form of f^∞ is not assumed but derived from the recession function; no quoted equation shows the claimed result being fed back as an input. The implementation limitation that abs-normal forms were computed by hand in the examples also does not affect the theoretical derivations. Under the hard rules, no circular step can be exhibited, so the score is 0.

Assumptions & free parameters 1 free parameters · 5 assumptions · 0 invented entities

The central results use no fitted constants. The only hand-chosen numerical quantity is the big-M bound mu. The derivations rely on external standard background (abs-normal form existence from [9,10], LCP theory from [3], PA polyhedral theory from [22], horizon functions from [20]) and on the solver behavior of PATH. No new entities are introduced.

free parameters (1)
  • big-M bound mu = 10^5 (default)
    User-supplied bound needed for the MILP (4.9); if too small, valid solutions may be cut off. The implementation defaults to 10^5, so the practical optimization results depend on this hand-chosen value.
assumptions (5)
  • domain assumption Every continuous PA function has an abs-normal form (2.1) with strictly lower triangular L (Assumption 2.1).
    The paper assumes the abs-normal form as input; existence was established in [9,10] and is not reproven here.
  • standard math Standard LCP theory: existence and uniqueness properties of P-matrices and Q-matrices (Cottle-Pang-Stone [3]).
    Used in Corollary 3.1 to characterize when the constructed LCP (3.6) has a solution.
  • standard math Polyhedral decomposition and recession cones of PA functions (Scholtes [22]).
    Used in Lemma 4.1 to reduce existence of a minimum to checking recession directions.
  • standard math Horizon function definition and positive homogeneity (Rockafellar-Wets [20]).
    Provides f^infinity and its basic property f^infinity(0)=0; used in Lemmas 4.1 and 4.2.
  • domain assumption PATH solver is a reliable solver for the constructed MCPs under nonsingularity assumptions (Dirkse-Ferris [4]).
    The numerical strategy relies on the solver; the paper reports failures at larger n but does not analyze them.

how reviews work

0 comments
Cite this review

Pith. "Pith review of New complementarity formulations for root-finding and optimization of piecewise-affine functions in abs-normal form." pith.science (2026). https://pith.science/paper/RBRJDXPN

@misc{pith2026250118503,
  author       = {Pith},
  title        = {Pith review of: New complementarity formulations for root-finding and optimization of piecewise-affine functions in abs-normal form},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RBRJDXPN}},
  note         = {Machine review of arXiv:2501.18503}
}
read the original abstract

Nonsmooth functions have been used to model discrete-continuous phenomena such as contact mechanics, and are also prevalent in neural network formulations via activation functions such as ReLU. At previous AD conferences, Griewank et al. showed that nonsmooth functions may be approximated well by piecewise-affine functions constructed using an AD-like procedure. Moreover, such a piecewise-affine function may always be represented in an "abs-normal form", encoding it as a collection of four matrices and two vectors. We present new general complementarity formulations for root-finding and optimization of piecewise-affine functions in abs-normal form, with significantly fewer restrictions than previous approaches. In particular, piecewise-affine root-finding may always be represented as a mixed-linear complementarity problem (MLCP), which may often be simplified to a linear complementarity problem (LCP). We also present approaches for verifying existence of solutions to these problems. A proof-of-concept implementation in Julia is discussed and applied to several numerical examples, using the PATH solver to solve complementarity problems.

Figures

Figures reproduced from arXiv: 2501.18503 by the authors.

Figure 1
Figure 1. The horizon function f∞ (dashed) for the piecewise affine function f given by (4.10) (solid). Lemma 4.1. Suppose that f : R n → R is PA, and choose a set X ⊂ R n for which 0 ∈ int(X). The function f has a (global) minimum in R n if and only if infξ∈X f∞(ξ) = 0. Copyright © 2025 by SIAM Unauthorized reproduction of this article is prohibited [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. CPU time (s) for generating a random PA function in Example 5 and determining its root using our new root-finding approaches (including computing all necessary vectors, matrices, and solving the corresponding formulations), averaged over 100 runs. The inset figure zooms in on the lower-left corner. In the following example, we compare our new root-finding formulations MLCP (3.4) and LCP (3.6) with the approach of Gr… view at source ↗
Figure 3
Figure 3. CPU time (s) for generating a random PA function in Example 6 and determining its root using both our new approaches and Griewank et al.’s approaches (including computing all necessary vectors, matrices, and solving the corresponding formulations), averaged over 100 runs. The inset figure zooms in on the lower-left corner. varied for illustration: f(x) = [PITH_FULL_IMAGE:figures/full_fig_p013_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: CPU time (s) for computing our auxiliary matrices/vectors in Definition 3.1 for the function f in Example 7 (yellow), and for minimizing it via our MILP formulation (red) and our LPCC formulation (blue), averaged over 100 runs. The inset figure zooms in on the lower-le…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages

  1. [1]

    Bosse, (Almost) matrix-free solver for piecewise linear functions in abs-normal form , Numerical Linear Algebra with Applications, 26 (2019), p

    T. Bosse, (Almost) matrix-free solver for piecewise linear functions in abs-normal form , Numerical Linear Algebra with Applications, 26 (2019), p. e2258

    work page 2019

  2. [2]

    T. F. Bosse and S. H. K. Narayanan, Study of the numerical efficiency of structured abs-normal forms , Optimization Methods and Software, 36 (2021), pp. 909–933

    work page 2021

  3. [3]

    R. W. Cottle, J.-S. Pang, and R. E. Stone, The Linear Complementarity Problem , Classics in Applied Mathematics, SIAM, Philadelphia, 2009

    work page 2009

  4. [4]

    S. P. Dirkse and M. C. Ferris, The PATH solver: a non-monotone stabilization scheme for mixed complementarity problems, Optim. Method. Softw., 5 (1995), pp. 123–156

    work page 1995

  5. [5]

    M. C. Ferris and T. S. Munson, Interfaces to PATH 3.0: design, implementation and usage , Comput. Optim. Appl., 12 (1999), pp. 207–227

    work page 1999

  6. [6]

    Fiege, A

    S. Fiege, A. W alther, K. Kulshreshtha, and A. Griewank, Algorithmic differentiation for piecewise smooth functions: a case study for robust optimization , Optimization Methods and Software, 33 (2018), pp. 1073–1088

    work page 2018

  7. [7]

    Fukushima and J.-S

    M. Fukushima and J.-S. Pang, Some feasibility issues in mathematical programs with equilibrium constraints, SIAM J. Optim., 8 (1998), pp. 673–681

    work page 1998

  8. [8]

    Griewank, On stable piecewise linearization and generalized algorithmic differentiation , in The 6th International Conference on Automatic Differentiation, Colorado, 2012

    A. Griewank, On stable piecewise linearization and generalized algorithmic differentiation , in The 6th International Conference on Automatic Differentiation, Colorado, 2012

    work page 2012

Show all 26 references
  1. [9]

    Griewank, J.-U

    A. Griewank, J.-U. Bernt, M. Radons, and T. Streubel, Solving piecewise linear systems in abs-normal form , Linear Algebra Appl., 471 (2015), pp. 500–530

    2015

  2. [10]

    Griewank, A

    A. Griewank, A. W alther, S. Fiege, and T. Bosse, On Lipschitz optimization based on gray-box piecewise linearization, Math. Program. A, 158 (2016), pp. 383–415

    2016

  3. [11]

    L. C. Hegerhorst-Schultchen, Optimality conditions for abs-normal NLPs , (2020)

    2020

  4. [12]

    L. C. Hegerhorst-Schultchen, C. Kirches, and M. C. Steinbach, On the relation between MPECs and optimization problems in abs-normal form , Optimization Methods and Software, 35 (2020), pp. 560–575. Copyright © 2025 by SIAM Unauthorized reproduction of this article is prohibited

    2020

  5. [13]

    J. Hu, J. E. Mitchell, J.-S. Pang, and B. Yu, On linear programs with linear complementarity constraints , J. Glob. Optim., 53 (2012), pp. 29–51

    2012

  6. [14]

    Kazda and X

    K. Kazda and X. Li, Nonconvex multivariate piecewise-linear fitting using the difference-of-convex representation , Computers & Chemical Engineering, 150 (2021), p. 107310

    2021

  7. [15]

    K. A. Khan and P. I. Barton, Evaluating an element of the Clarke generalized Jacobian of a piecewise differentiable function, in Recent Advances in Algorithmic Differentiation, S. Forth, P. Hovland, E. Phipps, J. Utke, and A. Walther, eds., Springer-Verlag, Berlin, 2012, pp. 115–125

    2012

  8. [16]

    Kubota, Enumeration of subdifferentials of piecewise linear functions with abs-normal form , Optimization Methods and Software, 33 (2018), pp

    K. Kubota, Enumeration of subdifferentials of piecewise linear functions with abs-normal form , Optimization Methods and Software, 33 (2018), pp. 1156–1172

    2018

  9. [17]

    Kwon and O

    C. Kwon and O. Dowson, PATHSolver.jl. https://github.com/chkwon/PATHSolver.jl, 2024

    2024

  10. [18]

    Lubin, O

    M. Lubin, O. Dowson, J. Dias Garcia, J. Huchette, B. Legat, and J. P. Vielma, JuMP 1.0: Recent improvements to a modeling language for mathematical optimization , Mathematical Programming Computation, (2023)

    2023

  11. [19]

    P. M. Pardalos, Linear complementarity problems solvable by integer programming , Optimization, 19 (1988), pp. 467–474

    1988

  12. [20]

    R. T. Rockafellar and R. J.-B. Wets, Variational Analysis, A Series of Comprehensive Studies in Mathematics, Springer, Berlin, 1998

    1998

  13. [21]

    N. V. Sahinidis, BARON: A general purpose global optimization software package , Journal of global optimization, 8 (1996), pp. 201–205

    1996

  14. [22]

    Scholtes, Introduction to piecewise differentiable equations, SpringerBriefs in Optimization, Springer, New York, NY, 2012

    S. Scholtes, Introduction to piecewise differentiable equations, SpringerBriefs in Optimization, Springer, New York, NY, 2012

    2012

  15. [23]

    Siebert, J

    T. Siebert, J. Fuhrmann, and A. W alther, ADOLC.jl: A Julia-Wrapper for ADOL-C . Presentation at the 8th International Conference on Algorithmic Differentiation, 2024

    2024

  16. [24]

    Streubel, A

    T. Streubel, A. Griewank, M. Radons, and J.-U. Bernt, Representation and analysis of piecewise linear functions in abs-normal form , in System Modeling and Optimization: 26th IFIP TC 7 Conference, CSMO 2013, Klagenfurt, Austria, September 9-13, 2013, Revised Selected Papers 26...

    2013

  17. [25]

    W alther and A

    A. W alther and A. Griewank, Getting started with ADOL-C, in Combinatorial Scientific Computing, U. Naumann and O. Schenk, eds., CRC Press, Boca Raton, 2012, pp. 181–202

    2012

  18. [26]

    B. Yu, J. E. Mitchell, and J.-S. Pang, Solving linear programs with complementarity constraints using branch- and-cut. Preprint, http://www.optimization-online.org/DB_HTML/2016/10/5689.html, 2016. Copyright © 2025 by SIAM Unauthorized reproduction of this article is prohibited

    2016

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.