An algorithm for a singly constrained class of quadratic programs subject upper and lower bounds
type: Item
instance of: scholarly article
title: An algorithm for a singly constrained class of quadratic programs subject upper and lower bounds
zbMATH Open document ID: 0711.90061
DOI: 10.1007/BF01585748
author: Panos M. Pardalos
author: Nainan Kovoor
published in: Mathematical Programming. Series A. Series B
publication date: 1990-01-01T00:00:00Z
review text: 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.
reviewed by: Riho Lepp
Mathematics Subject Classification ID: 90C20
Mathematics Subject Classification ID: 90C25
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 90-08
Mathematics Subject Classification ID: 90C60
zbMATH DE Number: 4170648
zbMATH Keywords: linear-quadratic program
zbMATH Keywords: composed objective function
zbMATH Keywords: singly constrained quadratic program
zbMATH Keywords: piecewise linear monotone non-decreasing function
zbMATH Keywords: finite break-points
describes a project that uses: LINDO
MaRDI profile type: Publication
cites work: Q4091421
cites work: Time bounds for selection
cites work: An O(n) algorithm for quadratic knapsack problems
cites work: Quasi-Newton Updates with Bounds
cites work: Integer Programming Algorithms: A Framework and State-of-the-Art Survey
cites work: Validation of subgradient optimization
cites work: A polynomially bounded algorithm for a singly constrained quadratic program
cites work: Multipoint methods for separable nonlinear networks
cites work: Constrained global optimization: algorithms and applications
cites work: Methods for Global Concave Minimization: A Bibliographic Survey
cites work: Global minimization of large-scale constrained concave quadratic problems by separable programming
full work available at URL: https://doi.org/10.1007/bf01585748
OpenAlex ID: W2061211758
description: scientific article; zbMATH DE number 4170648