NAG C Library Function Document

nag_opt_sdp_read_sdpa (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 nag_opt_handle_init (e04rac) (initialization), nag_opt_handle_set_linobj (e04rec) (linear objective function), nag_opt_handle_set_linmatineq (e04rnc) (linear matrix constraints), nag_opt_handle_solve_pennon (e04svc) (solver) and nag_opt_handle_free (e04rzc) (deallocation) from the NAG optimization modelling suite.

2

Specification

#include <nag.h>

#include <nage04.h>

void	nag_opt_sdp_read_sdpa (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)

3

Description

nag_opt_sdp_read_sdpa (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:

\begin{array}{l} \underset{x \in ℝ^{n}}{minimize} & c^{T} x & (a) \\ subject to & \sum_{i = 1}^{n} x_{i} A_{i} - A_{0} ⪰ 0, & (b) \end{array}

(1)

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_{i = 1}^{n} x_{i} A_{i}^{k} - A_{0}^{k} ⪰ 0, k = 1, \dots, m_{A}

(2)

can be equivalently expressed as one matrix inequality (1)(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}

\sum_{i = 1}^{n} x_{i} (\begin{matrix} A_{i}^{1} \\ A_{i}^{2} \\ ⋱ \\ A_{i}^{m_{A}} \end{matrix}) - (\begin{matrix} A_{0}^{1} \\ A_{0}^{2} \\ ⋱ \\ A_{0}^{m_{A}} \end{matrix}) ⪰ 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 \times 1

), the associated matrix inequality

\sum_{i = 1}^{n} x_{i} A_{i}^{k} - A_{0}^{k} ⪰ 0

(3)

defines actually a standard linear constraint

B x \geq 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} = {(A_{0}^{k})}_{i i}

and

b_{i j} = {(A_{j}^{k})}_{i i}

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

Comments. The file can begin with arbitrarily many lines of comments. Each line of comments must begin with ‘"’ or ‘*’.

The first line after the comments contains integer

n

, the number of variables. The rest of this line is ignored.

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.

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

5

block in which only the diagonal elements are nonzero.

The fourth line after the comments contains an

n

-dimensional real vector defining the objective function vector

c

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, \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,

