allow quit early optimization even when there is positive probability to keep a higher-scoring change

[dave-doty]

Currently, we have a brittle criteria for quitting early when evaluating constraints: the total score of violations evaluated so far exceeds the total score of the current best design. This rule only works when we use the default probability_of_keeping_change function that has probability 0 to keep a change that is worse.

probability_of_keeping_change takes as input delta, the difference between the new design's score and the current best design's score, i.e., if the best has score 10 and the current one is worse, with score 13, then delta = 3. probability_of_keeping_change then outputs the probability to keep the change.

The following could allow us to use other probability_of_keeping_change functions and still get the benefit of the optimization. We can "invert" probability_of_keeping_change by doing the following. Prior to the next iteration, we compute a score threshold that we would be willing to keep. For example, if probability_of_keeping_change(delta) = 1/2^delta, then Pr[keep score 10] = 1, Pr[keep score 11] = 1/2, Pr[keep score 12] = 1/4, Pr[keep score 13] = 1/8, etc.

I'm not sure exactly how to efficiently sample a score threshold from the appropriate distributed, given only black-box access to probability_of_keeping_change.

But if we could do this, then we'd put all the randomness at the start of the iteration, before evaluating any constraints. Then the check we do generalizes to comparing to this sampled threshold, rather than the score of the best design so far.

The typical case, where probability_of_keeping_change is very unlikely to keep any change that is "much worse" would be that the sampled threshold would be only very slightly above the best score so far, so would be almost equivalent to what we are currently doing, while allowing occasional changes to be kept even if they are worse.

[dave-doty]

If we had the inverse of the CDF for probability_of_keeping_change, then inverse transform sampling is the way to go. But not sure of an efficient way to compute the inverse of the CDF given only the PDF (which is essentially what probability_of_keeping_change is).