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 f(x) is the set of all vectors w for which f(x + w) = f(x) for all possible vectors x. 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 F(x) 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
within the ``box'' region
(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 group
functions.
The argument
is known as the i-th group.
The functions 
, are called nonlinear element functions.
They are functions of the problem variables
, where the
are either small subsets of x or such that 
has a
large invariant subspace
for some other reason. The constants 
are known as
weights.
Finally, the function 
is known as the linear
element for the i-th group.
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.
