Next: A Simple Example
Up: What Bounds Can Learn
Previous: What Bounds Can Learn
Figure:
The area in which
must lie is shown.
is implicitly given since the distribution is normalized.
a) The pyramid is the allowable space. The darker planes show how
this pyramid can be restricted by adding earlier computed bounds as
constraints in the linear programming problem. b) This results in a
smaller polyhedron. The black lines show the planes where the
function
is
constant for this particular problem.

In terms of standard linear programming, Equation can be
expressed as

(7) 
where the variables are defined as
where
iff the states of the
nodes both node sets have in common are equal. Thus the columns of
the matrix correspond to
, the rows of and to
all the constraints (of which we have
for each
). The ordering of the rows of
and is irrelevant as long as it is the same for both. The constraint
that
should be normalized can be incorporated in
and by requiring

(8) 
The maximum of
corresponds to
.
The negative of
can be found by using
as the objective function.
Next: A Simple Example
Up: What Bounds Can Learn
Previous: What Bounds Can Learn
Martijn Leisink
20030818