An algorithm for a singly constrained class of quadratic programs subject upper and lower bounds (Q922953)

An O(n) algorithm for a singly constrained quadratic program with the objective function consisting of a sum of concave and convex parts, is presented. Such a minimization problem is equivalent to solve an equation with piecewise linear monotone non-decreasing function with finite break- points. The presented algorithm performs a binary search for locating a minimum interval for finding the solution of such an equation. The algorithm is described and test results are presented. The computational results show that the authors' approach is much faster than the original O(n log n) method for practical-sized problems.