NAG C Library Function Document

nag_opt_handle_set_quadmatineq (e04rpc) is a part of the NAG optimization modelling suite and defines bilinear matrix terms either in a new matrix constraint or adds them to an existing linear matrix inequality.

2

Specification

#include <nag.h>

#include <nage04.h>

void	nag_opt_handle_set_quadmatineq (void handle, Integer nq, const Integer qi[], const Integer qj[], Integer dimq, const Integer nnzq[], Integer nnzqsum, const Integer irowq[], const Integer icolq[], const double q[], Integer idblk, NagError *fail)

3

Description

After the initialization function nag_opt_handle_init (e04rac) has been called, nag_opt_handle_set_quadmatineq (e04rpc) may be used to define bilinear matrix terms. It may be used in two ways, either to add to the problem formulation a new bilinear matrix inequality (BMI) which does not have linear terms:

\sum_{i,j = 1}^{n} x_{i} x_{j} Q_{i j} ⪰ 0

(1)

or to extend an existing linear matrix inequality constraint by bilinear terms:

\sum_{i,j = 1}^{n} x_{i} x_{j} Q_{i j}^{k} .

(2)

Here

Q_{i j}^{k}

are

d

d

(sparse) symmetric matrices and

k

, if present, is the number of the existing constraint. This function will typically be used on semidefinite programming problems with bilinear matrix constraints (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)

The function can be called multiple times to define an additional matrix inequality or to extend an existing one, but it cannot be called twice to extend the same matrix inequality. The argument idblk is used to distinguish whether a new matrix constraint should be added (

idblk = 0

) or if an existing linear matrix inequality should be extended (

idblk > 0

). In the latter case, idblk should be set to

k

, the number of the existing inequality. See nag_opt_handle_set_linmatineq (e04rnc) for details about formulation of linear matrix constraints and their numbering and a further description of idblk. For a generic description of the problem see nag_opt_handle_init (e04rac). In the further text, the index

k

will be omitted.

3.1

Input data organization

It is expected that only some of the matrices

Q_{i j}

will be nonzero therefore only their index pairs

i, j

are listed in arrays qi and qj. Note that a pair

i, j

should not repeat, i.e., a matrix

Q_{i j}

should not be defined more than once. No particular ordering of pairs

i, j

is expected but other input arrays irowq, icolq, q and nnzq need to respect the chosen order.

Note: the dimension of

Q_{i j}

