NAG Library Routine Document

e04raf initializes a data structure for the NAG optimization modelling suite for problems such as, linear programming (LP), quadratic programming (QP), nonlinear programming (NLP), least squares (LSQ) problems, linear semidefinite programming (SDP) and semidefinite programming with bilinear matrix inequalities (BMI-SDP).

2

Specification

Fortran Interface

Subroutine e04raf (

handle, nvar, ifail)

Integer, Intent (In)	::	nvar
Integer, Intent (Inout)	::	ifail
Type (c_ptr), Intent (Out)	::	handle

C Header Interface

#include <nagmk26.h>

void	e04raf_ (void *handle, const Integer nvar, Integer *ifail)

3

Description

e04raf initializes an empty problem with

n

decision variables,

x

, and returns a handle to the data structure. This handle may then be passed to some of the routines e04ref, e04rff, e04rgf, e04rhf, e04rjf, e04rkf, e04rlf, e04rmf, e04rnf and e04rpf to formulate the problem (define the objective function and constraints) and to a compatible solver, e04fff, e04mtf, e04stf or e04svf, to solve it. The handle must not be changed between calls. When the handle is no longer needed, e04rzf must be called to destroy it and deallocate all the allocated memory and data within. In addition, the suite comprises auxiliary routines for extracting or providing information to the handle (e04rxf), for printing (e04ryf), for setting optional parameters (e04zmf and e04zpf), for retrieving them (e04znf) and for reading data files for linear semidefinite programming (e04rdf).

The handle can store various problem formulations, including linear programming (LP)

\begin{array}{l} \underset{x \in ℝ^{n}}{minimize} & c^{T} x & (a) \\ subject to & l_{B} \leq B x \leq u_{B} & (b) \\ l_{x} \leq x \leq u_{x}, & (c) \end{array}

(1)

quadratic programming (QP)

\begin{array}{l} \underset{x \in ℝ^{n}}{minimize} & \frac{1}{2} x^{T} H x + c^{T} x & (a) \\ subject to & l_{B} \leq B x \leq u_{B} & (b) \\ l_{x} \leq x \leq u_{x}, & (c) \end{array}

(2)

nonlinear programming (NLP)

\begin{array}{l} \underset{x \in ℝ^{n}}{minimize} & f (x) & (a) \\ subject to & l_{g} \leq g (x) \leq u_{g} & (b) \\ l_{B} \leq B x \leq u_{B} & (c) \\ l_{x} \leq x \leq u_{x} & (d) \end{array}

(3)

least squares (LSQ) problems

\begin{array}{l} \underset{x \in ℝ^{n}}{minimize} & \sum_{i = 1}^{m_{r}} {r_{i} (x)}^{2} & (a) \\ subject to & l_{x} \leq x \leq u_{x}, & (b) \end{array}

(4)

linear semidefinite programming (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}

(5)

or semidefinite programming with bilinear matrix inequalities (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}

(6)

where

H

A_{i}^{k}

and

Q_{i j}^{k}

denote symmetric matrices,

B

is a general rectangular matrix,

m_{A}

is the number of semidefinite constraints (matrix inequalities) and

c

l

and

u

are vectors. 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.

3.1

Life Cycle of the Handle

Each handle should pass four stages in its life as depicted in the diagram below. These are initialization, problem formulation, problem solution and deallocation. The initialization by e04raf and deallocation by e04rzf mark the beginning and the end of the life of the handle. During this time the handle must only be modified by the provided routines. Working with a handle which has not been properly initialized will result in

ifail = 1

(uniform across the suite) and is potentially very dangerous as it may cause unpredictable behaviour.

After the handle has been initialized, various routines are provided to add the following basic building blocks to the problem formulation: objective function, simple variable bounds, (standard) linear and nonlinear constraints and matrix constraints. Some of these can be defined at most once (e.g., objective function) and an attempt to redefine them will return

ifail = 3

. Others (matrix constraints) may be composed using several repetitive calls. The routines work in tight cooperation and if the provided data is not compatible with the previous information,

ifail = 4

is returned.

The handle may be passed to one of the following routines to define the objective function:

e04ref – a linear objective (such as (1)(a) or (5)(a)) as a dense vector;
e04rff – a quadratic objective or a spare linear objective, such as (1)(a) or (2)(a);
e04rgf – a nonlinear objective function (3)(a);
e04rmf – a nonlinear least squares objective function (4)(a).

Only one objective may be defined. If none of them are used the problem will find a feasible point satisfying the constraints.

