NAG CL Interface
e04rdc (sdp_​read_​sdpa)

Settings help

CL Name Style:


1 Purpose

e04rdc reads in a linear semidefinite programming problem (SDP) from a file in sparse SDPA format and returns it in the form which is usable by functions e04rac (initialization), e04rec (linear objective function), e04rnc (linear matrix constraints), e04svc (solver) and e04rzc (deallocation) from the NAG optimization modelling suite.

2 Specification

#include <nag.h>
void  e04rdc (Nag_FileID infile, Integer maxnvar, Integer maxnblk, Integer maxnnz, Integer filelst, Integer *nvar, Integer *nblk, Integer *nnz, double cvec[], Integer nnza[], Integer irowa[], Integer icola[], double a[], Integer blksizea[], NagError *fail)
The function may be called by the names: e04rdc or nag_opt_sdp_read_sdpa.

3 Description

e04rdc is capable of reading linear semidefinite programming problems (SDP) from a text file in sparse SDPA format. The problem is captured and returned in the following form:
minimize xn cTx   (a) subject to   i=1 n xi Ai - A0 0 ,   (b) (1)
where Ai denotes symmetric matrices and c is a vector. The expression S0 stands for a constraint on the eigenvalues of a symmetric matrix S, namely, all the eigenvalues should be non-negative, i.e., the matrix S should be positive semidefinite.
Please note that this form covers even general linear SDP formulations with multiple linear matrix inequalities and a set of standard linear constraints. A set of mA linear matrix inequalities
i=1 n xi Aik - A0k 0 ,  k=1,,mA (2)
can be equivalently expressed as one matrix inequality (1)(b) in the following block diagonal form where the matrices Ai1 , Ai2 , , AimA create the diagonal blocks of Ai:
i=1 n xi ( Ai1 Ai2 AimA ) - ( A01 A02 A0mA ) 0 .  
In addition, notice that if all matrices A i k belonging to the same block, say block k, are themselves diagonal matrices (or have dimension 1×1), the associated matrix inequality
i=1 n xi Aik - A0k 0 (3)
actually defines a standard linear constraint
Bxl  
where l and columns of the matrix B are formed by the diagonals of matrices A0k and A1k,,Ank, respectively. Precisely, li = (A0k) ii and bij = (Ajk) ii .
Alternatively, e04sac may be used to read the data file directly into a handle of the NAG optimization modelling suite.

3.1 Sparse SDPA file format

The problem data is written in an ASCII input file in the SDPA sparse format which was first introduced in Fujisawa et al. (1998). In the description below we follow closely the specification from Borchers (1999).
The format is line oriented. If more elements are required on the line they need to be separated by a space, a tab or any of the special characters ‘,’, ‘(’, ‘)’, ‘{’ or ‘}’. The file consists of six sections:
  1. 1.Comments. The file can begin with an arbitrary number of lines of comment. Each line of comment must begin with ‘"’ or ‘*’.
  2. 2.The first line after the comments contains integer n, the number of variables. The rest of this line is ignored.
  3. 3.The second line after the comments contains integer mA, the number of blocks in the block diagonal structure of the matrices. Additional text on this line after mA is ignored.
  4. 4.The third line after the comments contains a vector of mA integers that give the sizes of the individual blocks. Negative numbers may be used to indicate that a block is actually a diagonal submatrix. Thus a block size of ‘-5’ indicates a 5×5 block in which only the diagonal elements are nonzero.
  5. 5.The fourth line after the comments contains an n-dimensional real vector defining the objective function vector c.
  6. 6.The remaining lines of the file contain nonzero entries in the constraint matrices, with one entry per line. The format for each line is
    matno blkno i j entry  
    where matno is the number (0,,n) of the matrix to which this entry belongs and blkno specifies the block number k=1,2,,mA within this matrix. Together, they uniquely identify the block A matno blkno . Integers i and j are one-based indices which specify a location of the entry within the block. Note that since all matrices are assumed to be symmetric, only entries in the upper triangle of a matrix should be supplied. Finally, entry should give the real value of the entry in the matrix. Precisely, ( A matno blkno ) i j = ( A matno blkno ) j i = entry .
In the text below and in the file listing (filelst) we use the word ‘token’ as a reference to a group of contiguous characters without a space or any other delimeters.

3.2 Recommendation on how best to use e04rdc

  1. (a)The input file with the problem needs to be opened for reading by x04acc (mode=0). Setting filelst=1 might help with possible file formatting errors.
  2. (b)Unless the dimension of the problem (or its overestimate) is known in advance, initially call e04rdc with maxnvar=0, maxnblk=0 and maxnnz=0. In this case, the exact size of the problem is computed and returned in nvar, nblk and nnz. No other data will be stored and the arrays cvec, nnza, irowa, icola, a, blksizea will not be referenced and may be NULL. Then the exact storage can be allocated and the file reopened. When e04rdc is called for the second time, the problem is read in and stored in appropriate arrays.
  3. (c)A typical sequence of calls to solve the problem read in by e04rdc might be as follows. First, an empty handle needs to be initialized by e04rac with nvar variables. This should be followed by calls to e04rec and e04rnc to formulate the objective function and the constraints, respectively. The arguments of both functions use the same naming and storage as in e04rdc so the variables can be passed unchanged; only dima in e04rnc is new and should be equal to sum blksizea[0] ++ blksizea[nblk-1] . nnzasum in e04rnc is the same as nnz in e04rdc. You may at this point want to modify option settings using e04zmc. If dual variables (Lagrangian multipliers) are required from the solver, sufficient space needs to be allocated. The size is equal to the sum of the number of elements of dense triangular matrices for each block. For further details, see the argument ua in the solver e04svc. The solver should be called and then followed, finally, by a call to e04rzc to deallocate memory associated with the problem.

