Minimization of a concave quadratic function subject to box constraints

The authors 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 that is in many cases a global minimum of the BCQP. The second feature reduces (sometimes dramatically) the size of the BCQP to be solved after 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 the authors show that the algorithm MINBCQP is quite efficient to deal with this type of problems. They 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 perfroms better than other alternative techniques, for this type of BCQPs.