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 条
  • [1] Low-rank quadratic semidefinite programming
    Yuan, Ganzhao
    Zhang, Zhenjie
    Ghanem, Bernard
    Hao, Zhifeng
    NEUROCOMPUTING, 2013, 106 : 51 - 60
  • [2] Low-rank exploitation in semidefinite programming for control
    Falkeborn, Rikard
    Lofberg, Johan
    Hansson, Anders
    INTERNATIONAL JOURNAL OF CONTROL, 2011, 84 (12) : 1975 - 1982
  • [3] Local Minima and Convergence in Low-Rank Semidefinite Programming
    Samuel Burer
    Renato D.C. Monteiro
    Mathematical Programming, 2005, 103 : 427 - 444
  • [4] Local minima and convergence in low-rank semidefinite programming
    Burer, S
    Monteiro, RDC
    MATHEMATICAL PROGRAMMING, 2005, 103 (03) : 427 - 444
  • [5] Finding graph embeddings by incremental low-rank semidefinite programming
    Pulkkinen, Seppo
    OPTIMIZATION METHODS & SOFTWARE, 2015, 30 (05): : 1050 - 1076
  • [6] A DECOMPOSITION AUGMENTED LAGRANGIAN METHOD FOR LOW-RANK SEMIDEFINITE PROGRAMMING
    Wang, Yifei
    Deng, Kangkang
    Liu, Haoyang
    Wen, Zaiwen
    SIAM JOURNAL ON OPTIMIZATION, 2023, 33 (03) : 1361 - 1390
  • [7] Efficient Low-Rank Semidefinite Programming With Robust Loss Functions
    Yao, Quanming
    Yang, Hansi
    Hu, En-Liang
    Kwok, James T.
    IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 2022, 44 (10) : 6153 - 6168
  • [8] Low-Rank Semidefinite Programming for the MAX2SAT Problem
    Wang, Po-Wei
    Kolter, J. Zico
    THIRTY-THIRD AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE / THIRTY-FIRST INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE CONFERENCE / NINTH AAAI SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE, 2019, : 1641 - 1649
  • [9] Exploiting low-rank structure in semidefinite programming by approximate operator splitting
    Souto, Mario
    Garcia, Joaquim D.
    Veiga, Alvaro
    OPTIMIZATION, 2022, 71 (01) : 117 - 144
  • [10] Loraine - an interior-point solver for low-rank semidefinite programming
    Habibi, Soodeh
    Kocvara, Michal
    Stingl, Michael
    OPTIMIZATION METHODS & SOFTWARE, 2024, 39 (06): : 1185 - 1215
12345