A dynamic programming approach for generalized nearly isotonic optimization

DOI10.1007/S12532-022-00229-XMaRDI QIDQ6102862zbMATH OpenOpenAlexFDO

Authors Zhensheng Yu, Xuyu Chen, Xudong Li

Publication date 23 June 2023

Published in Mathematical Programming Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2011.03305

zbMATH Keywords

dynamic programminggeneralized nearly isotonic optimizationshape constrained statistical regression

Mathematics Subject Classification ID

Convex programming (90C25) Large-scale problems in mathematical programming (90C06) Dynamic programming (90C39)

Abstract: Shape restricted statistical estimation problems have been extensively studied, with many important practical applications in signal processing, bioinformatics, and machine learning. In this paper, we propose and study a generalized nearly isotonic optimization (GNIO) model, which recovers, as special cases, many classic problems in shape constrained statistical regression, such as isotonic regression, nearly isotonic regression and unimodal regression problems. We develop an efficient and easy-to-implement dynamic programming algorithm for solving the proposed model whose recursion nature is carefully uncovered and exploited. For special $el{l}_2$-GNIO problems, implementation details and the optimal $calO(n)$ running time analysis of our algorithm are discussed. Numerical experiments, including the comparisons among our approach, the powerful commercial solver Gurobi, and existing fast algorithms for solving $el{l}_1$-GNIO and $el{l}_2$-GNIO problems, on both simulated and real data sets, are presented to demonstrate the high efficiency and robustness of our proposed algorithm in solving large scale GNIO problems.

Recommendations

• An O(n^2) algorithm for isotonic regression
• A dual active set algorithm for optimal sparse convex regression
• Estimating piecewise monotone signals
• Isotonic regression in general dimensions

Cites work

• scientific article; zbMATH DE number 3390139 (Why is no real title available?)
• A Fast Scaling Algorithm for Minimizing Separable Convex Functions Subject to Chain Constraints
• A TEST OF HOMOGENEITY FOR ORDERED ALTERNATIVES
• A TEST OF HOMOGENEITY FOR ORDERED ALTERNATIVES. II
• A faster algorithm solving a generalization of isotonic median regression and a class of fused Lasso problems
• Active set algorithms for isotonic regression; a unifying framework
• An Empirical Distribution Function for Sampling with Incomplete Information
• An algorithm for isotonic regression with arbitrary convex distance function
• An efficient algorithm for image segmentation, Markov random fields and related problems
• Constrained Statistical Inference
• Convex Analysis
• De-noising by soft-thresholding
• Ideal spatial adaptation by wavelet shrinkage
• Introduction to algorithms.
• Locally monotonic regression
• Maximum Likelihood Estimates of Monotone Parameters
• Minimizing Separable Convex Functions Subject to Simple Chain Constraints
• Modular proximal optimization for multidimensional total-variation regularization
• Pathwise coordinate optimization
• Unimodal regression via prefix isotonic regression

Cited in

(1)

• An active-set-based recursive approach for solving convex isotonic regression with generalized order restrictions

This page was built for publication: A dynamic programming approach for generalized nearly isotonic optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6102862)