![]() |
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
We consider the quadratic program with bound constraints. This problem setting is of interesting by itself, since it has numerous applications, and also because symmetric linear complementarity problems and quadratic programs with strongly convex objective functions and general linear constraints can be reduced to this problem setting. Earlier it was proposed to employ a semismooth Newton method to primal-dual optimality systems of general quadratic programs, without any globalization strategies. The numerical results demonstrate the extraordinary efficiency of this approach for strongly convex quadratic programs with general linear constraints provided that the number of constraints does not exceed the number of variables. On the other hand, if the number of constraints is greater than the number of variables, then this primal-dual approach usually fails. Therefore, we propose a different (completely primal) way of using a semismooth Newton method for problem: in the case of positive semidefinite H, problem (1) is replaced by equivalent mixed complementarity problem, which, in its turn, is replaced by the equivalent non-smooth system of equation. Thelatter is solved by the semismooth Newton method. In order to obtain a fully justified finite global algorithm, we propose to combine the semismooth Newton method with a certain traditional finite method for problem (1). This traditional method may be one of the active-set methods designed for general quadratic programs, or certain versions of the projected gradient method designed specially for problems with bound constraints (the latter approach is more efficient for such problems). The numerical results clearly demonstrate that the semismooth Newton method is advantageous for dense strongly convex problems and convex problems with matrices having low rank deficiencies. Unfortunately, the robustness and efficiency of the semismooth Newton method significantly degrade for convex problems with having a higher rank deficiency. This can already be seen for . The method becomes useless as is decreased further. The same is true of non-convex problems.