A Fast Scaling Algorithm for Minimizing Separable Convex Functions Subject to Chain Constraints

Ravindra K. Ahuja () and James B. Orlin ()
Additional contact information
Ravindra K. Ahuja: Industrial and Systems Engineering Department, University of Florida, Gainesville, Florida 32611
James B. Orlin: Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

Operations Research, 2001, vol. 49, issue 5, 784-789

Abstract: We consider the problem of minimizing (Sigma) j(in)N C j (x j ), subject to the following chain constraints x 1 (le) x 2 (le) x 3 (le) ... (le) x n , where C j (x j ) is a convex function of x j for each j (in) N = {1,2, ... ,n}. This problem is a generalization of the isotonic regression problems with complete order, an important class of problems in regression analysis that has been examined extensively in the literature. We refer to this problem as the generalized isotonic regression problem . In this paper, we focus on developing a fast-scaling algorithm to obtain an integer solution of the generalized isotonic regression problem. Let U denote the difference between an upper bound on an optimal value of x n and a lower bound on an optimal value of x 1 . Under the assumption that the evaluation of any function C j (x j ) takes O (1) time, we show that the generalized isotonic regression problem can be solved in O (n log U ) time. This improves by a factor of n the previous best running time of O (n 2 log U ) to solve the same problem. In addition, when our algorithm is specialized to the isotonic median regression problem (where C j (x j ) = c j |x j -a j |) for specified values of c j s and a j s , the algorithm obtains a real-valued optimal solution in O (n log n ) time. This time bound matches the best available time bound to solve the isotonic median regression problem, but our algorithm uses simpler data structures and may be easier to implement.

Keywords: Statistics; data analysis: isotonic regression problem; Programming; nonlinear: convex programming subject to chain constraints (search for similar items in EconPapers)
Date: 2001
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (11)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.49.5.784.10601 (application/pdf)

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:inm:oropre:v:49:y:2001:i:5:p:784-789

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().