The Directed Acyclic Graph
The directed acyclic graph, or DAG, is a recursive data structure fit to
hold nonlinear expressions
in such a way that evaluation and computation of partial derivatives by
means of automatic differentiation is efficient.
Essentially, the DAG for an expression is the
Kantorovich graph [Kantorovitch 1957]
for that expression, in which the repeated occurence of a
sub-expression is fully exploited. In this context, it is also referred to
as a computational graph [Bauer 1974].
Variables and constants are leaves of
the DAG. All other nodes are operators, such as the addition, division,
multiplication or exponentiation. The terminology walking the DAG
refers to starting from the top
node&emdash;the {\em root} of this tree&emdash;and visiting each node in turn, in a
prescribed order. Walking the DAG from top to bottom,
and at each node, from left to right recursively, amounts to performing a
depth-first search in the tree.
By storing common expression only once, the DAG is
advantageously used by AMPL,
to store and evaluate but also differentiate nonlinear expressions
automatically. Automatic differentiation offers the possibility
of computing gradients and Hessian-vector products at a small multiple
of the cost of evaluating the function value.
Storage of the DAG in AMPL
The DAG in AMPL is stored in a conglomerate of recursive data structures,
representing each node of the tree&emdash;the operators and leaves&emdash;as well as
the edges. We examine in turn the data structures used to represent leaves
and other nodes. This is done in C-type code that follows
closely the implementation found in the Ampl Library so the reader can
work with the present description and the code in parallel.
Leaves of the DAG
Constants are held in a data structure named expr_n. This structure
is defined in the main header asl.h as
struct expr_n {
efunc_n *op;
real v;
};
where we have the following type declarations
typedef double real;
typedef real efunc_n (expr_n*);
In other words, every object of type efunc_n is a function taking an
expr_n* as argument and returning a double precision floating-point
number. The op field of an expr_n is a pointer to such a
function. The value of the constant is held in the v field.
Variables are held in a data structure named expr_v, defined in
nlp.h as
struct expr_v {
efunc *op;
int a;
real v;
};
We delay for a moment the exact definition of efunc. An instance of an
expr_v represents the a-th variable x[a],
whose current value is held in the v field. Variable indices are zero-based.
General nodes of the DAG
We have the type declaration
typedef real efunc (expr*);
where an expr represents a more general expression than just the
constant or the variable. It can hold any type of operator predefined in
AMPL. In the header nlp.h, we have the declaration
struct expr {
efunc *op;
int a;
real dL;
ei L, R;
real dR;
};
where the op field is a pointer to a function implementing the
operator represented by the node. If this operator takes arguments, they are
represented by the L and R fields. The type ei
is a union, and basically represents an expr* in a field named e.
union ei {
expr *e;
...
expr_n *en;
...
}
Hence each general node in the DAG is represented by an expr
structure.
In AMPL, each operator, such as addition and product, and each
built-in function, such as sine, cosine or logarithm, is implemented as an
efunc which receives numerical arguments in the form of an
expr* and returns a double precision result.
The root of the DAG
The only functions appearing in an optimization problem are the
objective(s) and the constraints. The
structure ASL_fg, holding the whole problem data, has the fields
cde *obj_de_;
cde *con_de_;
Each function, i.e., each objective and each constraint, has its own DAG. The
root of the DAG for the first objective is pointed to by obj_de_, i.e.,
the first element of the array obj_de_.
That for the second objective, if any, is pointed to by obj_de_ + 1, and so
forth. The pointer con_de_ plays a similar role for constraints. The
structure cde is basically a pointer to an expr.
In nlp.h, it is declared as
struct cde {
expr *e;
derp *d;
...
};
To treat the DAG of each objective in turn, one could thus use a loop such as
for( i = 0; i < nlo; i++ ) {
current_obj = (obj_de_ + i)->e;
ProcessObjective( current_obj );
}
using appropriate declarations. In the above loop,
nlo is the total number
of objective functions declared in the Ampl model which possess a nonlinear part,
as exported by the AMPL Library.
Finally, ProcessObjective() is a hypothetical function
that processes a given DAG. A similar loop can be written to process each
constraint in turn.
Ampl makes provision for common expressions and stores them in a separate
structure so as not to duplicate information and to save storage. Such expressions,
sometimes referred to as defined variables,
naturally occur in models
when a given expression appears at several places in the objective and/or
constraints. A DAG containing such a defined variable will represent it as
a leaf, as if it were a regular variable of the problem, only with an index
which indicates that it should receive special treatment. Considering the
simple example
model;
var x, y; # Problem variables
var z = x^2 + y^2; # A defined variable
minimize distance: z;
it is easy to see that even though the objective function appears to be a
linear function of z, it really is quadratic in the problem
variables. The DAG of the objective will be the single node representing
the variable z, but will indicate that there is a pointer to another
DAG, stored as a common expression, describing the nonlinear expression
x2 + y2. In graph terminology, the separate and unique
storage of common expressions implies that the DAG is reduced.
|