nag_opt_handle_set_linmatineq (e04rnc) is a part of the NAG optimization modelling suite and defines one or more linear matrix constraints of the problem.

2

Specification

#include <nag.h>

#include <nage04.h>

void	nag_opt_handle_set_linmatineq (void handle, Integer nvar, Integer dima, const Integer nnza[], Integer nnzasum, const Integer irowa[], const Integer icola[], const double a[], Integer nblk, const Integer blksizea[], Integer idblk, NagError *fail)

3

Description

After the initialization function nag_opt_handle_init (e04rac) has been called, nag_opt_handle_set_linmatineq (e04rnc) may be used to add one or more linear matrix inequalities

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

(1)

to the problem definition. Here

A_{i}

are

d

d

symmetric matrices. The expression

S ⪰ 0

stands for a constraint on eigenvalues of a symmetric matrix

S

, namely, all the eigenvalues should be non-negative, i.e., the matrix

S

should be positive semidefinite.

Typically, this will be used in linear semidefinite programming problems (SDP)

\begin{array}{l} \underset{x \in ℝ^{n}}{minimize} & c^{T} x & (a) \\ subject to & \sum_{i = 1}^{n} x_{i} A_{i}^{k} - A_{0}^{k} ⪰ 0, k = 1, \dots, m_{A} & (b) \\ l_{B} \leq B x \leq u_{B} & (c) \\ l_{x} \leq x \leq u_{x} & (d) \end{array}

(2)

or to define the linear part of bilinear matrix inequalities (3)(b) in (BMI-SDP)

\begin{array}{l} \underset{x \in ℝ^{n}}{minimize} & \frac{1}{2} x^{T} H x + c^{T} x & (a) \\ subject to & \sum_{i,j = 1}^{n} x_{i} x_{j} Q_{i j}^{k} + \sum_{i = 1}^{n} x_{i} A_{i}^{k} - A_{0}^{k} ⪰ 0, k = 1, \dots, m_{A} & (b) \\ l_{B} \leq B x \leq u_{B} & (c) \\ l_{x} \leq x \leq u_{x} & (d) \end{array}

(3)

nag_opt_handle_set_linmatineq (e04rnc) can be called repeatedly to accumulate more matrix inequalities. See nag_opt_handle_init (e04rac) for more details.

3.1

Input data organization

All the matrices

A_{i}

, for

i = 0, 1, \dots, n

, are symmetric and thus only their upper triangles are passed to the function. 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 function 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

nnza [i]

, 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 nag_opt_sdp_read_sdpa (e04rdc) which uses the same data organization.

irowa	upper triangle	upper triangle		upper triangle
icola	nonzeros	nonzeros	$\dots$	nonzeros
a	$\underset{︸}{from A_{0}}$	$\underset{︸}{from A_{1}}$		$\underset{︸}{from A_{n}}$
	$nnza [0]$	$nnza [1]$		$nnza [n]$

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

\sum_{i = 1}^{n} x_{i} A_{i}^{k} - A_{0}^{k} ⪰ 0, k = 1, 2, \dots, m_{A}

(4)

to the problem. The first is to call nag_opt_handle_set_linmatineq (e04rnc)

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 nag_opt_handle_set_linmatineq (e04rnc). It is easy to see that (4) can be equivalently expressed as one bigger matrix inequality with the following block diagonal structure

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

d_{k}

denotes the dimension of inequality

k

, the new merged inequality has dimension

d = \sum_{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

blksizea [k - 1]

d_{k}

, the size of the

k

th diagonal blocks. This might be useful in connection with nag_opt_sdp_read_sdpa (e04rdc).

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)

nag_opt_handle_set_linmatineq (e04rnc) is designed to be used together with nag_opt_handle_set_quadmatineq (e04rpc) to define bilinear matrix inequalities (3)(b). nag_opt_handle_set_linmatineq (e04rnc) sets the linear part of the constraint and nag_opt_handle_set_quadmatineq (e04rpc) expands it by higher order terms. To distinquish which linear matrix inequality (or more precisely, which block) is to be expanded, nag_opt_handle_set_quadmatineq (e04rpc) 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 function 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

idblk = 1

, the second one

idblk = 2

, etc. Therefore if you call nag_opt_handle_set_linmatineq (e04rnc) for the very first time with

nblk = 42

, it adds

42

inequalities with idblk from

1

42

and the function returns

idblk = 42

(the number of the last one). A subsequent call with

nblk = 1

would add only one inequality, this time with

idblk = 43

which would be returned.

4

References

None.

5

Arguments

1: $handle$ – void *Input

On entry: the handle to the problem. It needs to be initialized by nag_opt_handle_init (e04rac) and must not be changed.

2: $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 nag_opt_handle_init (e04rac).