{(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 nag_opt_sdp_read_sdpa (e04rdc)

(a)	The input file with the problem needs to be opened for reading by nag_open_file (x04acc) ( $mode = 0$ ). Setting $filelst = 1$ might help with possible file formatting errors.
(b)	Unless the dimension of the problem (or its overestimate) is known in advance, call nag_opt_sdp_read_sdpa (e04rdc) initially 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 none of the arrays cvec, nnza, irowa, icola, a, blksizea will be referenced and may be NULL. Then the exact storage can be allocated and the file reopened. When nag_opt_sdp_read_sdpa (e04rdc) 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 nag_opt_sdp_read_sdpa (e04rdc). First an empty handle needs to be initialized by nag_opt_handle_init (e04rac) with nvar variables. This should be followed by calls to nag_opt_handle_set_linobj (e04rec) and nag_opt_handle_set_linmatineq (e04rnc) to formulate the objective function and the constraints, respectively. The arguments of both functions use the same naming and storage as in nag_opt_sdp_read_sdpa (e04rdc) so the variables can be passed unchanged; only dima in nag_opt_handle_set_linmatineq (e04rnc) is new and should equal to sum $blksizea [0] + \dots + blksizea [nblk - 1]$ and nnzasum in nag_opt_handle_set_linmatineq (e04rnc) is the same as nnz in nag_opt_sdp_read_sdpa (e04rdc). You may at this point want to modify option settings using nag_opt_handle_opt_set (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 of the solver nag_opt_handle_solve_pennon (e04svc). The solver should be called and then followed, finally, by a call to nag_opt_handle_free (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_FileIDInput: On entry: the file identifier associated with the sparse SDPA data file. Note: that the file needs to be opened in read mode by nag_open_file (x04acc) with $mode = 0$ .
2: $maxnvar$ – IntegerInput: 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 and may be NULL.

Constraint: $maxnvar \geq 0$ .
3: $maxnblk$ – IntegerInput: 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 and may be NULL.

Constraint: $maxnblk \geq 0$ .
4: $maxnnz$ – IntegerInput: On entry: the upper limit on the sum of nonzeros in all matrices $A_{i}^{k}$ , for $i = 0, 1, \dots, nvar$ and $k = 1, 2, \dots, nblk$ . If it is set to zero, irowa, icola and a will not be referenced and may be NULL.

Constraint: $maxnnz \geq 0$ .
5: $filelst$ – IntegerInput: On entry: if $filelst \neq 0$ , 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 $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.
9: $cvec [maxnvar]$ – doubleOutput: On exit: $cvec [i - 1]$ , for $i = 1, 2, \dots, 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]$ – IntegerOutput: On exit: $nnza [i]$ , for $i = 0, 1, \dots, nvar$ , stores the number of nonzero elements in matrices $A_{i}$ . If $maxnvar = 0$ , nnza is not referenced and may be NULL.
11: $irowa [maxnnz]$ – IntegerOutput
12: $icola [maxnnz]$ – IntegerOutput
13: $a [maxnnz]$ – doubleOutput: On exit: irowa, icola and a store the nonzeros in the upper triangle of matrices $A_{i}$ , for $i = 0, 1, \dots, 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, \dots, nnz$ . See Section 9. If $maxnnz = 0$ , the arrays are not referenced and may be NULL.
14: $blksizea [maxnblk]$ – IntegerOutput: On exit: $blksizea [k - 1]$ , for $k = 1, 2, \dots, nblk$ , stores the sizes of the diagonal blocks in matrices $A_{i}$ 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 3.7 in How to Use the NAG Library and its Documentation).

6

Error Indicators and Warnings

NE_ALLOC_FAIL: Dynamic memory allocation failed.
See Section 2.3.1.2 in How to Use the NAG Library and its Documentation 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: $infile \geq 0$ .
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: $maxnblk \geq 0$ .

On entry, $maxnnz = 〈value〉$ .
Constraint: $maxnnz \geq 0$ .

On entry, $maxnvar = 〈value〉$ .
Constraint: $maxnvar \geq 0$ .
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 2.7.6 in How to Use the NAG Library and its Documentation 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 2.7.5 in How to Use the NAG Library and its Documentation 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 nag_open_file (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 $m_{A}$ (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 $m_{A}$ 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

nag_opt_sdp_read_sdpa (e04rdc) is not threaded in any implementation.

9

Further Comments

The following artificial example demonstrates how the elements of

A_{i}

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

A_{0} = (\begin{matrix} 0 & 0.1 & 0 \\ 0.1 & 0 & 0.2 \\ 0 & 0.2 & 0.3 \end{matrix}),

A_{1} = (\begin{matrix} 1.1 & 0 & 0 \\ 0 & 1.2 & 1.3 \\ 0 & 1.3 & 1.4 \end{matrix}),

A_{2} ​ empty,

A_{3} = (\begin{matrix} 0 & 0 & 0 \\ 0 & 3.1 & 0 \\ 0 & 0 & 3.2 \end{matrix}),

A_{4} = (\begin{matrix} 4.1 & 4.2 & 4.3 \\ 4.2 & 0 & 0 \\ 4.3 & 0 & 0 \end{matrix}) .

All matrices

A_{i}

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	$\begin{matrix} 1 & 2 & 3 \end{matrix}$	$\begin{matrix} 1 & 2 & 2 & 3 \end{matrix}$		$\begin{matrix} 2 & 3 \end{matrix}$	$\begin{matrix} 1 & 2 & 3 \end{matrix}$
icola	$\begin{matrix} 2 & 3 & 3 \end{matrix}$	$\begin{matrix} 1 & 2 & 3 & 3 \end{matrix}$		$\begin{matrix} 2 & 3 \end{matrix}$	$\begin{matrix} 1 & 1 & 1 \end{matrix}$
a	$\underset{︸}{\begin{matrix} 0.1 & 0.2 & 0.3 \end{matrix}}$	$\underset{︸}{\begin{matrix} 1.1 & 1.2 & 1.3 & 1.4 \end{matrix}}$	$\underset{︸}{}$	$\underset{︸}{\begin{matrix} 3.1 & 3.2 \end{matrix}}$	$\underset{︸}{\begin{matrix} 4.1 & 4.2 & 4.3 \end{matrix}}$
	$A_{0}$	$A_{1}$	$A_{2}$	$A_{3}$	$A_{4}$
nnza	$3$	$4$	$0$	$2$	$3$

See also Section 3 in nag_opt_handle_set_linmatineq (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.

\begin{array}{l} \underset{x \in ℝ^{2}}{minimize} & 10 x_{1} + 20 x_{2} \\ subject to & (\begin{matrix} 1 & 0 \\ 1 & 1 \end{matrix}) (\begin{matrix} x_{1} \\ x_{2} \end{matrix}) \geq (\begin{matrix} 1 \\ 1.5 \end{matrix}) \\ (\begin{matrix} 5 & 2 \\ 2 & 6 \end{matrix}) x_{2} - (\begin{matrix} 3 & 0 \\ 0 & 4 \end{matrix}) ⪰ 0 . \end{array}

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 (

m_{A} = 2

). Both blocks have dimension

2

but the first one (defining linear constraints) is only diagonal, thus the sizes will be stated as

\begin{matrix} - 2 & 2 \end{matrix}

The problem can be rewritten as

\begin{array}{l} \underset{x \in ℝ^{2}}{minimize} & c^{T} x \\ subject to & A_{1} x_{1} + A_{2} x_{2} - A_{0} ⪰ 0 \end{array}

where

$c = {(\begin{matrix} 10 & 20 \end{matrix})}^{T}$ ,
$A_{0} = (\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1.5 & 0 & 0 \\ 0 & 0 & 3 & 0 \\ 0 & 0 & 0 & 4 \end{matrix})$ ,
$A_{1} = (\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{matrix})$ ,
$A_{2} = (\begin{matrix} 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 5 & 2 \\ 0 & 0 & 2 & 6 \end{matrix})$ .

The optimal solution is

x^{*} = {(\begin{matrix} 1.0 & 1.0 \end{matrix})}^{T}

with the objective function value

30.0

. The optimal Lagrangian multipliers (dual variables) are

10.0

0.0

and

(\begin{matrix} 20 / 7, & - 20 / 7 \\ - 20 / 7, & 20 / 7 \end{matrix})

See also Section 10 in nag_opt_handle_init (e04rac) for links to further examples in the suite.

NAG C Library Function Document

nag_opt_sdp_read_sdpa (e04rdc)

▸▿ Contents

1 Purpose

2 Specification

3 Description

3.1 Sparse SDPA file format

3.2 Recommendation on how best to use nag_opt_sdp_read_sdpa (e04rdc)

4 References

5 Arguments

6 Error Indicators and Warnings

7 Accuracy

8 Parallelism and Performance

9 Further Comments

10 Example

10.1 Program Text

10.2 Program Data

10.3 Program Results

1

Purpose

2

Specification

3

Description

3.1

Sparse SDPA file format

3.2

Recommendation on how best to use nag_opt_sdp_read_sdpa (e04rdc)

4

References

5

Arguments

6

Error Indicators and Warnings

7

Accuracy

8

Parallelism and Performance

9

Further Comments

10

Example

10.1

Program Text

10.2

Program Data

10.3

Program Results