On the convergence of a greedy algorithm for the solution of the problem for the construction of monotone regression

The paper presents greedy algorithms that use the Frank–Woolf-type approach for finding a sparse monotonic regression. The problem of finding monotonic regression arises in smoothing an empirical data, in problems of dynamic programming, mathematical statistics and in many other applied problems. The problem is to find a non-decreasing sequence of points with the lowest error of approximation to the given set of points on the plane. The problem of constructing monotonic regression can be formulated as a convex programming problem with linear constraints and is NP-hard problem. The paper also contains estimates of the rate of convergence for the presented greedy algorithms.