Dual active-set algorithm for optimal 3-monotone regression

Abstract

The paper considers a shape-constrained optimization problem of constructing monotone regression which has gained much attention over the recent years. This paper presents the results of constructing the nonlinear regression with $3$-monotone constraints. Monotone regression of high orders can be applied in many fields, including non-parametric mathematical statistics and empirical data smoothing. In this paper, an iterative algorithm is proposed for constructing a sparse $3$-monotone regression, i.e. for finding a $3$-monotone vector with the lowest square error of approximation to a given (not necessarily $3$-monotone) vector. The problem can be written as a convex programming problem with linear constraints. It is proved that the proposed dual active-set algorithm has polynomial complexity and obtains the optimal solution.

Keywords

• dual algorithm
• isotonic regression
• monotone regression
• k-monotone regression
• convex regression