The routines for constraint definition are:

e04rhf – simple bounds (box constraints), such as (1)(c) or (2)(c);
e04rjf – linear constraints, such as (1)(b) or (2)(b);
e04rkf – nonlinear constraints (3)(b);
e04rlf – second derivatives for the objective and/or constraints;
e04rnf – linear matrix inequalities (5)(b) or the linear part of bilinear matrix inequalities (6)(b);
e04rpf – quadratic terms for bilinear matrix inequalities in (6)(b).

These routines may be called in an arbitrary order, however, a call to e04rnf must precede a call to e04rpf for the matrix inequalities with bilinear terms and the nonlinear objective or constraints (e04rgf or e04rkf) must precede the definition of the second derivatives by e04rlf. A call to e04rnf can be repeated several times if more matrix inequality constraints are required.

When the problem is fully formulated, the handle can be passed to a solver which is compatible with the defined problem. The NAG optimization modelling suite comprises of e04fff, e04mtf, e04stf and e04svf. If the solver cannot deal with the given problem,

ifail = 2

is returned. Once the solver is called, no further modifications of the problem formulation are allowed and calling any of the routines defining the objective function or the constraints will return

ifail = 2

. The solver may be called repetitively, for example, with various optional parameters and/or starting points.

Any optional parameters may be set by a call to e04zmf at any time between the initialization by e04raf and the call to the solver or after the solver returns. Several optional parameters can be modified at once by e04zpf when an option file is used. The current value of the optional parameters may be retrieved by e04znf.

For further details, see the documentation of the individual routines and the solvers which also contain a description of all the optional parameters.

Figure 1

4

References

None.

5

Arguments

1: $handle$ – Type (c_ptr)Output: Note: handle does not need to be set on input.

On exit: holds a handle to the internal data structure where an empty problem with nvar variables is defined. You must not change the handle until the call to e04rzf (deallocation).
2: $nvar$ – IntegerInput: On entry: $n$ , the number of decision variables in the problem.

Constraint: $nvar > 0$ .
3: $ifail$ – IntegerInput/Output: On entry: ifail must be set to $0$ , $- 1 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 or 1$ is recommended. If the output of error messages is undesirable, then the value $1$ is recommended. Otherwise, if you are not familiar with this argument, the recommended value is $0$ . When the value $- 1 or 1$ is used it is essential to test the value of ifail on exit.

On exit: $ifail = 0$ unless the routine detects an error or a warning has been flagged (see Section 6).

6

Error Indicators and Warnings

If on entry

ifail = 0

- 1

, explanatory error messages are output on the current error message unit (as defined by x04aaf).

Errors or warnings detected by the routine:

$ifail = 6$: On entry, $nvar = 〈value〉$ .
Constraint: $nvar > 0$ .

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

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

$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

e04raf is not threaded in any implementation.

9

Further Comments

None.

10

Example

See examples associated with other routines in the suite:

–	the example in Section 10 in e04fff demonstrates how to use a DFO LSQ solver,
–	the example in Section 10 in e04mtf solves a small LP example using an LP IPM solver,
–	the example in Section 10 in e04rdf demonstrates how to use the SDPA file reader and how to solve linear semidefinite programming problems, including printing of the matrix Lagrangian multipliers,
–	the example in Section 10 in e04rff presents an alternative way to compute the nearest correlation matrix by means of nonlinear semidefinite programming,
–	a matrix completion problem (minimization of a rank of a partially unknown matrix) formulated as SDP is demonstrated in Section 10 in e04rhf, the example also demonstrates the monitoring mode of the solver e04svf,
–	the example in Section 10 in e04rjf solves LP/QP problems read in from an MPS file by e04mxf,
–	an application for statistics, $E$ optimal design, solved as an SDP problem is shown in Section 10 in e04rnf,
–	the example in Section 10 in e04rpf reads a BMI-SDP problem from a file which can be modified, in this case it solves a Static Output Feedback (SOF) problem,
–	the example in Section 10 in e04rxf demonstrates how an approximate solution can be extracted during a monitoring step of e04mtf,
–	the example in Section 10 in e04ryf walks through the life cycle of the handle in which a BMI-SDP problem is formulated and solved,
–	an example in Section 10 in e04stf is a small test from Hock and Schittkowski set to show how to call the NLP solver,
–	the simple example in Section 10 in e04svf demonstrates on the Lovász $ϑ$ function eigenvalue optimization problem formulated as SDP.