Computing the best approximation over the intersection of a polyhedral set and the doubly nonnegative cone

Ying Cui; Defeng Sun; Kim Chuan Toh

doi:10.1137/18M1175562

Computing the best approximation over the intersection of a polyhedral set and the doubly nonnegative cone

Ying Cui, Defeng Sun, Kim Chuan Toh

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

Abstract

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/k²) 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)
Pages (from-to)	2785-2813
Number of pages	29
Journal	SIAM Journal on Optimization
Volume	29
Issue number	4
DOIs	https://doi.org/10.1137/18M1175562
State	Published - 2019
Externally published	Yes

Bibliographical note

Funding 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 (yingcui@usc.edu). ‡Department of Applied Mathematics, Hong Kong Polytechnic University, Hong Kong (defeng.sun@polyu.edu.hk). §Department of Mathematics, National University of Singapore, Singapore, 119076 (mattohkc@ nus.edu.sg).

Publisher Copyright:
Copyright © by SIAM.

Keywords

Acceleration
Complexity
Doubly nonnegative cone
Semidefinite programming
Semismooth Newton

Publisher link

10.1137/18M1175562

Find It

Find It at U of M Libraries

Cite this

@article{0a5d0ca519ac46878fb4d3db3d2ee307,

title = "Computing the best approximation over the intersection of a polyhedral set and the doubly nonnegative cone",

abstract = "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.",

keywords = "Acceleration, Complexity, Doubly nonnegative cone, Semidefinite programming, Semismooth Newton",

author = "Ying Cui and Defeng Sun and Toh, {Kim Chuan}",

note = "Funding 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{\textquoteright}s research is partially supported by a start-up research grant from the Hong Kong Polytechnic University. The third author{\textquoteright}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 (yingcui@usc.edu). ‡Department of Applied Mathematics, Hong Kong Polytechnic University, Hong Kong (defeng.sun@polyu.edu.hk). §Department of Mathematics, National University of Singapore, Singapore, 119076 (mattohkc@ nus.edu.sg). Publisher Copyright: Copyright {\textcopyright} by SIAM.",

year = "2019",

doi = "10.1137/18M1175562",

language = "English (US)",

volume = "29",

pages = "2785--2813",

journal = "SIAM Journal on Optimization",

issn = "1052-6234",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "4",

}

TY - JOUR

T1 - Computing the best approximation over the intersection of a polyhedral set and the doubly nonnegative cone

AU - Cui, Ying

AU - Sun, Defeng

AU - Toh, Kim Chuan

N1 - Funding 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 (yingcui@usc.edu). ‡Department of Applied Mathematics, Hong Kong Polytechnic University, Hong Kong (defeng.sun@polyu.edu.hk). §Department of Mathematics, National University of Singapore, Singapore, 119076 (mattohkc@ nus.edu.sg). Publisher Copyright: Copyright © by SIAM.

PY - 2019

Y1 - 2019

N2 - 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.

AB - 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.

KW - Acceleration

KW - Complexity

KW - Doubly nonnegative cone

KW - Semidefinite programming

KW - Semismooth Newton

UR - http://www.scopus.com/inward/record.url?scp=85076158275&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85076158275&partnerID=8YFLogxK

U2 - 10.1137/18M1175562

DO - 10.1137/18M1175562

M3 - Article

AN - SCOPUS:85076158275

SN - 1052-6234

VL - 29

SP - 2785

EP - 2813

JO - SIAM Journal on Optimization

JF - SIAM Journal on Optimization

IS - 4

ER -

Computing the best approximation over the intersection of a polyhedral set and the doubly nonnegative cone

Abstract

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this