UBC Faculty Research and Publications

Computation of the epsilon-subdifferential of convex piecewise linear-quadratic functions in optimal worst-case time Deepak, Kumar; Lucet, Yves

Abstract

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.

Item Citations and Data

Rights

Attribution-NonCommercial-NoDerivatives 4.0 International

Usage Statistics