Linear-Time Convexity Test for Low-Order Piecewise Polynomials
针对二次和三次分段函数，提出线性时间算法检验其凸性，并给出MATLAB实现，适用于含凸性约束的优化问题。
Given a piecewise-defined function, checking whether it is convex is a nontrivial task. While it may be easy to check whether the restriction of the function to each piece is convex, ensuring the entire function is convex seems to require global conditions. However, it is known that one only needs to ensure the (convex) subdifferential is nonempty on the boundary of the pieces thereby obtaining more local conditions. We specialize the results to quadratic and cubic piecewise defined functions and provide linear-time algorithms to check their convexity. We also provide a MATLAB implementation using an edge-list data structure and discuss two applications: checking the structure of piecewise quadratic functions and optimization problems involving convexity constraints.