must respect the size of the linear matrix inequality if they are supposed to expand it (case

idblk > 0

Matrices

Q_{i j}

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. All these triplets from all

Q_{i j}

matrices are passed to the function in three arrays: irowq for row indices, icolq for column indices and q for the values. No particular order of nonzeros within one matrix is enforced but all nonzeros belonging to one

Q_{i j}

matrix need to be stored next to each other. The first

nnzq [0]

nonzeros belong to

Q_{i_{1} j_{1}}

where

i_{1} = qi [0]

j_{1} = qj [0]

, the following

nnzq [1]

nonzeros to the next one given by qi, qj and so on. The array nnzq thus splits arrays irowq, icolq and q into sections so that each section defines one

Q_{i j}

matrix. See Table 1 below. Functions nag_opt_sdp_read_sdpa (e04rdc) and nag_opt_handle_set_linmatineq (e04rnc) use the same data organization so further examples can be found there.

irowq	upper triangle	upper triangle		upper triangle
icolq	nonzeros	nonzeros	$\dots$	nonzeros
q	$\underset{︸}{from Q_{i_{1} j_{1}}}$	$\underset{︸}{from Q_{i_{2} j_{2}}}$		$\underset{︸}{from Q_{i_{nq} j_{nq}}}$
	$nnzq [0]$	$nnzq [1]$		$nnzq [nq - 1]$
	$i_{1} = qi [0]$	$i_{2} = qi [1]$		$i_{nq} = qi [nq - 1]$
	$j_{1} = qj [0]$	$j_{2} = qj [1]$		$j_{nq} = qj [nq - 1]$

Table 1
Coordinate storage format of

Q_{i j}

matrices in input arrays

4

References

Syrmos V L, Abdallah C T, Dorato P and Grigoriadis K (1997) Static output feedback – a survey Journal Automatica (Journal of IFAC) (Volume 33) 2 125–137

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: $nq$ – IntegerInput

On entry: the number of index pairs

i, j

of the nonzero matrices

Q_{i j}

Constraint:

nq > 0

3: $qi [nq]$ – const IntegerInput

4: $qj [nq]$ – const IntegerInput

On entry: the index pairs

i, j

of the nonzero matrices

Q_{i j}

in any order.

Constraint:

1 \leq i, j \leq n

where

n

is the number of decision variables in the problem set during the initialization of the handle by nag_opt_handle_init (e04rac). The pairs do not repeat.

5: $dimq$ – IntegerInput

On entry:

d

, the dimension of matrices

Q_{i j}

Constraints:

$dimq > 0$ ;
if $idblk > 0$ , dimq needs to be identical to the dimension of matrices of the constraint $k$ .

6: $nnzq [nq]$ – const IntegerInput

On entry: the numbers of nonzero elements in the upper triangles of

Q_{i j}

matrices.

Constraint:

nnzq [i - 1] > 0

7: $nnzqsum$ – IntegerInput

On entry: the dimension of the arrays irowq, icolq and q, at least the total number of all nonzeros in all

Q_{i j}

matrices.

Constraints:

$nnzqsum > 0$ ;
$nnzqsum \geq \sum_{k = 1}^{nq} nnzq [k - 1]$ .

8: $irowq [nnzqsum]$ – const IntegerInput

9: $icolq [nnzqsum]$ – const IntegerInput

10: $q [nnzqsum]$ – const doubleInput

On entry: the nonzero elements of the upper triangles of matrices

Q_{i j}

stored in coordinate storage format. The first

nnzq [0]

elements belong to the first

Q_{i_{1} j_{1}}

, the following

nnzq [1]

Q_{i_{2} j_{2}}

, etc.

Constraint:

1 \leq irowq [i - 1] \leq dimq

irowq [i - 1] \leq icolq [i - 1] \leq dimq

11: $idblk$ – Integer *Input/Output

On entry: if

idblk = 0

, a new matrix constraint is created; otherwise

idblk = k > 0

, the number of the existing linear matrix constraint to be expanded with the bilinear terms.

Constraint:

idblk \geq 0

On exit: if

idblk = 0

on entry, the number of the new matrix constraint is returned. By definition, it is the number of the matrix inequalities already defined plus one. Otherwise,

idblk > 0

stays unchanged.

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_ALREADY_DEFINED: On entry, $idblk = 〈value〉$ .
Bilinear terms of the matrix inequality block with the given idblk have already been defined.
NE_BAD_PARAM: On entry, argument $〈value〉$ had an illegal value.
NE_DIM_MATCH: On entry, $dimq = 〈value〉$ , $idblk = 〈value〉$ .
The correct dimension of the given idblk is $〈value〉$ .
Constraint: dimq must match the dimension of the block supplied earlier.
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_INDICES: On entry, index pair with $qi = 〈value〉$ and $qj = 〈value〉$ repeats.
Constraint: each index pair qi, qj must be unique.

On entry, $k = 〈value〉$ , $qi [k - 1] = 〈value〉$ and $n = 〈value〉$ .
Constraint: $1 \leq qi [k - 1] \leq n$ .

On entry, $k = 〈value〉$ , $qj [k - 1] = 〈value〉$ and $n = 〈value〉$ .
Constraint: $1 \leq qj [k - 1] \leq n$ .
NE_INT: On entry, $dimq = 〈value〉$ .
Constraint: $dimq > 0$ .

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

On entry, $nq = 〈value〉$ .
Constraint: $nq > 0$ .
NE_INT_2: On entry, $nnzqsum = 〈value〉$ and $sum (nnzq) = 〈value〉$ .
Constraint: $nnzqsum \geq sum (nnzq)$ .
NE_INT_ARRAY_1: On entry, $i = 〈value〉$ and $nnzq [i - 1] = 〈value〉$ .
Constraint: $nnzq [i - 1] > 0$ .
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: On entry, an error occurred in matrix $Q_{i j}$ of index $k = 〈value〉$ , $qi [k - 1] = 〈value〉$ , $qj [k - 1] = 〈value〉$ .
For $j = 〈value〉$ , $icolq [j - 1] = 〈value〉$ and $dimq = 〈value〉$ .
Constraint: $1 \leq icolq [j - 1] \leq dimq$ .

On entry, an error occurred in matrix $Q_{i j}$ of index $k = 〈value〉$ , $qi [k - 1] = 〈value〉$ , $qj [k - 1] = 〈value〉$ .
For $j = 〈value〉$ , $irowq [j - 1] = 〈value〉$ and $dimq = 〈value〉$ .
Constraint: $1 \leq irowq [j - 1] \leq dimq$ .

On entry, an error occurred in matrix $Q_{i j}$ of index $k = 〈value〉$ , $qi [k - 1] = 〈value〉$ , $qj [k - 1] = 〈value〉$ .
For $j = 〈value〉$ , $irowq [j - 1] = 〈value〉$ and $icolq [j - 1] = 〈value〉$ .
Constraint: $irowq [j - 1] \leq icolq [j - 1]$ (elements within the upper triangle).

On entry, an error occurred in matrix $Q_{i j}$ of index $k = 〈value〉$ , $qi [k - 1] = 〈value〉$ , $qj [k - 1] = 〈value〉$ .
More than one element of $Q_{i j}$ has row index $〈value〉$ and column index $〈value〉$ .
Constraint: each element of $Q_{i j}$ 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〉$ .
The given idblk does not match with any existing matrix inequality block.
The maximum idblk is currently $〈value〉$ .

On entry, $idblk = 〈value〉$ .
The given idblk refers to a nonexistent matrix inequality block.
No matrix inequalities have been added yet.

7

Accuracy

Not applicable.

8

Parallelism and Performance

nag_opt_handle_set_quadmatineq (e04rpc) is not threaded in any implementation.

9

Further Comments

None.

10

Example

This example demonstrates how semidefinite programming can be used in control theory. See also Section 10 in nag_opt_handle_init (e04rac) for links to further examples in the suite.

The problem, from static output feedback (SOF) control Syrmos et al. (1997), solved here is the linear time-invariant (LTI) ‘test’ system

\begin{matrix} \dot{x} = A x + B u \\ y = C x \end{matrix}

(4)

subject to static output feedback

u = K y .

(5)

Here

A \in ℝ^{n \times n}

B \in ℝ^{n \times m}

and

C \in ℝ^{p \times n}

are given matrices,

x \in ℝ^{n}

is the vector of state variables,

u \in ℝ^{m}

is the vector of control inputs,

y \in ℝ^{p}

is the vector of system outputs, and

K \in ℝ^{m \times p}

is the unknown feedback gain matrix.

The problem is to find

K

such that (4) is time-stable when subject to (5), i.e., all eigenvalues of the closed-loop system matrix

A + B K C

belong to the left half-plane. From the Lyapunov stability theory, this holds if and only if there exists a symmetric positive definite matrix

P

such that

{(A + B K C)}^{T} P + P (A + B K C) ≺ 0 .

Hence, by introducing the new variable, the Lyapunov matrix

P

, we can formulate the SOF problem as a feasibility BMI-SDP problem in variables

K

and

P

. As we cannot formulate the problem with sharp matrix inequalities, we can solve the following system instead (note that the objective function is added to bound matrix

P

\begin{array}{l} \underset{K, P}{minimize} & trace (P) \\ subject to & {(A + B K C)}^{T} P + P (A + B K C) ⪯ - I \\ P ⪰ I . \end{array}

(6)

For

n = p = 2

m = 1

A = (\begin{array}{r} - 1 & 2 \\ - 3 & - 4 \end{array}), B = (\begin{matrix} - 1 \\ - 1 \end{matrix}), C = I

and the unknown matrices expressed as

P = (\begin{matrix} x_{1} & x_{2} \\ x_{2} & x_{3} \end{matrix}), K = (\begin{matrix} x_{4} & x_{5} \end{matrix}),

the problem (6) can be rewritten in the form (3) as follows:

\begin{array}{l} \underset{x \in ℝ^{5}}{minimize} & x_{1} + x_{3} \\ subject to & (\begin{array}{r} 2 x_{1} x_{4} + 2 x_{2} x_{4} & x_{1} x_{5} + x_{2} x_{4} + x_{2} x_{5} + x_{3} x_{4} \\ sym. & 2 x_{2} x_{5} + 2 x_{3} x_{5} \end{array}) + \\ (\begin{array}{r} 2 x_{1} + 6 x_{2} & - 2 x_{1} + 5 x_{2} + 3 x_{3} \\ sym. & - 4 x_{2} + 8 x_{3} \end{array}) - I ⪰ 0 \\ (\begin{matrix} x_{1} & x_{2} \\ sym. & x_{3} \end{matrix}) - I ⪰ 0 . \end{array}

This formulation has been stored in a generic BMI-SDP data file which is processed and solved by the example program.

NAG C Library Function Document

nag_opt_handle_set_quadmatineq (e04rpc)

▸▿ Contents

1 Purpose

2 Specification

3 Description

3.1 Input data organization

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

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