A Simplex Algorithm for the Local Minimization of a Box-Constrained Concave Quadratic Program

In this work, we extend the simplex algorithm of linear programming for finding a local minimum of a concave quadratic function subject to box constraints. In order to test the performance of the proposed algorithm, we have developed an implementation with MATLAB. The simplex algorithm is tested on a set of 5 box-constrained QP test instances corresponding to a mathematical model arising a statistical physics application and 48 test problems taken from the CUTEr library. The obtained numerical results are very encouraging. Indeed, the local minimizer obtained with the simplex algorithm is global for the majority of the considered test problems.