NAG Library Routine Document
E04RNF
1 Purpose
E04RNF is a part of the NAG optimization modelling suite and defines one or more linear matrix constraints of the problem.
2 Specification
SUBROUTINE E04RNF ( 
HANDLE, NVAR, DIMA, NNZA, NNZASUM, IROWA, ICOLA, A, NBLK, BLKSIZEA, IDBLK, IFAIL) 
INTEGER 
NVAR, DIMA, NNZA(NVAR+1), NNZASUM, IROWA(NNZASUM), ICOLA(NNZASUM), NBLK, BLKSIZEA(NBLK), IDBLK, IFAIL 
REAL (KIND=nag_wp) 
A(NNZASUM) 
TYPE (C_PTR) 
HANDLE 

3 Description
After the initialization routine
E04RAF has been called, E04RNF may be used to add one or more linear matrix inequalities
to the problem definition. Here
${A}_{i}$ are
$d$ by
$d$ symmetric matrices. The expression
$S\u2ab00$ stands for a constraint on eigenvalues of a symmetric matrix
$S$, namely, all the eigenvalues should be nonnegative, i.e., the matrix
$S$ should be positive semidefinite.
Typically, this will be used in linear semidefinite programming problems (SDP)
or to define the linear part of bilinear matrix inequalities
(3)(b) in (BMISDP)
E04RNF can be called repeatedly to accumulate more matrix inequalities. See
E04RAF for more details.
All the matrices
${A}_{\mathit{i}}$, for
$\mathit{i}=0,1,\dots ,n$, are symmetric and thus only their upper triangles are passed to the routine. They are stored in sparse coordinate storage format (see
Section 2.1.1 in the F11 Chapter Introduction), i.e., every nonzero from the upper triangles is coded as a triplet of row index, column index and the numeric value. These triplets of all (upper triangle) nonzeros from all
${A}_{i}$ matrices are passed to the routine in three arrays:
IROWA for row indices,
ICOLA for column indices and
A for the values. No particular order of nonzeros within one matrix is enforced but all nonzeros from
${A}_{0}$ must be stored first, followed by all nonzero from
${A}_{1}$, followed by
${A}_{2}$, etc.
The number of stored nonzeros from each
${A}_{i}$ matrix is given in
${\mathbf{NNZA}}\left(i+1\right)$, thus this array indicates which section of arrays
IROWA,
ICOLA and
A belongs to which
${A}_{i}$ matrix. See
Table 1 and the example in
Section 9. See also
E04RDF which uses the same data organization.
IROWA 
upper triangle 
upper triangle 

upper triangle

ICOLA 
nonzeros 
nonzeros 
$\cdots $ 
nonzeros 
A 
$\underbrace{\text{from}{A}_{0}}$ 
$\underbrace{\text{from}{A}_{1}}$ 

$\underbrace{\text{from}{A}_{n}}$ 

${\mathbf{NNZA}}\left(1\right)$ 
${\mathbf{NNZA}}\left(2\right)$ 