3: $dima$ – IntegerInput

On entry:

d

, the dimension of the matrices

A_{i}

, for

i = 0, 1, \dots, nvar

Constraint:

dima > 0

4: $nnza [nvar + 1]$ – const IntegerInput

On entry:

nnza [i]

, for

i = 0, 1, \dots, nvar

, gives the number of nonzero elements in the upper triangle of matrix

A_{i}

. To define

A_{i}

as a zero matrix, set

nnza [i] = 0

. However, there must be at least one matrix with at least one nonzero.

Constraints:

$nnza [i - 1] \geq 0$ ;
$\sum_{i = 1}^{n + 1} nnza [i - 1] \geq 1$ .

5: $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:

$nnzasum > 0$ ;
$\sum_{i = 1}^{n + 1} nnza [i - 1] \leq nnzasum$ .

6: $irowa [nnzasum]$ – const IntegerInput

7: $icola [nnzasum]$ – const IntegerInput

8: $a [nnzasum]$ – const doubleInput

On entry: nonzero elements in upper triangle of matrices

A_{i}

stored in coordinate storage. The first

nnza [0]

elements belong to

A_{0}

, the following

nnza [1]

elements belong to

A_{1}

, etc. See explanation above.

Constraints:

$1 \leq irowa [i - 1] \leq dima$ , $irowa [i - 1] \leq icola [i - 1] \leq dima$ ;
irowa and icola match the block diagonal pattern set by blksizea.

9: $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:

nblk \geq 1

10: $blksizea [nblk]$ – const IntegerInput

On entry: if

nblk > 1

, sizes

d_{k}

of the diagonal blocks.

nblk = 1

, blksizea is not referenced and may be NULL.

Constraints:

$blksizea [i - 1] \geq 1$ ;
$\sum_{i = 1}^{m_{A}} blksizea [i - 1] = dima$ .

11: $idblk$ – Integer *Input/Output

On entry: if

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 C Library.

Constraint:

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: $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_HANDLE: 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 nag_opt_handle_init (e04rac) or it has been corrupted.
NE_INT: On entry, $dima = 〈value〉$ .
Constraint: $dima > 0$ .

On entry, $nblk = 〈value〉$ .
Constraint: $nblk > 0$ .
NE_INT_2: On entry, $nnzasum = 〈value〉$ and $sum (nnza) = 〈value〉$ .
Constraint: $nnzasum \geq sum (nnza)$ .
NE_INT_ARRAY_1: On entry, $i = 〈value〉$ and $nnza [i - 1] = 〈value〉$ .
Constraint: $nnza [i - 1] \geq 0$ .

On entry, $sum (nnza) = 〈value〉$ .
Constraint: $sum (nnza) \geq 1$ .
NE_INT_ARRAY_2: On entry, $i = 〈value〉$ and $blksizea [i - 1] = 〈value〉$ .
Constraint: $blksizea [i - 1] \geq 1$ .
NE_INTARR_INT: On entry, $dima = 〈value〉$ and $sum (blksizea) = 〈value〉$ .
Constraint: $sum (blksizea) = dima$ .
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: An error occurred in matrix $A_{i}$ , $i = 〈value〉$ (counting indices $1 \dots nvar + 1$ ).
On entry, $j = 〈value〉$ , $icola [j - 1] = 〈value〉$ and $dima = 〈value〉$ .
Constraint: $1 \leq icola [j - 1] \leq dima$ .

An error occurred in matrix $A_{i}$ , $i = 〈value〉$ (counting indices $1 \dots nvar + 1$ ).
On entry, $j = 〈value〉$ , $irowa [j - 1] = 〈value〉$ and $dima = 〈value〉$ .
Constraint: $1 \leq irowa [j - 1] \leq dima$ .

An error occurred in matrix $A_{i}$ , $i = 〈value〉$ (counting indices $1 \dots nvar + 1$ ).
On entry, $j = 〈value〉$ , $irowa [j - 1] = 〈value〉$ and $icola [j - 1] = 〈value〉$ .
Constraint: $irowa [j - 1] \leq icola [j - 1]$ (elements within the upper triangle).

An error occurred in matrix $A_{i}$ , $i = 〈value〉$ (counting indices $1 \dots nvar + 1$ ).
On entry, $j = 〈value〉$ , $irowa [j - 1] = 〈value〉$ and $icola [j - 1] = 〈value〉$ . Maximum column index in this row given by the block structure defined by blksizea is $〈value〉$ .
Constraint: all elements of $A_{i}$ must respect the block structure given by blksizea.

