QSDPNAL

QSDPNAL: a two-phase augmented Lagrangian method for convex quadratic semidefinite programming. In this paper, we present a two-phase augmented Lagrangian method, called QSDPNAL, for solving convex quadratic semidefinite programming (QSDP) problems with constraints consisting of a large number of linear equality and inequality constraints, a simple convex polyhedral set constraint, and a positive semidefinite cone constraint. A first order algorithm which relies on the inexact Schur complement based decomposition technique is developed in QSDPNAL-Phase I with the aim of solving a QSDP problem to moderate accuracy or using it to generate a reasonably good initial point for the second phase. In QSDPNAL-Phase II, we design an augmented Lagrangian method (ALM) wherein the inner subproblem in each iteration is solved via inexact semismooth Newton based algorithms. Simple and implementable stopping criteria are designed for the ALM. Moreover, under mild conditions, we are able to establish the rate of convergence of the proposed algorithm and prove the R-(super)linear convergence of the KKT residual. In the implementation of QSDPNAL, we also develop efficient techniques for solving large scale linear systems of equations under certain subspace constraints. More specifically, simpler and yet better conditioned linear systems are carefully designed to replace the original linear systems and novel shadow sequences are constructed to alleviate the numerical difficulties brought about by the crucial subspace constraints. Extensive numerical results for various large scale QSDPs show that our two-phase algorithm is highly efficient and robust in obtaining accurate solutions. The software reviewed as part of this submission was given the DOI (Digital Object Identifier) doi:10.5281/zenodo.1206980.


References in zbMATH (referenced in 26 articles , 1 standard article )

Showing results 1 to 20 of 26.
Sorted by year (citations)

1 2 next

  1. Chen, Liang; Li, Xudong; Sun, Defeng; Toh, Kim-Chuan: On the equivalence of inexact proximal ALM and ADMM for a class of convex composite programming (2021)
  2. Chen, Liang; Chang, Xiaokai; Liu, Sanyang: A three-operator splitting perspective of a three-block ADMM for convex quadratic semidefinite programming and beyond (2020)
  3. Chen, Xiaotong; Song, Xiaoliang; Chen, Zixuan; Yu, Bo: A multi-level ADMM algorithm for elliptic PDE-constrained optimization problems (2020)
  4. Ding, Chao; Sun, Defeng; Sun, Jie; Toh, Kim-Chuan: Spectral operators of matrices: semismoothness and characterizations of the generalized Jacobian (2020)
  5. Li, Xudong; Sun, Defeng; Toh, Kim-Chuan: On the efficient computation of a generalized Jacobian of the projector over the Birkhoff polytope (2020)
  6. Li, Xudong; Sun, Defeng; Toh, Kim-Chuan: An asymptotically superlinearly convergent semismooth Newton augmented Lagrangian method for linear programming (2020)
  7. Zhai, Fengzhen; Li, Qingna: A Euclidean distance matrix model for protein molecular conformation (2020)
  8. Zhang, Ning: A symmetric Gauss-Seidel based method for a class of multi-period mean-variance portfolio selection problems (2020)
  9. Zhao, Xin-Yuan; Chen, Liang: The linear and asymptotically superlinear convergence rates of the augmented Lagrangian method with a practical relative error criterion (2020)
  10. Ahmadi, Amir Ali; de Klerk, Etienne; Hall, Georgina: Polynomial norms (2019)
  11. Ahmadi, Amir Ali; Majumdar, Anirudha: DSOS and SDSOS optimization: more tractable alternatives to sum of squares and semidefinite optimization (2019)
  12. Chen, Zixuan; Song, Xiaoliang; Zhang, Xuping; Yu, Bo: A FE-ADMM algorithm for Lavrentiev-regularized state-constrained elliptic control problem (2019)
  13. Cui, Ying; Sun, Defeng; Toh, Kim-Chuan: On the R-superlinear convergence of the KKT residuals generated by the augmented Lagrangian method for convex composite conic programming (2019)
  14. Li, Xudong; Sun, Defeng; Toh, Kim-Chuan: A block symmetric Gauss-Seidel decomposition theorem for convex composite quadratic programming and its applications (2019)
  15. Wang, Shuangyue; Xiao, Yunhai; Jin, Zhengfen: An efficient algorithm for batch images alignment with adaptive rank-correction term (2019)
  16. Ding, Yanyun; Xiao, Yunhai: Symmetric Gauss-Seidel technique-based alternating direction methods of multipliers for transform invariant low-rank textures problem (2018)
  17. Li, Xudong; Sun, Defeng; Toh, Kim-Chuan: QSDPNAL: a two-phase augmented Lagrangian method for convex quadratic semidefinite programming (2018)
  18. Li, Xudong; Sun, Defeng; Toh, Kim-Chuan: A highly efficient semismooth Newton augmented Lagrangian method for solving lasso problems (2018)
  19. Song, Xiaoliang; Chen, Bo; Yu, Bo: An efficient duality-based approach for PDE-constrained sparse optimization (2018)
  20. Xiao, Yunhai; Chen, Liang; Li, Donghui: A generalized alternating direction method of multipliers with semi-proximal terms for convex composite conic programming (2018)

1 2 next