A greedy algorithm for data sharpening and constraint handling

Moves data points to make an estimator (like a kernel density estimate) satisfy given constraints
Updated 10 May 2010

View License

This function was developed for nonparametric estimation problems where the estimate must satisfy some shape constraint. Our standard example of this is using a kernel density estimator, with the constraint that the estimate can have only one mode.

Let x be the observed data, and confun(x,...) be a function that checks whether a particular constraint is satisfied. Let y0 be some initial guess solution that satisfies the constraint.

y = improve(y0,x,confun) returns in y an "improved" solution--a set of data that are closer to x than y0, and still satisfy the constraint. This idea of moving the data points to improve an estimator or to satisfy constraints is known as data sharpening.

The function uses a greedy algorithm that sweeps repeatedly through the points, moving one at a time to be closer to their target x values until no more moves can be made without violating feasibility.

Also included is the function iteratedimprove( ), which allows the user to iteratively perturb the best solution and re-run improve( ). This tends to find better solutions in difficult problems.

This code was developed for data sharpening problems in shape-constrained density estimation, but it is basically a repair method for handling constraints (a means of making infeasible solutions into feasible ones). As such it could possibly be useful for other constrained estimation problems, or for other continuous constrained optimization problems.

This is a preliminary submission. The research of which this algorithm is a part is currently in process at a statistics journal. Once the work is accepted for publication our submission will be revised and expanded with more code and more information.

Cite As

Mark Wolters (2024). A greedy algorithm for data sharpening and constraint handling (https://www.mathworks.com/matlabcentral/fileexchange/27560-a-greedy-algorithm-for-data-sharpening-and-constraint-handling), MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R2007a
Compatible with any release
Platform Compatibility
Windows macOS Linux
Find more on Statistics and Machine Learning Toolbox in Help Center and MATLAB Answers

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
Version Published Release Notes

Fixed a typo in the Summary