# Designing a stopping rule using a hypothesis test

I am working on a stopping rule for an optimization algorithm that produces an upper bound and lower bound for the objective value of an optimization problem. In my case, the lower bound is deterministic, but the upper bound is an estimate derived from $N$ data points $UB_1, UB_2... UB_N$ with mean $\widehat{UB}$ and standard deviation $\hat{\sigma}_{UB}$, where:

$$\widehat{UB} = \frac{1}{N} \sum_{i=1}^N UB_i$$

$$\hat{\sigma}_{UB}^2 = \frac{1}{N} \sum_{i=1}^{N} (UB_i - \widehat{UB})^2$$

Theoretically speaking, the algorithm needs to stop when the upper bound is equal to the lower bound. The stopping rule that I have in mind is to stop when $\frac{\widehat{UB}}{LB} = 1$. More formally, I would like to test:

$$H_0: \frac{\widehat{UB}}{LB} = 1$$

$$H_A: \frac{\widehat{UB}}{LB} > 1$$

And stop when I fail to reject $H_A$.

Broadly speaking, I would like to control for both type I and type II errors. That is, I would like to specify the probability that I am stopping too early (i.e. $H_0$ is accepted given $H_A$ is true) and also specify that I am stopping too late (i.e. $H_0$ is rejected given that $H_0$ is true).

I'm wondering what the exact formulation should look like in this case? Or what type of test to do. I'm open to any ideas you may have, including a different test altogether so long as we can specify the probabilities I described above in some way.

• interesting question. you should add "hats" to your estimates, so that it is clear which quantities you are talking about (hypothesis refers to true values - others places refer to estimates). Also, are these upper and lower bounds "plugged" back into the optimization routine to get a new estimates of upper and lower bounds? so that $[\hat{\mu}_{UB}^{(j)},\hat{\mu}_{LB}^{(j)}]=F[\hat{\mu}_{UB}^{(j-1)},\hat{\mu}_{LB}^{(j-1)}]$ where $F[.]$ is the optimization routine. – probabilityislogic Mar 22 '11 at 12:54
• @probabilityislogic Thanks! I added some more detail to the question to help clear things up. In this case, the upper and lowerbounds are discarded from the routine. – Berk U. Mar 22 '11 at 15:00
• What is the relationship between the "data points" and the optimization algorithm? It is natural to suppose the data are estimates of the upper bound obtained during iterations of the algorithm. In this case they might form a sequence expected to converge to the lower bound. A far better approach would be to compare the minimum of the $UB_i$ to $LB$ and stop when it either gets close enough for the problem or the gap $UB_i - LB$ stops getting smaller. – whuber Jun 28 '11 at 15:14
• @whuber Well spotted. I had originally omitted this information to simplify my formulation, but the algorithm is used to solve stochastic optimization problems and works in a similar way to what you proposed. In particular, $UB$ and $LB$ are actually random variables and we have to stop when $E[UB]$ = $E[LB]$. In this case, $\hat{UB}$ is an estimate of $E[UB]$. Each iteration provides the exact value for $E[LB]$ and $N$ values of UB that are used to form $\hat{UB}$/estimate $E[UB]$. The stopping rule is applied at the end of each iteration, in order to terminate as quickly as possible. – Berk U. Jun 28 '11 at 17:24
• Decision theory could provide some insights and guidance, if you could quantify (even roughly) the costs of stopping too soon or going on too long with the optimization. An optimal stopping rule would minimize the expected costs. – whuber Jun 28 '11 at 19:19

Anyway, if the probability to reject the null wrongly is $1-\alpha$ the probability to accept it wrongly won't be $\alpha$, if you want to control the error of accepting the null wrongly you have to specify one alternative or at least to assume it is separated from the null and use the "extreme" point of the alternative to compute the threshold at the level you want.