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) https://doi.org/10.5281/zenodo.1206980.

1. In this case, the optimal solution set to (P) is necessarily a singleton though (D) may have multiple solutions.

2. https://www.rmicri.org.

Authors and Affiliations

1. Department of Operations Research and Financial Engineering, Princeton University, Sherrerd Hall, Princeton, NJ, 08544, USA

   Xudong Li

2. Department of Applied Mathematics, The Hong Kong Polytechnic University, Hung Hom, Hong Kong

   Defeng Sun

3. Department of Mathematics, and Institute of Operations Research and Analytics, National University of Singapore, 10 Lower Kent Ridge Road, Singapore, 119076, Singapore

   Kim-Chuan Toh

Corresponding author

Correspondence to Xudong Li.

An earlier version of this paper was made available in arXiv as arXiv:1512.08872. The software that was reviewed as part of this submission has been issued the Digital Object Identifier https://doi.org/10.5281/zenodo.1206980.

D. Sun: On leave from Department of Mathematics, National University of Singapore. This author’s research is partially supported by a start-up research grant from the Hong Kong Polytechnic University.

K.-C. Toh: This author’s research is supported in part by the Ministry of Education, Singapore, Academic Research Fund under Grant R-146-000-256-114.

Appendix

Along with the paper, we provide a Matlab implementation of our algorithm. The software package has been issued the Digital Object Identifier https://doi.org/10.5281/zenodo.1206980. Here, as a short users’ guide, we present some general description of the structure of our software.

Installation Qsdpnal is a Matlab software package developed under Matlab version 8.0 or above. It includes some C subroutines written to carry out certain operations for which Matlab is not efficient at. These subroutines are called within Matlab via the Mex interface. The user can simply follow the steps below to install Qsdpnal within Matlab:

(a):

unzip QSDPNAL+v0.1.zip;

(b):

run Matlab in the directory QSDPNAL+v0.1;

After that, to see whether you have installed Qsdpnal correctly, try the following steps:

In the above, startup.m sets up the paths for Qsdpnal in Matlab and qsdpdemo.m is a demo file illustrating how to solve a QSDP problem (31) in Qsdpnal.

Copyright Qsdpnal: A Matlab software for convex quadratic semidefinite programming with inequality, equality and bound constraints, is copyrighted in 2016 by Xudong Li, Defeng Sun and Kim-Chuan Toh. The software Qsdpnal is distributed under the GNU General Public License 2.0. You can redistribute it and/or modify it under the terms of the GNU General Public License 2.0 as published by the Free Software Foundation Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. For commercial applications that may be incompatible with this license, please contact the authors to discuss alternatives. This software is distributed in the hope that it will be useful, but without any warranty; without even the implied warranty of merchantability or fitness for a particular purpose. See the GNU General Public License for more details.

Main function and data structure Qsdpnal is an extension of the solvers Sdpnal [34] and Sdpnal+ [33]. The internal implementation of Qsdpnal thus follows in part the data structures and design framework of the above two solvers. A casual user does not need to understand the internal implementation of Qsdpnal.

In the Qsdpnal solver, the main routine is qsdpnal.m, whose calling syntax is as follows:

Input arguments

• blk: a cell array describing the conic structure of the QSDP problem.

• Q, AEt, bE, C, AIt, bI: data of QSDP problem (31). If the linear map \(\mathcal{A}_I\) is not present, one can set AIt = [], bI = [].

• options: a structure array of parameters.

Output arguments The names chosen for the output arguments explain their contents. The argument X is a solution to problem (31) up to the desired accuracy tolerance. The argument info is a structure array which records various performance measures of the solver. For example

correspond to the measures \(\eta _Z\), \(\eta _{I_1}\), \(\eta _{I_2}\) and \(\eta _{I_3}\) defined in (35), respectively. The argument runhist is a structure array which records the history of various performance measures during the course of running qsdpnal. For example,

record the primal and dual objective values, primal and dual infeasibilities at each iteration, respectively.

Data structure The format of the input data in Qsdpnal is similar to those in Sdpnal [34] and Sdpnal+ [33]. For problem (31), we set

where \({\bar{n}} = n(n+1)/2\) and the self-adjoint linear operator \(\mathcal{Q}\) is stored as a function handle which takes any matrix \(X\in \mathcal{S}^n\) as input and output the matrix \(\mathcal{Q}X\in \mathcal{S}^n\). For the sake of computational efficiency, following the same approach used in Sdpnal [34] and Sdpnal+ [33], we store the linear map \(\mathcal{A}_E\) in vectorized form as a single \({\bar{n}}\times m_E\) matrix AEt. The same procedure also applies to the linear operator \(\mathcal{A}_I\), i.e., AIt is stored in the same format as AEt. The data of the simple nonempty closed convex polyhedral set \(\mathcal{K}\) is encoded in the argument options. For example, if \(\mathcal{K}=\{ X\in \mathcal{S}^n\mid L\le X \le U\}\) with \(L,U\in S^n\) being given matrices, we set

The default is options.L = [], options.U = []. If \(\mathcal{K}= \{X\in \mathcal{S}^n\mid X\ge 0\}\), then one can simply set options.nonnegative = 1.

Apart from the information of \(\mathcal{K}\), various other parameters used in our solver qsdpnal.m are set in the structure array options. We list here the important parameters which the user is likely to reset.

• options.stoptol: accuracy tolerance to terminate the algorithm, default is \(10^{-6}\).

• options.maxiter: maximum number of iterations allowed, default is 5000.

• options.sGSstoptol: accuracy tolerance to use for Qsdpnal-Phase I (SCB_qsdp.m) when generating a starting point for the algorithm in the second phase of qsdpnal.m (default = \(10^{-4}\)).

• options.sGSmaxiter: maximum number of Qsdpnal-Phase I iterations allowed for generating a starting point (default = 1500).

Examples Next, we present two examples of using Qsdpnal for solving two QSDP problems in detail. The segment below illustrates how one can solve the instance be250.2 of QSDP-BIQ problems.

The next example is using qsdpnal.m to solve the instance chr15c of QSDP-QAP problems.

In the above codes, randQXfun generates the self-adjoint positive semidefinite linear operator \(\mathcal{Q}\) in (37) with randomly generated matrices \(A,B\in \mathcal{S}^n_+\).

Reprints and permissions