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
- 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 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
- Evaluating Derivatives
- Explicit formulas for the solutions of piecewise linear networks
- Finite-Dimensional Variational Inequalities and Complementarity Problems
- 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?)
- 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
(29)- Finding normal solutions in piecewise linear programming
- An algorithm for nonsmooth optimization by successive piecewise linearization
- Nonsmooth Kantorovich-Newton methods: hypotheses and auxiliary problems
- Direct solution of piecewise linear systems
- Convergence results for some piecewise linear solvers
- On the convergence of iterative schemes for solving a piecewise linear system of equations
- First- and second-order optimality conditions for piecewise smooth objective functions
- Representation and analysis of piecewise linear functions in abs-normal form
- A semi-smooth Newton method for projection equations and linear complementarity problems with respect to the second order cone
- Explicit formulas for the solutions of piecewise linear networks
- 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\)
- Relaxing Kink Qualifications and Proving Convergence Rates in Piecewise Smooth Optimization
- Computationally relevant generalized derivatives: theory, evaluation and applications
- Algorithmic differentiation for piecewise smooth functions: a case study for robust optimization
- Integrating Lipschitzian dynamical systems using piecewise algorithmic differentiation
- Piecewise linear secant approximation via algorithmic piecewise differentiation
- Branch-locking AD techniques for nonsmooth composite functions and nonsmooth implicit functions
- 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
- On the abs-polynomial expansion of piecewise smooth functions
- Finite convergence of an active signature method to local minima of piecewise linear functions
- (Almost) matrix-free solver for piecewise linear functions in abs-normal form.
- Characterizing and testing subdifferential regularity in piecewise smooth optimization
- Study of the numerical efficiency of structured ABS-normal forms
- A semi-smooth Newton method for a special piecewise linear system with application to positively constrained convex quadratic programming
- Comments on: ``Two efficient iteration methods for solving the absolute value equations
- How stringent is the linear independence kink qualification in abs-smooth optimization?
- An overview of absolute value equations: from theory to solution methods and challenges
- An open Newton method for piecewise smooth systems
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)