4 References

Borchers B (1999) SDPLIB 1.2, A Library of semidefinite programming test problems Optimization Methods and Software 11(1) 683–690 http://euler.nmt.edu/~brian/sdplib/
Fujisawa K, Kojima M and Nakata K (1998) SDPA (Semidefinite Programming Algorithm) User's Manual Technical Report B-308 Department of Mathematical and Computing Sciences, Tokyo Institute of Technology.

5 Arguments

1: infile Nag_FileID Input
On entry: the file identifier associated with the sparse SDPA data file. Note:  that the file needs to be opened in read mode by x04acc with mode=0.
2: maxnvar Integer Input
On entry: the upper limit for the number of variables in the problem. If maxnvar=0, cvec and nnza will not be referenced and may be NULL.
Constraint: maxnvar0.
3: maxnblk Integer Input
On entry: the upper limit for the number of matrix constraints (i.e., the number of diagonal blocks within the matrix). If maxnblk=0, blksizea will not be referenced and may be NULL.
Constraint: maxnblk0.
4: maxnnz Integer Input
On entry: the upper limit on the sum of nonzeros in all matrices Aik, for i=0,1,,nvar and k=1,2,,nblk. If maxnnz=0, irowa, icola and a will not be referenced and may be NULL.
Constraint: maxnnz0.
5: filelst Integer Input
On entry: if filelst0, a listing of the input data is sent to stdout. This can be useful for debugging the data file.
If filelst=0, no listing is produced.
6: nvar Integer * Output
7: nblk Integer * Output
8: nnz Integer * Output
On exit: the actual number of the variables n, matrix constraints mA and number of nonzeros of the problem in the file. This also indicates the exact memory needed in cvec, nnza, irowa, icola, a and blksizea.
9: cvec[maxnvar] double Output
On exit: cvec[i-1], for i=1,2,,nvar, stores the dense vector c of the linear objective function. If maxnvar=0, cvec is not referenced and may be NULL.
10: nnza[maxnvar+1] Integer Output
On exit: nnza[i], for i=0,1,,nvar, stores the number of nonzero elements in matrices Ai. If maxnvar=0, nnza is not referenced and may be NULL.
11: irowa[maxnnz] Integer Output
12: icola[maxnnz] Integer Output
13: a[maxnnz] double Output
On exit: irowa, icola and a store the nonzeros in the upper triangle of matrices Ai, for i=0,1,,nvar, in the coordinate storage, i.e., irowa[j-1] are one-based row indices, icola[j-1] are one-based column indices and a[j-1] are the values of the nonzero elements, for j=1,2,,nnz. See Section 9. If maxnnz=0, the arrays are not referenced and may be NULL.
14: blksizea[maxnblk] Integer Output
On exit: blksizea[k-1], for k=1,2,,nblk, stores the sizes of the diagonal blocks in matrices Ai from the top to the bottom. If maxnblk=0, blksizea is not referenced and may be NULL.
15: fail NagError * Input/Output
The NAG error argument (see Section 7 in the Introduction to the NAG Library CL Interface).

6 Error Indicators and Warnings

