I have a simulation that takes in quite a few parameters (say around
10). The data output can be simplified to just one point on a
two-dimensional chart. All I am interested in is the border of that
plot (i.e. the outlying points), not the points in the middle. The
relationship between the input parameters and the output points is not
straightforward, though not random. What is the best way to "move"
around the border of the plot when running the simulation (This will
save much simulation time, as I'd avoid running most simulations that
generate points around the center of the plot)?

Methods, pros and cons of each and (links to) easily implementable
solutions required.

There is no general answer to such a problem.  Even if the mapping
from R^10 (if we assume 10 real parameters) to R^2 is continuous, it
can be "chaotic", which means that in practice one cannot predict what
input parameters provide an output near the boundary, rather than the
interior, of the target region.

If the mapping were well understood, then perhaps analysis of it would
lead to the sort of economy of evaluations that you seek.  However
from the use of "simulation" and the lack of any specific description
of the computation, I am lead to suspect that the mapping would be
very difficult (perhaps impossible) to analyze in these terms.

Note that even if you identified _some_ inputs that produce boundary
points, there is no clear justification for assuming that these are
representative of all the boundary points which might be produced.

regards, mathtalk-ga

Hi, gooseman-ga:

If I were in your situation, I'd try some numerical experiments with
techniques borrowed from root-finding and optimization.  My first
trials would probably be with a Nelder-Mead type of approach: evaluate
the function at 11 affine independent points in your parameter space,
creating the vertices of the ten-dimensional equivalent of a
tetrahedron in 3-D.  Pick the vertex whose output is farthest from the
boundary (in 2-D output space) and "reflect" that vertex through the
opposing "face" (of the 10-plex) to get the next trial input.

Of  course you may find that these 10-plexes are constantly bumping
into boundaries in your input parameter space, and perhaps for that
reason or others having to do with the mapping from 10 dimensions into
2 that the sequence of points bogs down into cycles or otherwise
degenerates without mapping out much of the output boundary.  On the
other hand it might provide a more efficient sampling of the desired
boundary regions than what you are doing now, even if you are forced
to "restart" the process many times before obtaining an adequate
sampling.

Once I had a pretty good sampling of the outlying points, I might try
to fill in the regions (in 2-D) between them by what are called
continuation or homotopy methods.  In other words, if input A and
input B give relatively close outputs near the (presumed) boundary,
then one can try to "morph" the inputs from A to B to obtain a
connecting sequence between their outputs.

It really begs the question of how one knows when an output is close
to the "boundary" of course.  If you knew what the boundary was, you'd
presumably not need to map it!  So initially you'd have to use a proxy
criterion which instead of minimizing distance to "the boundary" would
maximize the distance away from some interior point.  With some
auspicious choices of initial point you may be able to "drive" the
iterations out to the boundary in a random set of directions rather
expeditiously.

regards, mathtalk-ga

Thanks for the info!

Do you think Nelder-Mead will work well for a 2d boundary which is
almost circular (or blob shaped) on the X Y plain?

It will certainly make things a bit easier if the output region is
"star shaped", ie. every point in the region is connected by a line
segment to some fixed "central" point (with the line segment entirely
in the output region).  Then you can set as the "goal" for any
particular iteration to move away from that point (the central point
itself might have to be estimated, e.g. by an initial run of
"scattered" inputs).

But I fear the critical element here is going to be the nature of your
input to output mapping.  Obviously in going from 10 dimensions down
to 2 there's going to be a lot of "collapsing" and many-to-one
mappings.  Picking which vertex in input space falls "farthest" from
the output boundary is likely to become a source of difficulty.  The
10-plex might map down (assuming a small diameter and a differentiable
mapping) to something resembling a nonagon (11-sided polygon), but in
most cases some vertexes will probably map "inside" the convex hull of
only four or five "exterior" points.

It's a good starting point for experiments, I think.  You may find
that the iterations begin to "cycle" without much progress toward the
boundary, and then it's a judgement call whether the approach merits
tinkering with the initial choice of inputs or with some perturbations
in the iterated vertices to try and squeeze out additional progress.

regards, mathtalk-ga