Construction of monotone smoothing splines using a branch and bound method
(2020) In Master’s Theses in Mathematical Sciences FMAM05 20201Mathematics (Faculty of Engineering)
- Abstract
- The purpose of this report is to investigate a branch and bound algorithm designed to construct monotone smoothing splines. The splines are defined as the solution of a minimization problem, where one wants to find a curve with non-negative derivative everywhere, that fits a data set consisting of points in the plane, while also being sufficiently smooth. The report describes the theory necessary to understand the mathematical background of the algorithm. The theory shows existence and uniqueness of a minimizer and uses the Karush-Kuhn-Tucker (KKT) conditions for vector spaces to reduce the problem to a finite dimensional optimization problem. The report also shows some results that can be used to improve the algorithm and reduce the... (More)
- The purpose of this report is to investigate a branch and bound algorithm designed to construct monotone smoothing splines. The splines are defined as the solution of a minimization problem, where one wants to find a curve with non-negative derivative everywhere, that fits a data set consisting of points in the plane, while also being sufficiently smooth. The report describes the theory necessary to understand the mathematical background of the algorithm. The theory shows existence and uniqueness of a minimizer and uses the Karush-Kuhn-Tucker (KKT) conditions for vector spaces to reduce the problem to a finite dimensional optimization problem. The report also shows some results that can be used to improve the algorithm and reduce the search space from 2^n to 1.84^n, where n is the number of data points. In practice the running time is often faster, although it can depend on some parameters as well as the data set. (Less)
- Popular Abstract
- It is a common problem to fit a curve to data. When it is known that the function should be increasing, this could be done using monotone smoothing splines. This thesis investigates an algorithm for finding this curve. The algorithm seems to work well for most parts, although there are cases when it is very slow.
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/student-papers/record/9018210
- author
- Larsson, Malte LU
- supervisor
- organization
- alternative title
- Beräkning av monotona utjämnande splines med en branch and bound-algoritm
- course
- FMAM05 20201
- year
- 2020
- type
- H2 - Master's Degree (Two Years)
- subject
- keywords
- Monotone smoothing splines, optimization, Karush-Kuhn-Tucker conditions, curve fitting
- publication/series
- Master’s Theses in Mathematical Sciences
- report number
- LUTFMA-3418-2020
- ISSN
- 1404-6342
- other publication id
- 2020:E38
- language
- English
- id
- 9018210
- date added to LUP
- 2020-06-30 13:02:10
- date last changed
- 2020-06-30 13:02:10
@misc{9018210, abstract = {{The purpose of this report is to investigate a branch and bound algorithm designed to construct monotone smoothing splines. The splines are defined as the solution of a minimization problem, where one wants to find a curve with non-negative derivative everywhere, that fits a data set consisting of points in the plane, while also being sufficiently smooth. The report describes the theory necessary to understand the mathematical background of the algorithm. The theory shows existence and uniqueness of a minimizer and uses the Karush-Kuhn-Tucker (KKT) conditions for vector spaces to reduce the problem to a finite dimensional optimization problem. The report also shows some results that can be used to improve the algorithm and reduce the search space from 2^n to 1.84^n, where n is the number of data points. In practice the running time is often faster, although it can depend on some parameters as well as the data set.}}, author = {{Larsson, Malte}}, issn = {{1404-6342}}, language = {{eng}}, note = {{Student Paper}}, series = {{Master’s Theses in Mathematical Sciences}}, title = {{Construction of monotone smoothing splines using a branch and bound method}}, year = {{2020}}, }