Computation of the epsilon-subdifferential of convex piecewise linear-quadratic functions in optimal worst-case time

The epsilon-subdifferential of convex univariate piecewise linear-quadratic (PLQ) functions can be computed in linear worst-case time complexity as the level-set of a convex function. Using binary search, we improve the complexity to logarithmic worst-case time, and prove such complexity is optimal. In addition, a new algorithm to compute the entire graph of the epsilon-subdifferential in (optimal) linear time is presented. Both algorithms are not limited to convex PLQ functions but are also applicable to any convex piecewise-defined functions with little restrictions.Arts and Sciences, Irving K. Barber School of (Okanagan)Computer Science, Mathematics, Physics and Statistics, Department of (Okanagan)ReviewedFacultyResearche