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?

  • 1
    $\begingroup$ Please be more explicit with your question: in particular, giving the general context and the definitions of $L_2$ and $U_2$ only takes a few lines, and makes this question potentially useful to more people than just yourself. $\endgroup$ – cody Oct 7 '15 at 15:07
  • $\begingroup$ Please edit the question to make the question self-contained and provide all relevant context (the definitions of L2 and U2, etc.). People shouldn't have to click to look on a separate page to understand what you are asking; and if that link stops working, we want the question to still be understandable. Finally, what are your thoughts? $\endgroup$ – D.W. Oct 8 '15 at 17:42

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.