naginterfaces.library.opt.sdp_​read_​sdpa

naginterfaces.library.opt.sdp_read_sdpa(infile, maxnvar, maxnblk, maxnnz, filelst=0, io_manager=None)

sdp_read_sdpa 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 handle_init() (initialization), handle_set_linobj() (linear objective function), handle_set_linmatineq() (linear matrix constraints), handle_solve_pennon() (solver) and handle_free() (deallocation) from the NAG optimization modelling suite.

For full information please refer to the NAG Library document for e04rd

https://support.nag.com/numeric/nl/nagdoc_30.3/flhtml/e04/e04rdf.html

Parameters

infileint

The unit number (see unit_from_fileobj()) associated with the sparse SDPA data file. Note: that the file needs to be opened in read mode.

maxnvarint

The upper limit for the number of variables in the problem. If $maxnvar=0$, $cvec$ and $nnza$ will not be referenced.

maxnblkint

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.

maxnnzint

The upper limit on the sum of nonzeros in all matrices $A_{\text{i}}^{\text{k}}$, for $\text{k}=1,2,\dots ,nblk$, for $\text{i}=0,1,\dots ,nvar$. If $maxnnz=0$, $irowa$, $icola$ and $a$ will not be referenced.

filelstint, optional

If $filelst\ne 0$, a listing of the input data is sent to the file object associated with the advisory I/O unit (see FileObjManager). This can be useful for debugging the data file.

If $filelst=0$, no listing is produced.

io_managerFileObjManager, optional

Manager for I/O in this routine.

Returns

nvarint

The actual number of the variables $n$, matrix constraints $m_A$ 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$.

nblkint

The actual number of the variables $n$, matrix constraints $m_A$ 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$.

nnzint

The actual number of the variables $n$, matrix constraints $m_A$ 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$.

cvecfloat, ndarray, shape $\left(maxnvar\right)$

$cvec[\text{i}-1]$, for $\text{i}=1,2,\dots ,nvar$, stores the dense vector $c$ of the linear objective function.

nnzaint, ndarray, shape $(maxnvar+1)$

$nnza\left[\text{i}\right]$, for $\text{i}=0,1,\dots ,nvar$, stores the number of nonzero elements in matrices $A_i$.

irowaint, ndarray, shape $\left(maxnnz\right)$

$irowa$, $icola$ and $a$ store the nonzeros in the upper triangle of matrices $A_{\text{i}}$, for $\text{i}=0,1,\dots ,nvar$, in the coordinate storage, i.e., $irowa[\text{j}-1]$ are one-based row indices, $icola[\text{j}-1]$ are one-based column indices and $a[\text{j}-1]$ are the values of the nonzero elements, for $\text{j}=1,2,\dots ,nnz$. See Further Comments.

icolaint, ndarray, shape $\left(maxnnz\right)$

$irowa$, $icola$ and $a$ store the nonzeros in the upper triangle of matrices $A_{\text{i}}$, for $\text{i}=0,1,\dots ,nvar$, in the coordinate storage, i.e., $irowa[\text{j}-1]$ are one-based row indices, $icola[\text{j}-1]$ are one-based column indices and $a[\text{j}-1]$ are the values of the nonzero elements, for $\text{j}=1,2,\dots ,nnz$. See Further Comments.

afloat, ndarray, shape $\left(maxnnz\right)$

$irowa$, $icola$ and $a$ store the nonzeros in the upper triangle of matrices $A_{\text{i}}$, for $\text{i}=0,1,\dots ,nvar$, in the coordinate storage, i.e., $irowa[\text{j}-1]$ are one-based row indices, $icola[\text{j}-1]$ are one-based column indices and $a[\text{j}-1]$ are the values of the nonzero elements, for $\text{j}=1,2,\dots ,nnz$. See Further Comments.

blksizeaint, ndarray, shape $\left(maxnblk\right)$

