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 nonnegative 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 KarushKuhnTucker (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 nonnegative 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 KarushKuhnTucker (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/studentpapers/record/9018210
 author
 Larsson, Malte ^{LU}
 supervisor

 Sara Maad Sasane ^{LU}
 organization
 alternative title
 Beräkning av monotona utjämnande splines med en branch and boundalgoritm
 course
 FMAM05 20201
 year
 2020
 type
 H2  Master's Degree (Two Years)
 subject
 keywords
 Monotone smoothing splines, optimization, KarushKuhnTucker conditions, curve fitting
 publication/series
 Master’s Theses in Mathematical Sciences
 report number
 LUTFMA34182020
 ISSN
 14046342
 other publication id
 2020:E38
 language
 English
 id
 9018210
 date added to LUP
 20200630 13:02:10
 date last changed
 20200630 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 nonnegative 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 KarushKuhnTucker (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 = {14046342}, keyword = {Monotone smoothing splines,optimization,KarushKuhnTucker 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}, }