Computational enhancements in low-rank semidefinite programming

被引：22

作者：

Burer, S ^{[1
]}

Choi, C ^{[1
]}

机构：

[1] Univ Iowa, Iowa City, IA 52242 USA

来源：

OPTIMIZATION METHODS & SOFTWARE | 2006年 / 21卷 / 03期

基金：

美国国家科学基金会;

关键词：

semidefinite programming; low-rank matrices; vector programming; non-linear programming; numerical experiments;

D O I：

10.1080/10556780500286582

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We discuss computational enhancements for the low-rank semidefinite programming algorithm, including the extension to block semidefinite programs (SDPs), an exact linesearch procedure, and a dynamic rank reduction scheme. A truncated-Newton method is also introduced, and several preconditioning strategies are proposed. Numerical experiments illustrating these enhancements are provided on a wide class of test problems. In particular, the truncated-Newton variant is able to achieve high accuracy in modest amounts of time on maximum-cut-type SDPs.

引用

页码：493 / 512

页数：20

共 50 条

[21] Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices
Musco, Cameron
Woodruff, David P.
2017 IEEE 58TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2017, : 672 - 683
[22] SEMIDEFINITE REPRESENTATIONS OF GAUGE FUNCTIONS FOR STRUCTURED LOW-RANK MATRIX DECOMPOSITION
Chao, Hsiao-Han
Vandenberghe, Lieven
SIAM JOURNAL ON OPTIMIZATION, 2017, 27 (03) : 1362 - 1389
[23] Enhancing low-rank solutions in semidefinite relaxations of Boolean quadratic problems
Cerone, Vito
Fosson, Sophie M.
Regruto, Diego
IFAC PAPERSONLINE, 2020, 53 (02): : 1894 - 1899
[24] Low-rank structure in semidefinite programs derived from the KYP lemma
Liu, Zhang
Vandenberghe, Lieven
PROCEEDINGS OF THE 46TH IEEE CONFERENCE ON DECISION AND CONTROL, VOLS 1-14, 2007, : 2056 - 2063
[25] Low-Rank Positive Semidefinite Matrix Recovery From Corrupted Rank-One Measurements
Li, Yuanxin
Sun, Yue
Chi, Yuejie
IEEE TRANSACTIONS ON SIGNAL PROCESSING, 2017, 65 (02) : 397 - 408
[26] Efficient Low-Rank Stochastic Gradient Descent Methods for Solving Semidefinite Programs
Chen, Jianhui
Yang, Tianbao
Zhu, Shenghuo
ARTIFICIAL INTELLIGENCE AND STATISTICS, VOL 33, 2014, 33 : 122 - 130
[27] SOLVING PHASELIFT BY LOW-RANK RIEMANNIAN OPTIMIZATION METHODS FOR COMPLEX SEMIDEFINITE CONSTRAINTS
Huang, Wen
Gallivan, K. A.
Zhang, Xiangxiong
SIAM JOURNAL ON SCIENTIFIC COMPUTING, 2017, 39 (05): : B840 - B859
[28] A Low-Rank Rounding Heuristic for Semidefinite Relaxation of Hydro Unit Commitment Problems
Paredes, M.
Martins, L. S. A.
Soares, S.
2018 IEEE POWER & ENERGY SOCIETY GENERAL MEETING (PESGM), 2018,
[29] An equivalent nonlinear optimization model with triangular low-rank factorization for semidefinite programs
Yamakawa, Yuya
Ikegami, Tetsuya
Fukuda, Ellen H. H.
Yamashita, Nobuo
OPTIMIZATION METHODS & SOFTWARE, 2023, 38 (06): : 1296 - 1310
[30] Solving clustered low-rank semidefinite programs arising from polynomial optimization
Leijenhorst, Nando
de Laat, David
MATHEMATICAL PROGRAMMING COMPUTATION, 2024, 16 (03) : 503 - 534

← 1 2 3 4 5 →