Computation of the Epsilon-Subdifferential of Convex Piecewise-Defined Functions in Optimal Worst-Case Time

Deepak Kumar, Yves Lucet

The $\epsilon$-subdifferential of convex univariate piecewise linear-quadratic functions can be computed in linear worst-case time complexity as the level-set of a convex function. Using…