Solving piecewise linear systems in ABS-normal form
From MaRDI portal
Abstract: With the ultimate goal of iteratively solving piecewise smooth (PS) systems, we consider the solution of piecewise linear (PL) equations. PL models can be derived in the fashion of automatic or algorithmic differentiation as local approximations of PS functions with a second order error in the distance to a given reference point. The resulting PL functions are obtained quite naturally in what we call the abs-normal form, a variant of the state representation proposed by Bokhoven in his dissertation. Apart from the tradition of PL modeling by electrical engineers, which dates back to the Master thesis of Thomas Stern in 1956, we take into account more recent results on linear complementarity problems and semi-smooth equations originating in the optimization community. We analyze simultaneously the original PL problem (OPL) in abs-normal form and a corresponding complementary system (CPL), which is closely related to the absolute value equation (AVE) studied by Mangasarian et al and a corresponding linear complementarity problem (LCP). We show that the CPL, like KKT conditions and other simply switched systems, cannot be open without being injective. Hence some of the intriguing PL structure described by Scholtes is lost in the transformation from OPL to CPL. To both problems one may apply Newton variants with appropriate generalized Jacobians directly computable from the abs-normal representation. Alternatively, the CPL can be solved by Bokhoven's modulus method and related fixed point iterations. We compile the properties of the various schemes and highlight the connection to the properties of the Schur complement matrix, in particular its signed real spectral radius as analyzed by Rump. Numerical experiments and suitable combinations of the fixed point solvers and stabilized generalized Newton variants remain to be realized.
Recommendations
- Representation and analysis of piecewise linear functions in abs-normal form
- (Almost) matrix-free solver for piecewise linear functions in abs-normal form.
- Explicit formulas for the solutions of piecewise linear networks
- Direct solution of piecewise linear systems
- Convergence results for some piecewise linear solvers
Cites work
- scientific article; zbMATH DE number 3976197 (Why is no real title available?)
- scientific article; zbMATH DE number 53115 (Why is no real title available?)
- scientific article; zbMATH DE number 1414604 (Why is no real title available?)
- A comparison of piecewise-linear model descriptions
- A nonsmooth version of Newton's method
- Absolute value equations
- An algorithm for solving the absolute value equation
- Derived eigenvalues of symmetric matrices, with applications to distance geometry
- Direct solution of piecewise linear systems
- Evaluating Derivatives
- Evaluating an element of the Clarke generalized Jacobian of a composite piecewise differentiable function
- Evaluating an element of the Clarke generalized Jacobian of a piecewise differentiable function
- Explicit formulas for the solutions of piecewise linear networks
- Finite-Dimensional Variational Inequalities and Complementarity Problems
- Introduction to Piecewise Differentiable Equations
- Iterative Solution of Piecewise Linear Systems
- Lexicographic differentiation of nonsmooth functions
- Nichtlineare Funktionalanalysis
- On iterative solution for linear complementarity problem with an \(H_{+}\)-matrix
- On stable piecewise linearization and generalized algorithmic differentiation
- Singularities and groups in bifurcation theory. Volume I
- Systems of linear interval equations
- Theorems of Perron-Frobenius type for matrices without sign restrictions
- Using Piecewise Linear Functions for Solving MINLPs
- Widely Convergent Method for Finding Multiple Solutions of Simultaneous Nonlinear Equations
Cited in
(25)- Enumeration of subdifferentials of piecewise linear functions with ABS-normal form
- Generic construction and efficient evaluation of flow network DAEs and their derivatives in the context of gas networks
- Direct solution of piecewise linear systems
- Convergence results for some piecewise linear solvers
- Nonsmooth Kantorovich-Newton methods: hypotheses and auxiliary problems
- Relaxing Kink Qualifications and Proving Convergence Rates in Piecewise Smooth Optimization
- Study of the numerical efficiency of structured ABS-normal forms
- First- and second-order optimality conditions for piecewise smooth objective functions
- (Almost) matrix-free solver for piecewise linear functions in abs-normal form.
- On the abs-polynomial expansion of piecewise smooth functions
- Representation and analysis of piecewise linear functions in abs-normal form
- Finite convergence of an active signature method to local minima of piecewise linear functions
- Piecewise linear secant approximation via algorithmic piecewise differentiation
- A semi-smooth Newton method for a special piecewise linear system with application to positively constrained convex quadratic programming
- Integrating Lipschitzian dynamical systems using piecewise algorithmic differentiation
- Characterizing and testing subdifferential regularity in piecewise smooth optimization
- Finding normal solutions in piecewise linear programming
- A semi-smooth Newton method for projection equations and linear complementarity problems with respect to the second order cone
- Chow rings of \(\widetilde{M p}_{0, 2}(N, d)\) and \(\overline{M}_{0, 2}(\mathbb P^{N - 1}, d)\) and Gromov-Witten invariants of projective hypersurfaces of degree \(1\) and \(2\)
- An algorithm for nonsmooth optimization by successive piecewise linearization
- On the convergence of iterative schemes for solving a piecewise linear system of equations
- Branch-locking AD techniques for nonsmooth composite functions and nonsmooth implicit functions
- Computationally relevant generalized derivatives: theory, evaluation and applications
- Explicit formulas for the solutions of piecewise linear networks
- Algorithmic differentiation for piecewise smooth functions: a case study for robust optimization
This page was built for publication: Solving piecewise linear systems in ABS-normal form
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2261559)
