2

Assume I have a program which we'll model as bool Worked = f(param1,param2,...) Assume these parameters are positive integers, and a starting set exists s/t Worked returns true. Is there a smarter way than parametric sweep to map/estimate the stable surface of the parameters, that is, the surface under which the function will return true? You can assume any intermediate values would work - that is, if 32 and 64 worked for a parameter ceteris paribus, any value between them would also work.

Carbon
  • 151
  • https://stats.stackexchange.com/questions/193306/optimization-when-cost-function-slow-to-evaluate/193310#193310 The methods in this thread are broadly applicable. – Sycorax Jun 21 '17 at 17:48
  • Any special considerations for a boolean return function? – Carbon Jun 21 '17 at 17:51
  • You have outcomes $y\in{\text{worked}, \text{did not work}}$, i.e. binary. So you're modeling $y\sim\text{Bernoulli}(\text{logit}^{-1}(z))$ where $z\in\mathbb{R}$ is inferred by the surrogate model. This just adds one tiny step to the procedure. – Sycorax Jun 21 '17 at 18:00
  • Ahhh ok, right, a logit model. – Carbon Jun 21 '17 at 18:01
  • Can you clarify your last sentence? Do you just mean the feasible set has a single connected component? (And "parameter sweep" = breadth first search?) – GeoMatt22 Jun 21 '17 at 18:41
  • @Sycorax mapping a feasible region seems different than optimization, no? (i.e. goal is a level set vs. a summit) – GeoMatt22 Jun 21 '17 at 18:46
  • @GeoMatt22 I guess my mind leapt to thinking about it as finding a volume with a high probability for Worked == True. You're right, though, my suggestion may not be the solution that OP is after, or even a helpful proxy for it. – Sycorax Jun 21 '17 at 19:05
  • I guess you could think of it as mapping the area f(x,y,z) that returns true. If you get true from f(32,32,32) and f(64,32,32), you can be assured f(48,32,32) will be true as well. – Carbon Jun 21 '17 at 19:47
  • Are you sure this isn't a satisfiability question? – Sycorax Jun 21 '17 at 19:54
  • You could look at it that way, I know that there exists a solution, I want to know what the bounds of satisfiability are. Did I put that right? – Carbon Jun 21 '17 at 19:57

2 Answers2

3

This is similar to a constraint satisfaction problem, except you want to map the entire feasible region vs. find a single point.

Given your connected constraint, then parameter sweep is not efficient. At the least, for coordinate-axis searching you could do binary search.

(On the left, which is bounded by 1 below. On the right you could say preface this by first finding an infeasible point by searching out exponentially, e.g. 2,4,8,...)

GeoMatt22
  • 12,950
1

There is a similar problem in the are of on-line motion planning, which is about finding an unknown point in an unknown (and unobservable) 2D terrain. This paper presents an optimal solution that can find this single point. Maybe there are similar algorithms which can also work with higher dimensional spaces.

In that case, you may be able to modify these algorithms to identify the furthest points and then build your surface from there.

LiKao
  • 2,661