An Active-Set-Based Recursive Approach for Solving Convex Isotonic Regression with Generalized Order Restrictions

Xuyu Chen (), Xudong Li and Yangfeng Su ()
Additional contact information
Xuyu Chen: School of Mathematical Sciences, Fudan University, Shanghai 200433, P. R. China
Xudong Li: School of Data Science, Fudan University, Shanghai 200433, P. R. China
Yangfeng Su: School of Mathematical Sciences, Fudan University, Shanghai 200433, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2024, vol. 41, issue 03, 1-27

Abstract: This paper studies the convex isotonic regression with generalized order restrictions induced by a directed tree. The proposed model covers various intriguing optimization problems with shape or order restrictions, including the generalized nearly isotonic optimization and the total variation on a tree. Inspired by the success of the pool-adjacent-violator algorithm and its active-set interpretation, we propose an active-set-based recursive approach for solving the underlying model. Unlike the brute-force approach that traverses an exponential number of possible active-set combinations, our algorithm has a polynomial time computational complexity under mild assumptions.

Keywords: Active set methods; convex isotonic regression; generalized order restrictions (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595923500252
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:41:y:2024:i:03:n:s0217595923500252

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595923500252

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().