If you want to make money online : Register now

Branch and bound stanford slides doubt

, , No Comments
Problem Detail: 

On the 6th slide at https://web.stanford.edu/class/ee364b/lectures/bb_slides.pdf, while defining L2 and U2, why are we taking min for both?

Asked By : Deepankar Arya
Answered By : cody

The slides are correct: remember that we are trying to find a bound on the optimal value of $f$, which is defined as $$\Phi_\mbox{min}({\cal Q}_\mbox{init}) =\min_{x\in{\cal Q}_{\tiny\mbox{init}}}f(x)$$

To find that minimum, we approximate it by upper and lower bounds $\Phi_\mbox{ub}$ and $\Phi_{\mbox{lb}}$. Let's concentrate on $\Phi_{\mbox{ub}}$. Note that if ${\cal Q}={\cal Q}_1\cup{\cal Q}_2$, then both $$ \min(\Phi_{\mbox{ub}}(\cal Q_1),\Phi_{\mbox{ub}}(\cal Q_2))\geq\Phi_\mbox{min}(\cal Q)$$ and $$ \max(\Phi_{\mbox{ub}}(\cal Q_1),\Phi_{\mbox{ub}}(\cal Q_2))\geq\Phi_\mbox{min}(\cal Q)$$

But we might as well take $\min$, since that is the value that is closer to the global minimum $\Phi_\min(\cal Q)$!

In fact, taking the minimum is going to be necessary if we want the branch and bound method to converge to the minimum as we sub-divide $\cal Q$ into smaller and smaller pieces.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/47979

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback