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 条

[41] An exact penalty method for semidefinite-box-constrained low-rank matrix optimization problems
Liu, Tianxiang
Lu, Zhaosong
Chen, Xiaojun
Dai, Yu-Hong
IMA JOURNAL OF NUMERICAL ANALYSIS, 2020, 40 (01) : 563 - 586
[42] Tight Certification of Adversarially Trained Neural Networks via Nonconvex Low-Rank Semidefinite Relaxations
Chiu, Hong-Ming
Zhang, Richard Y.
INTERNATIONAL CONFERENCE ON MACHINE LEARNING, VOL 202, 2023, 202
[43] Modified Interior-Point Method for Large-and-Sparse Low-Rank Semidefinite Programs
Zhang, Richard Y.
Lavaei, Javad
2017 IEEE 56TH ANNUAL CONFERENCE ON DECISION AND CONTROL (CDC), 2017,
[44] Low-Rank Transformer for High-Resolution Hyperspectral Computational Imaging
Liu, Yuanye
Dian, Renwei
Li, Shutao
INTERNATIONAL JOURNAL OF COMPUTER VISION, 2025, 133 (02) : 809 - 824
[45] Low-rank dynamics
Lubich, Christian
Lecture Notes in Computational Science and Engineering, 2014, 102 : 381 - 396
[46] A Unified Computational and Statistical Framework for Nonconvex Low-Rank Matrix Estimation
Wang, Lingxiao
Zhang, Xiao
Gu, Quanquan
ARTIFICIAL INTELLIGENCE AND STATISTICS, VOL 54, 2017, 54 : 981 - 990
[47] Some structural properties of low-rank matrices related to computational complexity
Codenotti, B
Pudlák, P
Resta, G
THEORETICAL COMPUTER SCIENCE, 2000, 235 (01) : 89 - 107
[48] REDUCED BASIS METHODS: FROM LOW-RANK MATRICES TO LOW-RANK TENSORS
Ballani, Jonas
Kressner, Daniel
SIAM JOURNAL ON SCIENTIFIC COMPUTING, 2016, 38 (04): : A2045 - A2067
[49] LOW-RANK PHYSICAL MODEL RECOVERY FROM LOW-RANK SIGNAL APPROXIMATION
Hayes, Charles Ethan
McClellan, James H.
Scott, Waymond R., Jr.
2017 IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH AND SIGNAL PROCESSING (ICASSP), 2017, : 3131 - 3135
[50] Low-Rank Tensor Completion Method for Implicitly Low-Rank Visual Data
Ji, Teng-Yu
Zhao, Xi-Le
Sun, Dong-Lin
IEEE SIGNAL PROCESSING LETTERS, 2022, 29 : 1162 - 1166

← 1 2 3 4 5 →