Database Reference
In-Depth Information
Updating A Local Model
1:
Require: I , x , f
(
x
)
f R
2:
if
R
,
I : x can be included in R
f R
3:
for all
R
,
I
4:
if x can be included in R
f R
5:
Update
R
,
to include x
6:
end if
7:
end for
8:
else
f R
9:
Add new
R
,
to I
10:
end if
Figure 11.13
Updating a local model.
approximates f well. It then gradually grows these conservative approxima-
tions over time. More specifically the update process first searches index I for
regions where x lies outside the region but
f R
. Such regions
are grown to contain x (Lines 2-7). If no existing regions can be grown, a new
conservative region centered around x and the associated f R is added to the
local model (Line 9). The Grow Process described is a heuristic that works
well in practice for functions that are locally smooth. This assumption holds
in combustion and in most other applications.
Instantiation: The original ISAT Algorithm proposed high-dimensional
ellipsoids as regions and used a linear model as the function in a region. The
linear model is initialized by computing the value of f and estimating the
derivative of f at the center of the ellipsoidal region:
||
(
x
)
f
(
x
) || ≤
f R
f (
(
x
) =
f
(
a
) +
x
a
),
where a is the center of region R and f (
is the derivative of f at a .
ISAT performs one of the following basic operations for each query point x .
Retrieve : Computing the function value at x using the current local model
by searching for a region containing x . Grow : Searching for regions that can
be grown to contain x and updating these regions in I . Add : Adding a new
region ( R ) and an associated
a
)
f R into I .
11.4.2.3
Indexing Problem
The indexing problem in function approximation produces a challenging work-
load for the operations on index I in Figures 11.12 and 11.13. The Retrieve
requires the index to support fast lookups. The Grow requires both a fast
lookup to find growable ellipsoids and then an ecient update process once
an ellipsoid is grown. Finally, an ecient insert operation is required for the
Add step. There are two main observations that make this indexing problem
different from traditional indexing. 31 , 32
Search WWH ::




Custom Search