Advanced

Construction of monotone smoothing splines using a branch and bound method

Larsson, Malte LU (2020) In Master’s Theses in Mathematical Sciences FMAM05 20201
Mathematics (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:
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
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},
  keyword      = {Monotone smoothing splines,optimization,Karush-Kuhn-Tucker conditions,curve fitting},
  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},
}