next up previous
Next: The Codes Up: Introduction Previous: The Problems Solved

Computing Errors

Suppose that we are given approximate optimal solutions of ($SQLP-P$) and ($SQLP-D$), respectively. To compute how far they are from an exact solution pair, we define a norm on $ X$, and a minimum eigenvalue w.r.t. the cone $ K$. Precisely, if $ x \in X$, then

$\displaystyle \vert\!\vert x \vert\!\vert = \sum_{j=1}^{n_s} \vert\!\vert x^s_j...
...vert\!\vert x^q_k \vert\!\vert _2 \, + \, \vert\!\vert x^\ell \vert\!\vert _2, $

where for a matrix $ a$, $ \vert\!\vert a \vert\!\vert _F$ is the Frobenius norm of $ a$. Also,

$\displaystyle \lambda_{\min, K}(x) = \min \, \biggl\{ \min_{j=1, \dots, n_s} \l...
...min_{k=1, \dots, n_q} \lambda_{\min,q}(x^q_k), \,
\min_{h} x^\ell_h

where Also, we denote by $ \vert\!\vert a \vert\!\vert _1$ the absolute value of the largest component of $ a$, for an arbitrary $ a \in X$.

Then, for approximate optimal solutions $ x$ of ($SQLP-P$) and $ (y,z)$ of ($SQLP-D$), we define

$\displaystyle {\rm err }_1(x,y,z)$ $\displaystyle =$ $\displaystyle \frac{\vert\!\vert \mathcal{A}x - b \vert\!\vert}{1+ \vert\!\vert b \vert\!\vert _1}$  
$\displaystyle {\rm err }_2(x,y,z)$ $\displaystyle =$ $\displaystyle \max \biggl\{ 0, \frac{-\lambda_{\min,K}(x)}{1+ \vert\!\vert b \vert\!\vert _1} \biggr\}$  
$\displaystyle {\rm err }_3(x,y,z)$ $\displaystyle =$ $\displaystyle \frac{\vert\!\vert \mathcal{A}^* y + z - c \vert\!\vert}{1 + \vert\!\vert c \vert\!\vert _1}$  
$\displaystyle {\rm err }_4(x,y,z)$ $\displaystyle =$ $\displaystyle \max \biggl\{ 0, \frac{-\lambda_{\min,K}(z)}{1+ \vert\!\vert c \vert\!\vert _1} \biggr\}$  
$\displaystyle {\rm err }_5(x,y,z)$ $\displaystyle =$ $\displaystyle \frac{\langle c, x \rangle - b^T y }{1+ \vert \langle c, x \rangle \vert + \vert b^T y \vert}$  

Furthermore, when $ x$ and $ z$ are both in $ K$, that is $ {\rm err }_2(x,y,z) = {\rm err }_4(x,y,z) = 0$, we also define
$\displaystyle {\rm err }_6(x,y,z)$ $\displaystyle =$ $\displaystyle \frac{\langle x, z \rangle }{1+ \vert \langle c, x \rangle \vert + \vert b^T y \vert}$  

A few remarks are in order.

In the error tables below $ {\rm err }_1$ and $ {\rm err }_5$ are always listed. $ {\rm err }_2$ is only given when nonzero and $ {\rm err }_6$ only when in the digits shown different from $ {\rm err }_5$. $ {\rm err }_6$ is not available for SDPA.

From the time the benchmark problems for the Challenge were published until the time the papers for this volume were due we have performed an evaluation of the codes on all the benchmark problems each code could solve. In most cases we had the latest version of the codes which the authors themselves used and on which their contributions to the volume are based. An exception is the code SDPA. Its authors are reporting about work done after release of their software and which is not yet available in coded form. The codes BMPR and BMZ were released once and not updated. All remaining codes were updated at least once, several at the time of the workshop or thereafter. Substantial changes were done with DSDP which evolved from a special code for discrete graph problems to a general purpose SDP solver accepting also standard sparse SDPA input format. Further quite remarkable improvements were applied to SDPT3, BUNDLE, and CSDP.

These benchmark results are meant to yield a rough overview of how the tested codes performed on the same, standard platform, a Sun Ultra 60 with Solaris 8, 2 GB of memory, and a 450 MHz processor. Paging was avoided. In the following section first basic information is given on each participating code. Then, as provided by the authors, a short description follows of the code itself, the stopping criteria used, and the perceived strengths and weaknesses. In the third section the test problems are listed followed by some remarks regarding the performance of the codes. Appended are tables with problem statistics and the benchmark results.

next up previous
Next: The Codes Up: Introduction Previous: The Problems Solved
Hans D. Mittelmann 2002-08-17