Computation of the Epsilon-Subdifferential of Convex Piecewise-Defined Functions in Optimal Worst-Case Time
arXiv:1803.01074 · doi:10.1007/s11228-018-0476-5
Abstract
The $ε$-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 dichotomic search, we show how the computation can be performed in logarithmic worst-case time. Furthermore, a new algorithm to compute the entire graph of the $ε$-subdifferential in linear time is presented. Both algorithms are not limited to convex PLQ functions but are also applicable to any convex piecewise-defined function with little restrictions.
16 pages, 7 figures; to appear in Set-Valued and Variational Analysis