О сходимости жадного алгоритма для решения задачи построения монотонной регрессии

В статье представлены жадные алгоритмы, которые используют подход типа Франка–Вульфа для нахождения разреженной монотонной регрессии. Проблема нахождения монотонной регрессии возникает при сглаживании эмпирических данных, в задачах динамического программирования, математической статистике и во многих других прикладных задачах. Для решения данной задачи требуется найти неубывающую последовательность точек, имеющую наименьшую ошибку приближения к заданному множеству точек на плоскости. Задача построения монотонной регрессии может быть сформулирована в виде задачи выпуклого программирования с линейными ограничениями и имеет неполиномиальную сложность. В статье также находятся оценки скорости сходимости представленных жадных алгоритмов.