Polyhedral DC Decomposition and DCA Optimization of Piecewise Linear Functions
2020
Online
Elektronische Ressource
For piecewise linear functions f:Rn↦R we show how their abs-linear representation can be extended to yield simultaneously their decomposition into a convex fˇ and a concave part fˆ , including a pair of generalized gradients gˇ∈Rn∋gˆ . The latter satisfy strict chain rules and can be computed in the reverse mode of algorithmic differentiation, at a small multiple of the cost of evaluating f itself. It is shown how fˇ and fˆ can be expressed as a single maximum and a single minimum of affine functions, respectively. The two subgradients gˇ and −gˆ are then used to drive DCA algorithms, where the (convex) inner problem can be solved in finitely many steps, e.g., by a Simplex variant or the true steepest descent method. Using a reflection technique to update the gradients of the concave part, one can ensure finite convergence to a local minimizer of f, provided the Linear Independence Kink Qualification holds. For piecewise smooth objectives the approach can be used as an inner method for successive piecewise linearization.
Peer Reviewed
Titel: |
Polyhedral DC Decomposition and DCA Optimization of Piecewise Linear Functions
|
---|---|
Link: | |
Veröffentlichung: | 2020 |
Medientyp: | Elektronische Ressource |
Schlagwort: |
|
Sonstiges: |
|