NE_ALLOC_FAIL
Dynamic memory allocation failed.
See Section 3.1.2 in the Introduction to the NAG Library CL Interface for further information.
NE_BAD_PARAM
On entry, argument value had an illegal value.
NE_DIAG_ELEMENTS
Invalid structural data found on line value.
The specified element belongs to a diagonal block but is not diagonal.
The row index is value and column index is value.
NE_DUPLICATE_ELEMENT
An entry in the constraints with matno=value, blkno=value, row index value and column index value was defined more than once. All entries need to be unique.
NE_FILE_INCOMPLETE
A premature end of the input stream. The part defining the dimensions of the blocks was not found.
A premature end of the input stream. The part defining the nonzero entries was not found.
A premature end of the input stream. The part defining the number of blocks was not found.
A premature end of the input stream. The part defining the number of variables was not found.
A premature end of the input stream. The part defining the objective function was not found.
NE_FILEID
On entry, infile=value.
Constraint: infile0.
NE_INT
An invalid number of blocks was given on line value.
The number stated there is value and needs to be at least 1.
An invalid number of variables was given on line value.
The number stated there is value and needs to be at least 1.
NE_INT_ARG
On entry, maxnblk=value.
Constraint: maxnblk0.
On entry, maxnnz=value.
Constraint: maxnnz0.
On entry, maxnvar=value.
Constraint: maxnvar0.
NE_INT_ARRAY
An invalid size of the block number value was given on line value.
The number stated there is value and needs to be nonzero.
NE_INT_MAX
At least one of maxnvar, maxnblk or maxnnz is too small. Suggested values are returned in nvar, nblk and nnz, respectively.
NE_INTERNAL_ERROR
An internal error has occurred in this function. Check the function call and any array sizes. If the call is correct then please contact NAG for assistance.
See Section 7.5 in the Introduction to the NAG Library CL Interface for further information.
NE_INVALID_CS
Invalid structural data found on line value.
The given column index is out of bounds, it must respect the size of the block. Its value value must be between value and value (inclusive).
Invalid structural data found on line value.
The given row index is out of bounds, it must respect the size of the block. Its value value must be between value and value (inclusive).
Invalid structural data found on line value.
The specified nonzero element is not in the upper triangle.
The row index is value and column index is value.
NE_INVALID_FORMAT
The token on line value at position value to value was not recognized as a valid integer.
The token on line value at position value to value was not recognized as a valid real number.
The token on line value starting at position value was too long and was not recognized.
NE_NO_LICENCE
Your licence key may have expired or may not have been installed correctly.
See Section 8 in the Introduction to the NAG Library CL Interface for further information.
NE_NOT_READ_FILE
The input stream seems to be empty. No data was read. This might indicate a problem with opening the file, check that x04acc was used correctly.
NE_OUT_OF_RANGE
Invalid structural data found on line value.
The given block number is out of bounds. Its value value must be between 1 and mA (inclusive).
Invalid structural data found on line value.
The given matrix number is out of bounds. Its value value must be between 0 and n (inclusive).
NE_READ_ERROR
Reading from the stream caused an unknown error on line value.
NE_WRONG_NUM_TOKENS
Not enough data was given on line value specifying block sizes.
Expected mA tokens but found only value.
Not enough data was given on line value specifying nonzero matrix elements.
Expected value tokens but found only value.
Not enough data was given on line value specifying the objective function.
Expected n tokens but found only value.

7 Accuracy

Not applicable.

8 Parallelism and Performance

e04rdc is not threaded in any implementation.

9 Further Comments

The following artificial example demonstrates how the elements of Ai matrices are organized within arrays nnza, irowa, icola and a. For simplicity let us assume that nblk=1, blksizea[0]=3 and nvar=4. Please note that the values of the elements were chosen to ease readability rather than to define a valid problem.
Let the matrix constraint (1)(b) be defined by
A0 = ( 0 0.1 0 0.1 0 0.2 0 0.2 0.3 ) , A1 = ( 1.1 0 0 0 1.2 1.3 0 1.3 1.4 ) , A2 ​ empty, A3 = ( 0 0 0 0 3.1 0 0 0 3.2 ) , A4 = ( 4.1 4.2 4.3 4.2 0 0 4.3 0 0 ) .  
All matrices Ai have to be symmetric and, therefore, only the elements in the upper triangles are stored. The table below shows how the arrays would be populated.
irowa 01. 02. 03. 01. 02. 02. 03. 02. 03. 01. 02. 03.
icola 02. 03. 03. 01. 02. 03. 03. 02. 03. 01. 01. 01.
a 0.1 0.2 0.3 1.1 1.2 1.3 1.4 000.0 3.1 3.2 4.1 4.2 4.3
A0 A1 A2 A3 A4
nnza 3 4 0 2 3
See also Section 3 in e04rnc which accepts the same format.

10 Example

The following example comes from Fujisawa et al. (1998).
Imagine that we want to store the following problem in a file in the SDPA format.
minimize x2 10x1 + 20x2 subject to ( 1 0 1 1 ) ( x1 x2 ) ( 1 1.5 ) , ( 5 2 2 6 ) x2 - ( 3 0 0 4 ) 0 .  
There are two variables (n=2) in the problem. One linear matrix constraint and one block of linear constraints can be formed as (1) with two diagonal blocks (mA=2). Both blocks have dimension 2 but the first one (defining linear constraints) is only diagonal, thus the sizes will be stated as -2 2 .
The problem can be rewritten as
minimize x2 cTx subject to A1x1 + A2x2 - A0 0 ,  
where
c= ( 10 20 ) T , A0 = ( 1 0 0 0 0 1.5 0 0 0 0 3 0 0 0 0 4 ) , A1 = ( 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 ) , A2 = ( 0 0 0 0 0 1 0 0 0 0 5 2 0 0 2 6 ) .  
The optimal solution is x*= ( 1.0 1.0 ) T with the objective function value 30.0. The optimal Lagrangian multipliers (dual variables) are 10.0, 0.0 and ( 20/7, -20/7 -20/7, 20/7 ).
See also e04rac for links to further examples in the suite.

10.1 Program Text

Program Text (e04rdce.c)

10.2 Program Data

Program Options (e04rdce.opt)

10.3 Program Results

Program Results (e04rdce.r)