Optimization Online


Regularized monotonic regression

Oleg Burdakov(oleg.burdakov***at***liu.se)
Oleg Sysoev(oleg.sysoev***at***liu.se)

Abstract: Monotonic (isotonic) Regression (MR) is a powerful tool used for solving a wide range of important applied problems. One of its features, which poses a limitation on its use in some areas, is that it produces a piecewise constant fitted response. For smoothing the fitted response, we introduce a regularization term in the MR formulated as a least distance problem with monotonicity constraints. The resulting Smoothed Monotonic Regrassion (SMR) is a convex quadratic optimization problem. We focus on the SMR, where the set of observations is completely (linearly) ordered. Our Smoothed Pool-Adjacent-Violators (SPAV) algorithm is designed for solving the SMR. It belongs to the class of dual active-set algorithms. We proved its finite convergence { to the optimal solution} in, at most, $n$ iterations, where $n$ is the problem size. One of its advantages is that the active set is progressively enlarging by including one or, typically, more constraints per iteration. This resulted in solving large-scale SMR test problems in a few iterations, whereas the size of that problems was prohibitively too large for the conventional quadratic optimization solvers. Although the complexity of the SPAV algorithm is $O(n^2)$, its running time was growing in our computational experiments almost linearly with $n$.

Keywords: Monotonic regression, regularization, quadratic penalty, convex quadratic optimization, dual active-set method, large-scale optimization.

Category 1: Applications -- Science and Engineering (Statistics )

Category 2: Nonlinear Optimization (Quadratic Programming )

Citation: Technical Report LiTH-MAT-R--2016/02--SE, Department of Mathematics, Linkoping University, 2016

Download: [PDF]

Entry Submitted: 06/30/2016
Entry Accepted: 06/30/2016
Entry Last Modified: 06/30/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society