${\mathbf{NNZA}}\left(n+1\right)$ 
Table 1
Coordinate storage format of matrices ${A}_{0},{A}_{1},\dots ,{A}_{n}$ in input arrays
There are two possibilities for defining more matrix inequality constraints
to the problem. The first is to call E04RNF
${m}_{A}$ times and define a single matrix inequality at a time. This might be more straightforward and therefore it is recommended. Alternatively, it is possible to merge all
${m}_{A}$ constraints into one inequality and pass them in a single call to E04RNF. It is easy to see that
(4) can be equivalently expressed as one bigger matrix inequality with the following block diagonal structure
If
${d}_{k}$ denotes the dimension of inequality
$k$, the new merged inequality has dimension
$d={\displaystyle \sum _{\mathit{k}=1}^{{m}_{A}}}{d}_{k}$ and each of the
${A}_{i}$ matrices is formed by
${A}_{i}^{1},{A}_{i}^{2},\dots ,{A}_{i}^{{m}_{A}}$ stored as
${m}_{A}$ diagonal blocks. In such a case,
NBLK is set to
${m}_{A}$ and
${\mathbf{BLKSIZEA}}\left(k\right)$ to
${d}_{k}$, the size of the
$k$th diagonal blocks. This might be useful in connection with
E04RDF.
On the other hand, if there is no block structure and just one matrix inequality is provided,
NBLK should be set to
$1$ and
BLKSIZEA is not referenced.
3.2 Definition of Bilinear Matrix Inequalities (BMI)
E04RNF is designed to be used together with
E04RPF to define bilinear matrix inequalities
(3)(b). E04RNF sets the linear part of the constraint and
E04RPF expands it by higher order terms. To distinquish which linear matrix inequality (or more precisely, which block) is to be expanded,
E04RPF needs the number of the block,
IDBLK. The blocks are numbered as they are added, starting from
$1$.
Whenever a matrix inequality (or a set of them expressed as diagonal blocks) is stored, the routine returns
IDBLK of the last inequality added.
IDBLK is just the order of the inequality amongst all matrix inequalities accumulated through the calls. The first inequality has
${\mathbf{IDBLK}}=1$, the second one
${\mathbf{IDBLK}}=2$, etc. Therefore if you call E04RNF for the very first time with
${\mathbf{NBLK}}=42$, it adds
$42$ inequalities with
IDBLK from
$1$ to
$42$ and the routine returns
${\mathbf{IDBLK}}=42$ (the number of the last one). A subsequent call with
${\mathbf{NBLK}}=1$ would add only one inequality, this time with
${\mathbf{IDBLK}}=43$ which would be returned.
4 References
None.
5 Arguments
 1: $\mathrm{HANDLE}$ – TYPE (C_PTR)Input

On entry: the handle to the problem. It needs to be initialized by
E04RAF and
must not be changed.
 2: $\mathrm{NVAR}$ – INTEGERInput

On entry:
$n$, the number of decision variables
$x$ in the problem. It must be unchanged from the value set during the initialization of the handle by
E04RAF.
 3: $\mathrm{DIMA}$ – INTEGERInput

On entry: $d$, the dimension of the matrices
${A}_{\mathit{i}}$, for $\mathit{i}=0,1,\dots ,{\mathbf{NVAR}}$.
Constraint:
${\mathbf{DIMA}}>0$.
 4: $\mathrm{NNZA}\left({\mathbf{NVAR}}+1\right)$ – INTEGER arrayInput

On entry: ${\mathbf{NNZA}}\left(\mathit{i}+1\right)$, for $\mathit{i}=0,1,\dots ,{\mathbf{NVAR}}$, gives the number of nonzero elements in the upper triangle of matrix ${A}_{i}$. To define ${A}_{i}$ as a zero matrix, set ${\mathbf{NNZA}}\left(i+1\right)=0$. However, there must be at least one matrix with at least one nonzero.
Constraints:
 ${\mathbf{NNZA}}\left(i\right)\ge 0$;
 $\sum _{\mathit{i}=1}^{n+1}}{\mathbf{NNZA}}\left(i\right)\ge 1$.
 5: $\mathrm{NNZASUM}$ – INTEGERInput

