A projection algorithm based on KKT conditions for convex quadratic semidefinite programming with nonnegative constraints

The dual form of convex quadratic semidefinite programming (CQSDP) problem, with nonnegative constraints, is a 4-block separable convex optimization problem. It is known that,the directly extended 4-block alternating direction method of multipliers (ADMM4d) is very efficient to solve the dual, but its convergence is not guaranteed. In this paper, we reformulate the dual as a 3-block convex programming by introducing an extra variable, and apply the directly extended 3-block ADMM (ADMM3d) to this reformulation. By using the solution of the subproblems from ADMM3d, we show that the KKT system of the CQSDP and its dual is equivalent to an equation system, having two projection operators on the positive semidefinite and nonnegative matrix cones. Based on the equation system, we propose a projection method to solve the 4-block dual. In fact, the proposed method can be obtained by modifying ADMM3d with unit step-length, but does not have to work out the subproblem with the primal variable at each iteration, compared with the existing ADMM methods. Satisfying a condition on the penalty parameter, the convergence of the proposed method to a KKT point is proved by using a fixed-point argument and the non-expansion of the projection operators. Numerical experiments on the various classes of CQSDP problems show that, our proposed algorithm performs better than ADMM3d for the reformulation, and comparably with ADMM4d.

Article

Download

View A projection algorithm based on KKT conditions for convex quadratic semidefinite programming with nonnegative constraints