Minimization of a Concave Quadratic Function Subject to Box Constraints

• Type: Article in International Scientific Journal
• Date: 1994

Authors

Ana Maria Faustino (Author) FEUP; J. Júdice (Author) Other

Journal

Title: Investigación Operativa : Latin-Iberian-American Journal on Operations Research

Vol. 4 No. 1 - Abril

Pages: 49-68

ISSN: 1014-8364

Publisher: ALIO - Latin-Iberian-American Association of Operations Research

Scientific classification

FOS: Natural sciences > Mathematics

Other information

Resumo (PT): We introduce a finite algorithm (MINBCQP) for finding a stationary point of a concave quadratic programming problem subject to box constraint (BCQP).This algorithm can move from one stationary point into another one with lower objective function value, it is also able to fix some variables into one of the bounds. Because of its first property, the algorithm finds in general an approximate optimal solution ttat is in many cases a global minimum of the BCQP. The second feature reduces (sometimes dramatically) the size of the BCQP to be solved alter the application of the algorithm MINBCQP. It is known that a BCQP with a nonpositive matrix can be solved in polynomial-time by exploring its reduction into a minimum-cut problem. In this paper we show that the algorithm MlNBCQP is quite efficient to deal with this type of problems. We also propose a hybrid technique for finding a global minimum of a BCQP. In this scheme, the algorithm MINBCQP is first applied to fix some variables to one of the bounds and then the BCQP associated with the free variables is solved by the minimum cut approach. Computational experience with large-scale BCQPs shows that this hybrid procedure is quite suitable and performs better than other alternative techniques for this type of BCQPs.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 20