$blksizea[\text{k}-1]$, for $\text{k}=1,2,\dots ,nblk$, stores the sizes of the diagonal blocks in matrices $A_i$ from the top to the bottom.

Raises

NagValueError

(errno $2$)

The token on line $⟨value⟩$ at position $⟨value⟩$ to $⟨value⟩$ was not recognized as a valid integer.

(errno $3$)

The token on line $⟨value⟩$ at position $⟨value⟩$ to $⟨value⟩$ was not recognized as a valid real number.

(errno $4$)

The token on line $⟨value⟩$ starting at position $⟨value⟩$ was too long and was not recognized.

(errno $5$)

An invalid number of variables was given on line $⟨value⟩$.

The number stated there is $⟨value⟩$ and needs to be at least $1$.

(errno $6$)

An invalid number of blocks was given on line $⟨value⟩$.

The number stated there is $⟨value⟩$ and needs to be at least $1$.

(errno $7$)

An invalid size of the block number $⟨value⟩$ was given on line $⟨value⟩$.

The number stated there is $⟨value⟩$ and needs to be nonzero.

(errno $8$)

Not enough data was given on line $⟨value⟩$ specifying block sizes.

Expected $⟨value⟩$ tokens but found only $⟨value⟩$.

(errno $9$)

Not enough data was given on line $⟨value⟩$ specifying the objective function.

Expected $⟨value⟩$ tokens but found only $⟨value⟩$.

(errno $10$)

Not enough data was given on line $⟨value⟩$ specifying nonzero matrix elements.

Expected $⟨value⟩$ tokens but found only $⟨value⟩$.

(errno $11$)

Invalid structural data found on line $⟨value⟩$.

The given matrix number is out of bounds. Its value $⟨value⟩$ must be between $⟨value⟩$ and $⟨value⟩$ (inclusive).

(errno $12$)

Invalid structural data found on line $⟨value⟩$.

The given block number is out of bounds. Its value $⟨value⟩$ must be between $⟨value⟩$ and $⟨value⟩$ (inclusive).

(errno $13$)

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).

(errno $14$)

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).

(errno $15$)

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⟩$.

(errno $16$)

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⟩$.

(errno $17$)

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.

(errno $18$)

A premature end of the input stream. The part defining the number of variables was not found.

(errno $18$)

A premature end of the input stream. The part defining the number of blocks was not found.

(errno $18$)

A premature end of the input stream. The part defining the dimensions of the blocks was not found.

(errno $18$)

A premature end of the input stream. The part defining the objective function was not found.

(errno $18$)

A premature end of the input stream. The part defining the nonzero entries was not found.

(errno $19$)

The input stream seems to be empty. No data was read.

(errno $20$)

Reading from the stream caused an unknown error on line $⟨value⟩$.

(errno $21$)

On entry, $infile=⟨value⟩$.

Constraint: $infile\ge 0$.

(errno $21$)

On entry, $maxnvar=⟨value⟩$.

Constraint: $maxnvar\ge 0$.

(errno $21$)

On entry, $maxnblk=⟨value⟩$.

Constraint: $maxnblk\ge 0$.

(errno $21$)

On entry, $maxnnz=⟨value⟩$.

Constraint: $maxnnz\ge 0$.

Warns

NagAlgorithmicWarning

(errno $1$)

At least one of $maxnvar$, $maxnblk$ or $maxnnz$ is too small.

$maxnvar$ should be at least $⟨value⟩$, was $⟨value⟩$.

$maxnblk$ should be at least $⟨value⟩$, was $⟨value⟩$.

$maxnnz$ should be at least $⟨value⟩$, was $⟨value⟩$.

Notes

sdp_read_sdpa 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:

$$\begin{array}{c}\begin{array}{ccc}{minimize}_{x\in R^n}& c^{T}x& \text{(a)}\\ \text{subject to}& {\sum }_1^n{x}_i{A}_i-A_0⪰0\text{,}& \text{(b)}\end{array}\end{array}$$

