Optimization Online


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

Chang Xiaokai (15293183303***at***163.com)
Liu Sanyang (846188043***at***qq.com)
Bai Jianchao (xkchang***at***lut.cn)

Abstract: 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.

Keywords: Quadratic semidefinite programming, Nonnegative constraints, Alternating direction method of multipliers, Projection, Convergence analysis.

Category 1: Linear, Cone and Semidefinite Programming


Download: [PDF]

Entry Submitted: 12/14/2017
Entry Accepted: 12/14/2017
Entry Last Modified: 07/01/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society