An adaptive hybrid direction algorithm for convex box-QP problems with enhanced pre-solving

In this paper, we propose a new algorithm for solving quadratic programming problem with box constraints. The principle of the algorithm is to apply a preprocessing procedure to reduce the original problem. Then the resulting reduced problem will be solved by applying the adaptive method with a hybrid direction. A post-processing step (post-solving) is necessary to deduce the optimal solution of the original problem. In order to test the algorithm of the proposed method and to make sure of its effectiveness, a comparative study of the proposed method is made with active-set quadprog algorithm, the interior-point-convex quadprog algorithm of the MATLAB optimisation toolbox and the modified proportioning with reduced gradient projections algorithm (MPRGP). The obtained results show that the proposed algorithm presents good performances, it always performs better than the active set method and appears to be very competitive with the interior point method and the MPRGP algorithm, mainly for the problems having |bi| sufficiently large with many active variables at the optimal solution and for problems where A is generalised diagonally dominant. In these cases, the optimal solution is obtained only by the pre-solving procedure.