2 An introduction to nonlinear optimization

problem structure

As we have already mentioned, structure
is an integral and significant
aspect of large-scale problems. Structure is often equated with
sparsity; indeed the two are closely linked when the problem is
linear. However, sparsity
is not the most important phenomenon associated with a nonlinear
function; that role is played by invariant subspaces. The *invariant subspace*
of a function is the
set of all vectors for which
for all possible
vectors . This phenomenon encompasses function sparsity.
For instance, the function

has a gradient and Hessian matrix each with a single nonzero, has an invariant subspace of dimension 999, and is, by almost any criterion, sparse. However the function

has a completely dense Hessian matrix but still has an invariant subspace of dimension 999, the set of all vectors orthogonal to a vector of ones. The importance of invariant subspaces is that nonlinear information is not required for a function in this subspace. We are particularly interested in functions which have large (as a percentage of the overall number of variables) invariant subspaces. This allows for efficient storage and calculation of derivative information. The penalty is, of course, the need to provide information about the subspace to an optimization procedure.

A particular objective function
is unlikely to have a large
invariant subspace itself.
However, many reasonably behaved functions may be expressed as a sum
of *element* functions,
each of which does have a large invariant subspace.
This is certainly true if the function is sufficiently differentiable
and has a sparse Hessian
matrix [11]. Thus, rather than storing a
function as itself, it pays to store it as the sum of its elements.
The elemental representation of a particular function is by no means
unique and there may be specific reasons for selecting a particular
representation. Specifying Hessian sparsity
is also supported in the present proposal, but we believe that it is
more efficient and also much easier to specify the invariant subspaces
directly.

*LANCELOT* considers the problem of minimizing or maximizing
an objective function
of the form

(where either bound on each variable may be infinite), and where the variables are required to satisfy the extra conditions

and

for some index sets and and (possibly infinite) values . The univariate functions are known as

is known as the -th

It is more common to call the group functions in (2.3) equality constraint functions, those in (2.4) inequality constraint functions and the sum of those in (2.1) the objective function.

When stating a structured nonlinear optimization problem of the form (2.1)-(2.4), we need to specify the group functions, linear and nonlinear elements and the way that they all fit together.

- 2.1 Problem, Elemental and Internal Variables
- 2.2 Element and Group Types
- 2.3 An Example
- 2.4 A Second Example
- 2.5 A Final Example