Dipartimento di Ingegneria informatica, automatica e gestionale

In this work, we consider the relevant class of Standard Quadratic Programming problems and we propose a simple and quick decomposition algorithm, which sequentially updates, at each iteration, two variables chosen by a suitable selection rule. The main features of the algorithm are the following: (1) the two variables are updated by solving a subproblem that, although nonconvex, can be analytically solved; (2) the adopted selection rule guarantees convergence towards stationary points of the problem. Then, the proposed Sequential Minimal Optimization algorithm, which optimizes the smallest possible sub-problem at each step, can be used as efficient local solver within a global optimization strategy. We performed extensive computational experiments and the obtained results show that the proposed decomposition algorithm, equipped with a simple multi-start strategy, is a valuable alternative to the state-of-the-art algorithms for Standard Quadratic Optimization Problems.