Open Collections

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 Metadata

Title
Computation of the epsilon-subdifferential of convex piecewise linear-quadratic functions in optimal worst-case time
Creator
Deepak, Kumar; Lucet, Yves
Publisher
Springer
Date Issued
2018
Description
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.
Subject
Subdifferential; ε-Subdifferentials; Piecewise linear-quadratic functions; Convex Function; Computational Convex Analysis (CCA); Computer-Aided Convex Analysis; Visualization; Optimization algorithms
Genre
Article
Type
Text
Language
eng
Date Available
2019-07-17
Provider
Vancouver : University of British Columbia Library
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International
DOI
10.14288/1.0379903
URI
http://hdl.handle.net/2429/71039
Affiliation
Arts and Sciences, Irving K. Barber School of (Okanagan); Computer Science, Mathematics, Physics and Statistics, Department of (Okanagan)
Citation
Kumar, D., & Lucet, Y. (2018). Computation of the epsilon-subdifferential of convex piecewise linear-quadratic functions in optimal worst-case time. Set-Valued and Variational Analysis.
Publisher DOI
10.1007/s11081-017-9366-1
Peer Review Status
Reviewed
Scholarly Level
Faculty; Researcher
Rights URI
http://creativecommons.org/licenses/by-nc-nd/4.0/
Aggregated Source Repository
DSpace

Item Media

Item Citations and Data

Rights

Attribution-NonCommercial-NoDerivatives 4.0 International