Code covered by the BSD License  

Highlights from
Data Convexity Check

Be the first to rate this file! 19 Downloads (last 30 days) File Size: 1.55 KB File ID: #33811
image thumbnail

Data Convexity Check

by

 

17 Nov 2011 (Updated )

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

| Watch this File

File Information
Description

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.

MATLAB release MATLAB 7.6 (R2008a)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Updates
18 Nov 2011

Added a brief note to mention that this can also be used to check the concavity of data.

Contact us