AN ALGORITHM FOR A SINGLY CONSTRAINED CLASS OF QUADRATIC PROGRAMS SUBJECT TO UPPER AND LOWER BOUNDS

被引：119

作者：

PARDALOS, PM

KOVOOR, N

机构：

[1] Computer Science Department, The Pennsylvania State University, University Park, 16802, PA

来源：

MATHEMATICAL PROGRAMMING | 1990年 / 46卷 / 03期

关键词：

Global optimization; quadratic programming; separable programming;

D O I：

10.1007/BF01585748

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

This paper gives an O(n) algorithm for a singly constrained convex quadratic program using binary search to solve the Kuhn-Tucker system. Computational results indicate that a randomized version of this algorithm runs in expected linear time and is suitable for practical applications. For the nonconvex case an ε-approximate algorithm is proposed which is based on convex and piecewise linear approximations of the objective function. © 1990 North-Holland.

引用

页码：321 / 328

页数：8

共 13 条

[1]

Aho A. V., 1974, DESIGN ANAL COMPUTER

[2]

BLUM M, 1972, J COMPUT SYST SCI, V7, P448

[3] AN O(N) ALGORITHM FOR QUADRATIC KNAPSACK-PROBLEMS [J].