A piecewise linear function can be described in different forms: as a nested expression of min - and max-functions, as a difference of two convex piecewise linearfunctions, or as a linearcombination of maxima of aff...
详细信息
A piecewise linear function can be described in different forms: as a nested expression of min - and max-functions, as a difference of two convex piecewise linearfunctions, or as a linearcombination of maxima of affine-linearfunctions. In this paper, we provide two main results: first, we show that for every piecewise linear function f : R-n -> R, there exists a linear combination of max-functions with at most n + 1 arguments, and give an algorithm for its computation. Moreover, these arguments are contained in the finite set of affine-linearfunctions that coincide with the given function in some open set. Second, we prove that the piecewise linear function max(0, x(1),., x(n)) cannot be represented as a linearcombination of maxima of less than n + 1 affine-linear arguments. This was conjectured by Wang and Sun (IEEE Trans Inf Theory 51:4425-4431, 2005) in a paper on representations of piecewise linearfunctions as linearcombination of maxima.
暂无评论