An error occurred in matrix $A_{i}$ , $i = 〈value〉$ (counting indices $1 \dots nvar + 1$ ).
On entry, more than one element of $A_{i}$ has row index $〈value〉$ and column index $〈value〉$ .
Constraint: each element of $A_{i}$ must have a unique row and column index.
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_PHASE: The problem cannot be modified in this phase any more, the solver has already been called.
NE_REF_MATCH: On entry, $idblk = 〈value〉$ .
Constraint: $idblk = 0$ .

On entry, $nvar = 〈value〉$ , expected $value = 〈value〉$ .
Constraint: nvar must match the value given during initialization of handle.

7

Accuracy

Not applicable.

8

Parallelism and Performance

nag_opt_handle_set_linmatineq (e04rnc) is not threaded in any implementation.

9

Further Comments

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 (

nblk = 2

). The first has dimension

3

3

(

blksizea [0] = 3

) and the second

2

2

(

blksizea [1] = 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.

\begin{array}{r} A_{0}^{1} = (\begin{array}{r} 0.1 & 0 & 0.3 \\ 0 & 0.2 & 0.4 \\ 0.3 & 0.4 & 0 \end{array}), & A_{1}^{1} ​ empty ​ & A_{2}^{1} = (\begin{array}{r} 2.1 & 0 & 0 \\ 0 & 2.2 & 0 \\ 0 & 0 & 2.3 \end{array}), \\ A_{0}^{2} = (\begin{array}{r} 0 & - 0.1 \\ - 0.1 & 0 \end{array}), & A_{1}^{2} = (\begin{array}{r} - 1.1 & 0 \\ 0 & - 1.2 \end{array}), & A_{2}^{2} = (\begin{array}{r} - 2.1 & - 2.2 \\ - 2.2 & - 2.3 \end{array}) . \end{array}

Both inequalities will be passed in a single call to nag_opt_handle_set_linmatineq (e04rnc), therefore the matrices are merged into the following block diagonal form:

A_{0} = (\begin{array}{r} 0.1 & 0 & 0.3 \\ 0 & 0.2 & 0.4 \\ 0.3 & 0.4 & 0 \\ 0 & - 0.1 \\ - 0.1 & 0 \end{array}),

A_{1} = (\begin{array}{r} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ - 1.1 & 0 \\ 0 & - 1.2 \end{array}),

A_{2} = (\begin{array}{r} 2.1 & 0 & 0 \\ 0 & 2.2 & 0 \\ 0 & 0 & 2.3 \\ - 2.1 & - 2.2 \\ - 2.2 & - 2.3 \end{array}) .

All matrices are symmetric and therefore only the upper triangles are passed to the function. 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{matrix} 2 & 2 & 4 & 1 & 1 \end{matrix}$	$\begin{matrix} 4 & 5 \end{matrix}$	$\begin{matrix} 1 & 2 & 3 & 4 & 4 & 5 \end{matrix}$
icola	$\begin{matrix} 2 & 3 & 5 & 1 & 3 \end{matrix}$	$\begin{matrix} 4 & 5 \end{matrix}$	$\begin{matrix} 1 & 2 & 3 & 4 & 5 & 5 \end{matrix}$
a	$\underset{︸}{\begin{matrix} 0.2 & 0.4 & - 0.1 & 0.1 & 0.3 \end{matrix}}$	$\underset{︸}{\begin{matrix} - 1.1 & - 1.2 \end{matrix}}$	$\underset{︸}{\begin{matrix} 2.1 & 2.2 & 2.3 & - 2.1 & - 2.2 & - 2.3 \end{matrix}}$
	$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 nag_opt_handle_init (e04rac).

Given a series of

M

vectors of length

p

\{v_{i} : i = 1, 2, \dots, M\}

this example solves the SDP problem:

\begin{array}{l} \underset{λ_{1}, \dots, λ_{M}, t}{maximize} & t \\ subject to & \sum_{i = 1}^{M} λ_{i} v_{i} v_{i}^{T} ⪰ t I \\ \sum_{i = 1}^{M} λ_{i} = 1 \\ λ_{i} \geq 0, k = 1, \dots, M . \end{array}

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:

y = X β + ε

where

y

is a vector of observed values,

X

is a design matrix of (known) independent variables and

ε

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,

\{v_{i} : i = 1, 2, \dots, M\}

. 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^{T} X

In this example we construct the

E

optimal design for a polynomial regression model of the form:

y = β_{0} + β_{1} x + β_{2} x^{2} + β_{3} x^{3} + β_{4} x^{4} + ε

where

x \in \{1 - j \times 0.05 : j = 0, 1, \dots, 40\}

NAG Library Function Document

nag_opt_handle_set_linmatineq (e04rnc)

▸▿ Contents

1 Purpose

2 Specification

3 Description

3.1 Input data organization

3.2 Definition of Bilinear Matrix Inequalities (BMI)

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

Input data organization

3.2

Definition of Bilinear Matrix Inequalities (BMI)

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