NAG FL Interface
e04rdf (sdp_read_sdpa)
1
Purpose
e04rdf 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 routines
e04raf (initialization),
e04ref (linear objective function),
e04rnf (linear matrix constraints),
e04svf (solver) and
e04rzf (deallocation) from the NAG optimization modelling suite.
2
Specification
Fortran Interface
Subroutine e04rdf ( |
infile, maxnvar, maxnblk, maxnnz, filelst, nvar, nblk, nnz, cvec, nnza, irowa, icola, a, blksizea, ifail) |
Integer, Intent (In) |
:: |
infile, maxnvar, maxnblk, maxnnz, filelst |
Integer, Intent (Inout) |
:: |
ifail |
Integer, Intent (Out) |
:: |
nvar, nblk, nnz, nnza(maxnvar+1), irowa(maxnnz), icola(maxnnz), blksizea(maxnblk) |
Real (Kind=nag_wp), Intent (Out) |
:: |
cvec(maxnvar), a(maxnnz) |
|
C Header Interface
#include <nag.h>
void |
e04rdf_ (const Integer *infile, const Integer *maxnvar, const Integer *maxnblk, const Integer *maxnnz, const Integer *filelst, Integer *nvar, Integer *nblk, Integer *nnz, double cvec[], Integer nnza[], Integer irowa[], Integer icola[], double a[], Integer blksizea[], Integer *ifail) |
|
C++ Header Interface
#include <nag.h> extern "C" {
void |
e04rdf_ (const Integer &infile, const Integer &maxnvar, const Integer &maxnblk, const Integer &maxnnz, const Integer &filelst, Integer &nvar, Integer &nblk, Integer &nnz, double cvec[], Integer nnza[], Integer irowa[], Integer icola[], double a[], Integer blksizea[], Integer &ifail) |
}
|
The routine may be called by the names e04rdf or nagf_opt_sdp_read_sdpa.
3
Description
e04rdf 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:
where
denotes symmetric matrices and
is a vector. The expression
stands for a constraint on the eigenvalues of a symmetric matrix
, namely, all the eigenvalues should be non-negative, i.e., the matrix
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
linear matrix inequalities
can be equivalently expressed as one matrix inequality
(1)(b) in the following block diagonal form where the matrices
create the diagonal blocks of
:
In addition, notice that if all matrices
belonging to the same block, say block
, are themselves diagonal matrices (or have dimension
), the associated matrix inequality
defines actually a standard linear constraint
where
and columns of the matrix
are formed by the diagonals of matrices
and
, respectively. Precisely,
and
. See
Section 10.
3.1
Sparse SDPA file format
The problem data is written in an ASCII input file in a 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.Comments. The file can begin with arbitrarily many lines of comments. Each line of comments must begin with ‘"’ or ‘*’.
-
2.The first line after the comments contains integer , the number of variables. The rest of this line is ignored.
-
3.The second line after the comments contains integer , the number of blocks in the block diagonal structure of the matrices. Additional text on this line after is ignored.
-
4.The third line after the comments contains a vector of 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 ‘’ indicates a by block in which only the diagonal elements are nonzero.
-
5.The fourth line after the comments contains an -dimensional real vector defining the objective function vector .
-
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
where is the number of the matrix to which this entry belongs and specifies the block number within this matrix. Together, they uniquely identify the block . Integers and 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, should give the real value of the entry in the matrix. Precisely, .
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 e04rdf
-
(a)The input file with the problem needs to be opened for reading by x04acf ().
In this way we avoid possible limitations of maximal lengths of lines inherited by Fortran I/O (x04acf uses the formatted stream access mode to bypass the restriction). If the file is opened by other means or standard input is used instead, lines within the file might be truncated which would produce a file format error message. This would most likely happen on the line defining the objective function.
Setting might help with possible file formatting errors.
-
(b)Unless the dimension of the problem (or its overestimate) is known in advance, call e04rdf initially with , and . 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 none of the arrays cvec, nnza, irowa, icola, a, blksizea will be referenced.
Then the exact storage can be allocated and the file reopened. When e04rdf is called for the second time, the problem is read in and stored in appropriate arrays.
-
(c)The example in Section 10 shows a typical sequence of calls to solve the problem read in by e04rdf. First an empty handle needs to be initialized by e04raf with nvar variables. This should be followed by calls to e04ref and e04rnf to formulate the objective function and the constraints, respectively. The arguments of both routines use the same naming and storage as in e04rdf so the variables can be passed unchanged; only dima in e04rnf is new and should equal to
and nnzasum in e04rnf is the same as nnz in e04rdf. You may at this point want to modify option settings using e04zmf. 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 of the solver e04svf. The solver should be called and then followed, finally, by a call to e04rzf 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:
– Integer
Input
-
On entry: the unit number associated with the sparse SDPA data file.
Note: that the file needs to be opened in read mode by
x04acf with
.
Constraint:
.
-
2:
– Integer
Input
-
On entry: the upper limit for the number of variables in the problem. If it is set to zero,
cvec and
nnza will not be referenced.
Constraint:
.
-
3:
– Integer
Input
-
On entry: the upper limit for the number of matrix constraints (i.e., the number of diagonal blocks within the matrix). If it is set to zero,
blksizea will not be referenced.
Constraint:
.
-
4:
– Integer
Input
-
On entry: the upper limit on the sum of nonzeros in all matrices
, for
and
. If it is set to zero,
irowa,
icola and
a will not be referenced.
Constraint:
.
-
5:
– Integer
Input
-
On entry: if
, a listing of the input data is sent to
the current advisory message unit (as defined by
x04abf).
This can be useful for debugging the data file.
If , no listing is produced.
-
6:
– Integer
Output
-
7:
– Integer
Output
-
8:
– Integer
Output
-
On exit: the actual number of the variables
, matrix constraints
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:
– Real (Kind=nag_wp) array
Output
-
On exit: , for , stores the dense vector of the linear objective function.
-
10:
– Integer array
Output
-
On exit: , for , stores the number of nonzero elements in matrices .
-
11:
– Integer array
Output
-
12:
– Integer array
Output
-
13:
– Real (Kind=nag_wp) array
Output
-
On exit:
irowa,
icola and
a store the nonzeros in the upper triangle of matrices
, for
, in the coordinate storage, i.e.,
are one-based row indices,
are one-based column indices and
are the values of the nonzero elements, for
. See
Section 9.
-
14:
– Integer array
Output
-
On exit: , for , stores the sizes of the diagonal blocks in matrices from the top to the bottom.
-
15:
– Integer
Input/Output
-
On entry:
ifail must be set to
,
. If you are unfamiliar with this argument you should refer to
Section 4 in the Introduction to the NAG Library FL Interface for details.
For environments where it might be inappropriate to halt program execution when an error is detected, the value
is recommended. If the output of error messages is undesirable, then the value
is recommended. Otherwise, because for this routine the values of the output arguments may be useful even if
on exit, the recommended value is
.
When the value is used it is essential to test the value of ifail on exit.
On exit:
unless the routine detects an error or a warning has been flagged (see
Section 6).
6
Error Indicators and Warnings
If on entry
or
, explanatory error messages are output on the current error message unit (as defined by
x04aaf).
Errors or warnings detected by the routine:
Note: in some cases e04rdf may return useful information.
-
At least one of
maxnvar,
maxnblk or
maxnnz is too small. Suggested values are returned in
nvar,
nblk and
nnz, respectively.
-
The token on line at position to was not recognized as a valid integer.
-
The token on line at position to was not recognized as a valid real number.
-
The token on line starting at position was too long and was not recognized.
-
An invalid number of variables was given on line .
The number stated there is and needs to be at least .
-
An invalid number of blocks was given on line .
The number stated there is and needs to be at least .
-
An invalid size of the block number was given on line .
The number stated there is and needs to be nonzero.
-
Not enough data was given on line specifying block sizes.
Expected
tokens but found only .
-
Not enough data was given on line specifying the objective function.
Expected tokens but found only .
-
Not enough data was given on line specifying nonzero matrix elements.
Expected tokens but found only .
-
Invalid structural data found on line .
The given matrix number is out of bounds. Its value must be between
and
(inclusive).
-
Invalid structural data found on line .
The given block number is out of bounds. Its value must be between
and
(inclusive).
-
Invalid structural data found on line .
The given row index is out of bounds, it must respect the size of the block. Its value must be between and (inclusive).
-
Invalid structural data found on line .
The given column index is out of bounds, it must respect the size of the block. Its value must be between and (inclusive).
-
Invalid structural data found on line .
The specified nonzero element is not in the upper triangle.
The row index is and column index is .
-
Invalid structural data found on line .
The specified element belongs to a diagonal block but is not diagonal.
The row index is and column index is .
-
An entry in the constraints with , , row index and column index was defined more than once. All entries need to be unique.
-
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.
-
The input stream seems to be empty. No data was read.
This might indicate a problem with opening the file, check that
x04acf was used correctly.
-
Reading from the stream caused an unknown error on line .
-
On entry, .
Constraint: .
On entry, .
Constraint: .
On entry, .
Constraint: .
On entry, .
Constraint: .
An unexpected error has been triggered by this routine. Please
contact
NAG.
See
Section 7 in the Introduction to the NAG Library FL Interface for further information.
Your licence key may have expired or may not have been installed correctly.
See
Section 8 in the Introduction to the NAG Library FL Interface for further information.
Dynamic memory allocation failed.
See
Section 9 in the Introduction to the NAG Library FL Interface for further information.
7
Accuracy
Not applicable.
8
Parallelism and Performance
e04rdf is not threaded in any implementation.
The following artificial example demonstrates how the elements of
matrices are organized within arrays
nnza,
irowa,
icola and
a. For simplicity let us assume that
,
and
. 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
All matrices
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 |
|
|
|
|
|
icola |
|
|
|
|
|
a |
|
|
|
|
|
|
|
|
|
|
|
nnza |
|
|
|
|
|
See also
Section 3 in
e04rnf 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.
There are two variables (
) in the problem. One linear matrix constraint and one block of linear constraints can be formed as
(1) with two diagonal blocks (
). Both blocks have dimension
but the first one (defining linear constraints) is only diagonal, thus the sizes will be stated as
.
The problem can be rewritten as
where
- ,
-
,
-
,
-
.
The optimal solution is with the objective function value . The optimal Lagrangian multipliers (dual variables) are , and .
See also
Section 10 in
e04raf for links to further examples in the suite.
10.1
Program Text
10.2
Program Data
10.3
Program Results