This paper introduces an efficient algorithm for computing the best approximation of a given matrix onto the intersection of linear equalities, inequalities, and the doubly nonnegative cone (the cone of all positive semidefinite matrices whose elements are nonnegative). In contrast to directly applying the block coordinate descent type methods, we propose an inexact accelerated (two-) block coordinate descent algorithm to tackle the four-block unconstrained nonsmooth dual program. The proposed algorithm hinges on the superlinearly convergent semismooth Newton method to solve each of the two subproblems generated from the (two-)block coordinate descent, which have no closed form solutions due to the merger of the original four blocks of variables. The O(1/k2) iteration complexity of the proposed algorithm is established. Extensive numerical results over various large scale semidefinite programming instances from relaxations of combinatorial problems demonstrate the effectiveness of the proposed algorithm.
|Original language||English (US)|
|Number of pages||29|
|Journal||SIAM Journal on Optimization|
|State||Published - 2019|
Bibliographical noteFunding Information:
∗Received by the editors March 14, 2018; accepted for publication (in revised form) September 4, 2019; published electronically October 31, 2019. https://doi.org/10.1137/18M1175562 Funding: The second author’s research is partially supported by a start-up research grant from the Hong Kong Polytechnic University. The third author’s research is partially supported by the Ministry of Education of Singapore through ARF grant R-146-000-257-112. †Department of Industrial and Systems Engineering, University of Southern California, Los Angeles, CA 90089-0193 (firstname.lastname@example.org). ‡Department of Applied Mathematics, Hong Kong Polytechnic University, Hong Kong (email@example.com). §Department of Mathematics, National University of Singapore, Singapore, 119076 (mattohkc@ nus.edu.sg).
Copyright © by SIAM.
- Doubly nonnegative cone
- Semidefinite programming
- Semismooth Newton