Data Convexity Check

Checks if given data may be represented by a convex function within a specified tolerance.

This is a quick and dirty way to test the convexity of an input-output data set - i.e. whether or not there exists a convex function that may fit the data within a specified residual tolerance. It was written for the purposes of testing a local convexity assumption on a set of noisy data, for which the residual tolerance is equal to the maximum magnitude of the noise.

The algorithm is simple and based on a linear-programming reformulation of the general convex-function interpolation problem (see, for example, p. 338 of "Convex Optimization" by Boyd and Vandenberghe). A linear program is solved to fit a piecewise-linear function to the data. If the maximum residual of the solution is greater than the specified error tolerance, then the hypothesis of the data representing a convex function is rejected (otherwise, it is kept).

The file calls the linprog function in MATLAB as the solver and does not attempt to exploit the structure of the constraint matrix. As such, it is likely only applicable for modest-size problems and may run out of memory otherwise. Anyone who would like to improve on this part of the file is more than welcome to do so. All other feedback/corrections is equally welcome.

Note: A data concavity check - to see if the data may be concave or not - can be done with the same file. The output vector just needs to be negated.