Dual active-set algorithm for optimal 3-monotone regression

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