On entry: the dimension of the arrays
IROWA,
ICOLA and
A, at least the total number of all nonzeros in all matrices
${A}_{i}$.
Constraints:
 ${\mathbf{NNZASUM}}>0$;
 $\sum _{\mathit{i}=1}^{n+1}}{\mathbf{NNZA}}\left(i\right)\le {\mathbf{NNZASUM}$.
 6: $\mathrm{IROWA}\left({\mathbf{NNZASUM}}\right)$ – INTEGER arrayInput
 7: $\mathrm{ICOLA}\left({\mathbf{NNZASUM}}\right)$ – INTEGER arrayInput
 8: $\mathrm{A}\left({\mathbf{NNZASUM}}\right)$ – REAL (KIND=nag_wp) arrayInput

On entry: nonzero elements in upper triangle of matrices ${A}_{i}$ stored in coordinate storage. The first ${\mathbf{NNZA}}\left(1\right)$ elements belong to ${A}_{0}$, the following ${\mathbf{NNZA}}\left(2\right)$ elements belong to ${A}_{1}$, etc. See explanation above.
Constraints:
 $1\le {\mathbf{IROWA}}\left(i\right)\le {\mathbf{DIMA}}$, ${\mathbf{IROWA}}\left(i\right)\le {\mathbf{ICOLA}}\left(i\right)\le {\mathbf{DIMA}}$;
 IROWA and ICOLA match the block diagonal pattern set by BLKSIZEA.
 9: $\mathrm{NBLK}$ – INTEGERInput

On entry: ${m}_{A}$, number of diagonal blocks in ${A}_{i}$ matrices. As explained above it is equivalent to the number of matrix inequalities supplied in this call.
Constraint:
${\mathbf{NBLK}}\ge 1$.
 10: $\mathrm{BLKSIZEA}\left({\mathbf{NBLK}}\right)$ – INTEGER arrayInput

On entry: if
${\mathbf{NBLK}}>1$, sizes
${d}_{k}$ of the diagonal blocks.
If
${\mathbf{NBLK}}=1$,
BLKSIZEA is not referenced.
Constraints:
 ${\mathbf{BLKSIZEA}}\left(i\right)\ge 1$;
 $\sum _{\mathit{i}=1}^{{m}_{A}}}{\mathbf{BLKSIZEA}}\left(i\right)={\mathbf{DIMA}$.
 11: $\mathrm{IDBLK}$ – INTEGERInput/Output

On entry: if ${\mathbf{IDBLK}}=0$, new matrix inequalities are created. This is the only value allowed at the moment; nonzero values are reserved for future releases of the NAG Library.
Constraint:
${\mathbf{IDBLK}}=0$.
On exit: the number of the last matrix inequality added. By definition, it is the number of the matrix inequalities already defined plus
NBLK.
 12: $\mathrm{IFAIL}$ – INTEGERInput/Output

On entry:
IFAIL must be set to
$0$,
$1\text{ or}1$. If you are unfamiliar with this argument you should refer to
Section 3.4 in How to Use the NAG Library and its Documentation for details.
For environments where it might be inappropriate to halt program execution when an error is detected, the value
$1\text{ or}1$ is recommended. If the output of error messages is undesirable, then the value
$1$ is recommended. Otherwise, the recommended value is
$1$.
When the value $\mathbf{1}\text{ or}1$ is used it is essential to test the value of IFAIL on exit.
On exit:
${\mathbf{IFAIL}}={\mathbf{0}}$ unless the routine detects an error or a warning has been flagged (see
Section 6).
6 Error Indicators and Warnings
If on entry
${\mathbf{IFAIL}}=0$ or
$1$, explanatory error messages are output on the current error message unit (as defined by
X04AAF).
Errors or warnings detected by the routine:
 ${\mathbf{IFAIL}}=1$

The supplied
HANDLE does not define a valid handle to the data structure for the NAG optimization modelling suite. It has not been initialized by
E04RAF or it has been corrupted.
 ${\mathbf{IFAIL}}=2$

The problem cannot be modified in this phase any more, the solver has already been called.
 ${\mathbf{IFAIL}}=4$

On entry, ${\mathbf{IDBLK}}=\u2329\mathit{\text{value}}\u232a$.
Constraint: ${\mathbf{IDBLK}}=0$.
On entry,
${\mathbf{NVAR}}=\u2329\mathit{\text{value}}\u232a$, expected
$\mathrm{value}=\u2329\mathit{\text{value}}\u232a$.
Constraint:
NVAR must match the value given during initialization of
HANDLE.
 ${\mathbf{IFAIL}}=6$

On entry, ${\mathbf{DIMA}}=\u2329\mathit{\text{value}}\u232a$.
Constraint: ${\mathbf{DIMA}}>0$.
On entry, $i=\u2329\mathit{\text{value}}\u232a$ and ${\mathbf{NNZA}}\left(i\right)=\u2329\mathit{\text{value}}\u232a$.
Constraint: ${\mathbf{NNZA}}\left(i\right)\ge 0$.
On entry, ${\mathbf{NNZASUM}}=\u2329\mathit{\text{value}}\u232a$ and $\mathrm{sum}\left({\mathbf{NNZA}}\right)=\u2329\mathit{\text{value}}\u232a$.
Constraint: ${\mathbf{NNZASUM}}\ge \mathrm{sum}\left({\mathbf{NNZA}}\right)$.
On entry, $\mathrm{sum}\left({\mathbf{NNZA}}\right)=\u2329\mathit{\text{value}}\u232a$.
Constraint: $\mathrm{sum}\left({\mathbf{NNZA}}\right)\ge 1$.
 ${\mathbf{IFAIL}}=7$

On entry, ${\mathbf{DIMA}}=\u2329\mathit{\text{value}}\u232a$ and $\mathrm{sum}\left({\mathbf{BLKSIZEA}}\right)=\u2329\mathit{\text{value}}\u232a$.
Constraint: $\mathrm{sum}\left({\mathbf{BLKSIZEA}}\right)={\mathbf{DIMA}}$.
On entry, $i=\u2329\mathit{\text{value}}\u232a$ and ${\mathbf{BLKSIZEA}}\left(i\right)=\u2329\mathit{\text{value}}\u232a$.
Constraint: ${\mathbf{BLKSIZEA}}\left(i\right)\ge 1$.
On entry, ${\mathbf{NBLK}}=\u2329\mathit{\text{value}}\u232a$.
Constraint: ${\mathbf{NBLK}}>0$.
 ${\mathbf{IFAIL}}=8$

An error occurred in matrix ${A}_{i}$, $i=\u2329\mathit{\text{value}}\u232a$ (counting indices $1\dots {\mathbf{NVAR}}+1$).
On entry, $j=\u2329\mathit{\text{value}}\u232a$, ${\mathbf{ICOLA}}\left(j\right)=\u2329\mathit{\text{value}}\u232a$ and ${\mathbf{DIMA}}=\u2329\mathit{\text{value}}\u232a$.
Constraint: $1\le {\mathbf{ICOLA}}\left(j\right)\le {\mathbf{DIMA}}$.
An error occurred in matrix ${A}_{i}$, $i=\u2329\mathit{\text{value}}\u232a$ (counting indices $1\dots {\mathbf{NVAR}}+1$).
On entry, $j=\u2329\mathit{\text{value}}\u232a$, ${\mathbf{IROWA}}\left(j\right)=\u2329\mathit{\text{value}}\u232a$ and ${\mathbf{DIMA}}=\u2329\mathit{\text{value}}\u232a$.
Constraint: $1\le {\mathbf{IROWA}}\left(j\right)\le {\mathbf{DIMA}}$.
An error occurred in matrix ${A}_{i}$, $i=\u2329\mathit{\text{value}}\u232a$ (counting indices $1\dots {\mathbf{NVAR}}+1$).
On entry, $j=\u2329\mathit{\text{value}}\u232a$, ${\mathbf{IROWA}}\left(j\right)=\u2329\mathit{\text{value}}\u232a$ and ${\mathbf{ICOLA}}\left(j\right)=\u2329\mathit{\text{value}}\u232a$.
Constraint: ${\mathbf{IROWA}}\left(\mathit{j}\right)\le {\mathbf{ICOLA}}\left(\mathit{j}\right)$ (elements within the upper triangle).
An error occurred in matrix
${A}_{i}$,
$i=\u2329\mathit{\text{value}}\u232a$ (counting indices
$1\dots {\mathbf{NVAR}}+1$).
On entry,
$j=\u2329\mathit{\text{value}}\u232a$,
${\mathbf{IROWA}}\left(j\right)=\u2329\mathit{\text{value}}\u232a$ and
${\mathbf{ICOLA}}\left(j\right)=\u2329\mathit{\text{value}}\u232a$. Maximum column index in this row given by the block structure defined by
BLKSIZEA is
$\u2329\mathit{\text{value}}\u232a$.
Constraint: all elements of
${A}_{i}$ must respect the block structure given by
BLKSIZEA.
An error occurred in matrix ${A}_{i}$, $i=\u2329\mathit{\text{value}}\u232a$ (counting indices $1\dots {\mathbf{NVAR}}+1$).
On entry, more than one element of ${A}_{i}$ has row index $\u2329\mathit{\text{value}}\u232a$ and column index $\u2329\mathit{\text{value}}\u232a$.
Constraint: each element of ${A}_{i}$ must have a unique row and column index.
 ${\mathbf{IFAIL}}=99$
An unexpected error has been triggered by this routine. Please
contact
NAG.
See
Section 3.9 in How to Use the NAG Library and its Documentation for further information.
 ${\mathbf{IFAIL}}=399$
Your licence key may have expired or may not have been installed correctly.
See
Section 3.8 in How to Use the NAG Library and its Documentation for further information.
 ${\mathbf{IFAIL}}=999$
Dynamic memory allocation failed.
See
Section 3.7 in How to Use the NAG Library and its Documentation for further information.
7 Accuracy
Not applicable.
8 Parallelism and Performance
E04RNF is not threaded in any implementation.
The following example demonstrates how the elements of the
${A}_{i}^{k}$ matrices are organized within the input arrays. Let us assume that there are two blocks defined (
${\mathbf{NBLK}}=2$). The first has dimension
$3$ by
$3$ (
${\mathbf{BLKSIZEA}}\left(1\right)=3$) and the second
$2$ by
$2$ (
${\mathbf{BLKSIZEA}}\left(2\right)=2$). For simplicity, the number of variables is
$2$. Please note that the values were chosen to ease orientation rather than to define a valid problem.
Both inequalities will be passed in a single call to E04RNF, therefore the matrices are merged into the following block diagonal form:
All matrices are symmetric and therefore only the upper triangles are passed to the routine. The coordinate storage format is used. Note that elements within the same matrix do not need to be in any specific order. The table below shows one of the ways the arrays could be populated.
IROWA 
$\begin{array}{ccccc}\phantom{0.}2\hfill & \phantom{0.}2\hfill & \phantom{0.}4\hfill & \phantom{0.}1\hfill & \phantom{0.}1\hfill \end{array}$ 
$\begin{array}{cc}\phantom{0.}4& \phantom{0.}5\end{array}$ 
$\begin{array}{cccccc}\phantom{0.}1& \phantom{0.}2& \phantom{0.}3& \phantom{0.}4& \phantom{0.}4& \phantom{0.}5\end{array}$ 
ICOLA 
$\begin{array}{ccccc}\phantom{0.}2& \phantom{0.}3& \phantom{0.}5& \phantom{0.}1& \phantom{0.}3\end{array}$ 
$\begin{array}{cc}\phantom{0.}4& \phantom{0.}5\end{array}$ 
$\begin{array}{cccccc}\phantom{0.}1& \phantom{0.}2& \phantom{0.}3& \phantom{0.}4& \phantom{0.}5& \phantom{0.}5\end{array}$ 
A 
$\underbrace{\begin{array}{ccccc}0.2& 0.4& 0.1& 0.1& 0.3\end{array}}$ 
$\underbrace{\begin{array}{cc}1.1& 1.2\end{array}}$ 
$\underbrace{\begin{array}{cccccc}2.1& 2.2& 2.3& 2.1& 2.2& 2.3\end{array}}$ 

${A}_{0}$ 
${A}_{1}$ 
${A}_{2}$ 
NNZA 
$5$ 
$2$ 
$6$ 
10 Example
There are various problems which can be successfully reformulated and solved as an SDP problem. The following example shows how a maximization of the minimal eigenvalue of a matrix depending on certain parameters can be utilized in statistics.
For further examples, please refer to
Section 10 in E04RAF.
Given a series of
$M$ vectors of length
$p$,
$\left\{{v}_{i}:i=1,2,\dots ,M\right\}$ this example solves the SDP problem:
This formulation comes from an area of statistics called experimental design and corresponds to finding an approximate $E$ optimal design for a linear regression.
A linear regression model has the form:
where
$y$ is a vector of observed values,
$X$ is a design matrix of (known) independent variables and
$\epsilon $ is a vector of errors. In experimental design it is assumed that each row of
$X$ is chosen from a set of
$M$ possible vectors,
$\left\{{v}_{i}:i=1,2,\dots ,M\right\}$. The goal of experimental design is to choose the rows of
$X$ so that the error covariance is ‘small’. For an
$E$ optimal design this is defined as the
$X$ that maximizes the minimum eigenvalue of
${X}^{\mathrm{T}}X$.
In this example we construct the
$E$ optimal design for a polynomial regression model of the form:
where
$x\in \left\{1j\times 0.05:j=0,1,\dots ,40\right\}$.
10.1 Program Text
Program Text (e04rnfe.f90)
10.2 Program Data
Program Data (e04rnfe.d)
10.3 Program Results
Program Results (e04rnfe.r)