Convex piecewise-linear fitting

We consider the problem of fitting a convex piecewise-linear function, with some specified form, to given multi-dimensional data. Except for a few special cases, this problem is hard to solve exactly, so we focus on heuristic methods that find locally optimal fits. The method we describe, which is a...

Full description

Saved in:
Bibliographic Details
Published in:Optimization and engineering 2009-03, Vol.10 (1), p.1-17
Main Authors: Magnani, Alessandro, Boyd, Stephen P.
Format: Article
Language:English
Subjects:
Algorithms
Clustering
Control
Engineering
Environmental Management
Financial Engineering
Fittings
Heuristic methods
Mathematics
Mathematics and Statistics
Operations research
Operations Research/Decision Theory
Optimization
Studies
Systems Theory
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider the problem of fitting a convex piecewise-linear function, with some specified form, to given multi-dimensional data. Except for a few special cases, this problem is hard to solve exactly, so we focus on heuristic methods that find locally optimal fits. The method we describe, which is a variation on the K -means algorithm for clustering, seems to work well in practice, at least on data that can be fit well by a convex function. We focus on the simplest function form, a maximum of a fixed number of affine functions, and then show how the methods extend to a more general form.
ISSN:1389-4420
1573-2924
DOI:10.1007/s11081-008-9045-3