where $A_i$ denotes symmetric matrices and $c$ is a vector. The expression $S⪰0$ 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 $m_A$ linear matrix inequalities

$$\sum _1^n{x}_i{A}_i^k-A_0^k⪰0\text{,}k=1,\dots ,m_A$$

can be equivalently expressed as one matrix inequality (3)(b) in the following block diagonal form where the matrices $A_i^1,A_i^2,\dots ,A_i^{m_A}$ create the diagonal blocks of $A_i$:

$$\begin{array}{c}\sum _1^n{x}_i\left(\begin{array}{cccc}{A}_i^1& & & \\ & A_i^2& & \\ & & \ddots & \\ & & & A_i^{m_A}\end{array}\right)-\left(\begin{array}{cccc}{A}_0^1& & & \\ & A_0^2& & \\ & & \ddots & \\ & & & A_0^{m_A}\end{array}\right)⪰0\text{.}\end{array}$$

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\times 1$), the associated matrix inequality

$$\sum _1^n{x}_i{A}_i^k-A_0^k⪰0$$

actually defines a standard linear constraint

$$Bx\ge l$$

where $l$ and columns of the matrix $B$ are formed by the diagonals of matrices $A_0^k$ and $A_1^k,\dots ,A_n^k$, respectively. Precisely, $l_i={\left(A_0^k\right)}_{ii}$ and $b_{ij}={\left(A_j^k\right)}_{ii}$.

Alternatively, handle_read_file() may be used to read the data file directly into a handle of the NAG optimization modelling suite.

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. Comments. The file can begin with an arbitrary number of lines of comment. Each line of comment must begin with ‘’’ or ‘*’.

2. The first line after the comments contains integer $n$, the number of variables. The rest of this line is ignored.

3. The second line after the comments contains integer $m_A$, the number of blocks in the block diagonal structure of the matrices. Additional text on this line after $m_A$ is ignored.

4. The third line after the comments contains a vector of $m_A$ 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\times 5$ block in which only the diagonal elements are nonzero.

5. The fourth line after the comments contains an $n$-dimensional real vector defining the objective function vector $c$.

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

   $$matnoblknoijentry$$

   where $matno$ is the number $(0,\dots ,n)$ of the matrix to which this entry belongs and $blkno$ specifies the block number $k=1,2,\dots ,m_A$ 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, ${\left(A_{matno}^{blkno}\right)}_{ij}={\left(A_{matno}^{blkno}\right)}_{ji}=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.

Recommendation on how best to use sdp_read_sdpa

1. The input file with the problem needs to be opened for reading by the FileObjManager method unit_from_fileobj() ($\text{mode}=0$). In this way we avoid possible limitations of maximal lengths of lines inherited by Fortran I/O (the FileObjManager method unit_from_fileobj() 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 $filelst=1$ might help with possible file formatting errors.

2. Unless the dimension of the problem (or its overestimate) is known in advance, initially call sdp_read_sdpa 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. Then the exact storage can be allocated and the file reopened. When sdp_read_sdpa is called for the second time, the problem is read in and stored in appropriate arrays.

3. A typical sequence of calls to solve the problem read in by sdp_read_sdpa might be as follows. First, an empty handle needs to be initialized by handle_init() with $\text{nvar}$ variables. This should be followed by calls to handle_set_linobj() and handle_set_linmatineq() to formulate the objective function and the constraints, respectively. The arguments of both functions use the same naming and storage as in sdp_read_sdpa so the variables can be passed unchanged; only $\text{dima}$ in handle_set_linmatineq() is new and should be equal to $SUM\left(blksizea\right[0:nblk\left]\right)$. $\text{nnzasum}$ in handle_set_linmatineq() is the same as $nnz$ in sdp_read_sdpa. You may at this point want to modify option settings using handle_opt_set(). 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 $\text{ua}$ in the solver handle_solve_pennon(). The solver should be called and then followed, finally, by a call to handle_free() to deallocate memory associated with the problem.

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.