A dual active-set algorithm for regularized slope-constrained monotonic regression

In many problems, it is necessary to take into account monotonic relations. Monotonic (isotonic) Regression (MR) is often involved in solving such problems. The MR solutions are of a step-shaped form with a typical sharp change of values between adjacent steps. This, in some applications, is regarded as a disadvantage. We recently introduced a Smoothed MR (SMR) problem which is obtained from the MR by adding a regularizationpenalty term. The SMR is aimed at smoothing the aforementioned sharp change. Moreover, its solution has a far less pronounced step-structure, if at all available. The purpose of this paper is to further improve the SMR solution by getting rid of such a structure. This is achieved by introducing in the SMR a lowed bound on the slope. We call it Smoothed Slope-Constrained MR (SSCMR) problem. It is shown here how to reduce itto the SMR which is a convex quadratic optimization problem. The SPAV algorithm developed in our recent publications for solving the SMR problem is adapted here to solving the SSCMR problem. This algorithm belongs to the class of dual active-set algorithms. Although the complexity of the SPAV algorithm is O(n2), its running time was growing in our computational experiments almost linearly with n. We present numericalresults which illustrate the predictive performance quality of our approach. They also show that the SSCMR solution is free of the undesirable features of the MR and SMR solutions

Keywords:

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