Computation of the Epsilon-Subdifferential of Convex Piecewise Linear-Quadratic Functions in Optimal Worst-Case Time
Copyright policy )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.
convex function, Numerical optimization and variational techniques, Piecewise linear-quadratic functions, piecewise linear-quadratic functions, \(\epsilon\)-subdifferentials, subdifferential, Optimization algorithms, Computer-Aided Convex Analysis, computational convex analysis (CCA), ε-Subdifferentials, computer-aided convex analysis, Convex Function, visualization, Subdifferential, Computational Convex Analysis (CCA), Visualization
convex function, Numerical optimization and variational techniques, Piecewise linear-quadratic functions, piecewise linear-quadratic functions, \(\epsilon\)-subdifferentials, subdifferential, Optimization algorithms, Computer-Aided Convex Analysis, computational convex analysis (CCA), ε-Subdifferentials, computer-aided convex analysis, Convex Function, visualization, Subdifferential, Computational Convex Analysis (CCA), Visualization
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).1 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!