Benchmarks¶

To assess the performance of our preliminary implementation of SMCP, we have conducted a series of numerical experiments.

SDP solvers¶

The following interior-point solvers were used in our experiments:

Method M1 (SMCP 0.3a, feasible start solver with kktsolver=’chol’)
Method M1c (SMCP 0.3a, feasible start solver with kktsolver=’chol’ and solvers.options[‘cholmod’]=True)
Method M2 (SMCP 0.3a, feasible start solver with kktsolver=’qr’)
CSDP 6.0.1
DSDP 5.8
SDPA 7.3.1
SDPA-C 6.2.1 (binary dist.)
SDPT3 4.0b (64-bit Matlab)
SeDuMi 1.2 (64-bit Matlab)

Error measures¶

We report DIMACS error measures when available. The six error measures are defined as:

\[\begin{split}\epsilon_1(X,y,S) &= \frac{\|\mathcal{A}(X) - b\|_2}{1+\|b\|_\infty} \\ \epsilon_2(X,y,S) &= \max\left\{0,\frac{-\lambda_{\min}(X)}{1+\|b\|_\infty } \right\} \\ \epsilon_3(X,y,S) &= \frac{\|\mathcal{A}^{\rm adj}(y)+S-C \|_F}{1+\|C\|_{\max}} \\ \epsilon_4(X,y,S) &= \max\left\{0, \frac{-\lambda_{\min}(S)}{1+\|C\|_{\max}} \right\} \\ \epsilon_5(X,y,S) &= \frac{C \bullet X - b^Ty}{1+|C\bullet X|+|b^Ty|} \\ \epsilon_6(X,y,S) &= \frac{S\bullet X}{1+|C\bullet X|+|b^Ty|}\end{split}\]

Here \(\|C\|_{\max} = \max_{i,j} |C_{ij}|\), and \(C\bullet X = \mathbf{tr}(C^TX)\).

Note that \(\epsilon_2(X,y,S)=0\) and \(\epsilon_4(X,y,S)=0\) since all iterates \((X,y,S)\) satisfy \(X \in \mathbf{S}_{V,c++}^n\) and \(S \in \mathbf{S}_{V,++}^n\).

Experimental setup¶

The following experiments were conducted on a desktop computer with an Intel Core 2 Quad Q6600 CPU (2.4 GHz), 4 GB of RAM, and running Ubuntu 9.10 (64 bit).

The problem instances used in the experiments are available for download here and the SDPLIB problems are available here.

We use the least-norm solution to the set of equations \(A_i \bullet X, i=1,\ldots,m,\) as starting point when it is strictly feasible, and otherwise we solve the phase I problem

\[\begin{split}\begin{array}{ll} \mbox{minimize} & s \\ \mbox{subject to} & A_i \bullet X = b_i, \quad i=1,\ldots,m, \\ & \mathbf{tr}(X) \leq M \\ & X + (s-\epsilon) I \succeq_{\rm c} 0, s \geq 0. \end{array}\end{split}\]

Here \(\epsilon\) is a small constant, and the constraint \(\mathbf{tr}(X) \leq M\) is added to bound the feasible set.

SDPs with band structure¶

We consider a family of SDP instances where the data matrices \(C,A_1,\ldots,A_m\) are of order \(n\) and banded with a common bandwidth \(2w+1\).

Experiment 1¶

\(m=100\) constraints, bandwidth \(11\) (\(w=5\)), and variable order \(n\)

Results

\[\begin{split}\begin{array}{ll} \mbox{minimize} & t \\ \mbox{subject to} & \begin{bmatrix} t I & F(x) +G \\ (F(x)+G)^T & tI \end{bmatrix} \succeq 0. \end{array}\end{split}\]

This SDP has dimensions \(m=r+1\) and \(n = p + q\). We generate \(G\) as a dense \(p\times q\) matrix, and the matrices \(F_i\) are generated such that the number of nonzero entries in each matrix is given by \(\max (1,dpq)\) where the parameter \(d \in [0,1]\) determines sparsity. The locations of nonzero entries in \(F_i\) are random. Thus, the problem family is parameterized by the tuple \((p,q,r,d)\).

Experiment 4¶

Show:

Three problems required a phase I: thetaG11 (M1 227.2 sec.; M1c 184.4 sec.), thetaG51 (M1 64.8 sec.: M1c 58.0 sec.), and truss8 (M1 17.9 sec.; M1c 17.9 sec.).

Nonchordal sparsity patterns¶

The following problems are based on sparsity patterns from the University of Florida Sparse Matrix Collection (UFSMC). We use as problem identifier the name rsX where X is the ID number of a sparsity pattern from UFSMC. Each problem instance has \(m\) constraints and the number of nonzeros in the lower triangle of \(A_i\) is \(\max\{1,\mathrm{round}(0.005 |V|)\}\) where \(|V|\) is the number of nonzeros in the lower triangle of the aggregate sparsity pattern \(V\), and \(C\) has \(|V|\) nonzeros.

Experiment 10¶

Results

Show: