Minimization of a Concave Quadratic Function Subject to Box Constraints

• Tipo: Artigo em Revista Científica Internacional
• Data: 1994

Autores

Ana Maria Faustino (Autor) FEUP; J. Júdice (Autor) Outra

Revista

Título: Investigación Operativa : Latin-Iberian-American Journal on Operations Research

Vol. 4 Nº 1 - Abril

Páginas: 49-68

ISSN: 1014-8364

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

Classificação Científica

FOS: Ciências exactas e naturais > Matemática

Outras Informações

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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 20