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 条

[31] Low-Rank Riemannian Optimization on Positive Semidefinite Stochastic Matrices with Applications to Graph Clustering
Douik, Ahmed
Hassibi, Babak
INTERNATIONAL CONFERENCE ON MACHINE LEARNING, VOL 80, 2018, 80
[32] Forbidden minor characterizations for low-rank optimal solutions to semidefinite programs over the elliptope
Nagy, M. E.
Laurent, M.
Varvitsiotis, A.
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2014, 108 : 40 - 80
[33] OPTIMAL ESTIMATION AND COMPUTATIONAL LIMIT OF LOW-RANK GAUSSIAN MIXTURES
Lyu, Zhongyuan
Xia, Dong
ANNALS OF STATISTICS, 2023, 51 (02): : 646 - 667
[34] Dynamic Programming in Rank Space: Scaling Structured Inference with Low-Rank HMMs and PCFGs
Yang, Songlin
Liu, Wei
Tu, Kewei
NAACL 2022: THE 2022 CONFERENCE OF THE NORTH AMERICAN CHAPTER OF THE ASSOCIATION FOR COMPUTATIONAL LINGUISTICS: HUMAN LANGUAGE TECHNOLOGIES, 2022, : 4797 - 4809
[35] From low-rank retractions to dynamical low-rank approximation and back
Seguin, Axel
Ceruti, Gianluca
Kressner, Daniel
BIT NUMERICAL MATHEMATICS, 2024, 64 (03)
[36] Low-rank and sparse matrices fitting algorithm for low-rank representation
Zhao, Jianxi
Zhao, Lina
COMPUTERS & MATHEMATICS WITH APPLICATIONS, 2020, 79 (02) : 407 - 425
[37] Low-rank Parareal: a low-rank parallel-in-time integrator
Benjamin Carrel
Martin J. Gander
Bart Vandereycken
BIT Numerical Mathematics, 2023, 63
[38] Low-rank Parareal: a low-rank parallel-in-time integrator
Carrel, Benjamin
Gander, Martin J.
Vandereycken, Bart
BIT NUMERICAL MATHEMATICS, 2023, 63 (01)
[39] OUTLIER-ROBUST RECOVERY OF LOW-RANK POSITIVE SEMIDEFINITE MATRICES FROM MAGNITUDE MEASUREMENTS
Sun, Yue
Li, Yuanxin
Chi, Yuejie
2016 IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH AND SIGNAL PROCESSING PROCEEDINGS, 2016, : 4069 - 4073
[40] Sketching Low-Rank Matrices With a Shared Column Space by Convex Programming
Srinivasa, Rakshith S.
Kim, Seonho
Lee, Kiryung
IEEE JOURNAL ON SELECTED AREAS IN INFORMATION THEORY, 2023, 4 : 54 - 60

← 1 2 3 4 5 →