An algorithm for a singly constrained class of quadratic programs subject upper and lower bounds
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.
piecewise linear monotone non-decreasing function
scientific article; zbMATH DE number 4170648
scientific article