Branch and Bound Methods• basic ideas and attributes• unconstrained nonconvex optimization• mixed convex-Boolean optimizationProf. S. Boyd, EE364b, Stanford UniversityMethods for nonconvex optimization problems• convex optimization methods are (roughly) always global, always fast• for general nonconvex problems, we have to give up one• local optimization methods are fast, but need not find global solution(and even when they do, ca nnot certify it)• global optimization methods find global solution (and cer tif y it), butare not always fast (indeed, are often slow)Prof. S. Boyd, EE364b, Stanford University 1Branch and bound algorithms• methods for global optimization for nonconvex problems• nonheuristic– maintain provable lower and upper bounds on global objective value– terminate with certificate proving ǫ-suboptimality• often slow; exponential worst case per formance• but (with luck) can (sometimes) work wellProf. S. Boyd, EE364b, Stanford University 2Basic idea• rely on two subroutines that (efficiently) c om pute a lower and an upperbound on the optimal value over a given region– upper bound can be found by choosing any point in the region, or bya local optimization method– lower bound can be found from convex re laxation, d ua lity, Lipschitzor other bounds, . . .• basic idea:– partition feasible set into convex sets, and find lower/upper boundsfor each– form global lower and upper bounds; quit if c lose enough– else, refine partition and repeatProf. S. Boyd, EE364b, Stanford University 3Unconstrained nonconvex minimizationgoal: find global minimum of function f : Rm→ R, over anm-dimensional rectangle Qinit, to within som e prescribed accu r a cy ǫ• for any rectangle Q ⊆ Qinit, we define Φmin(Q) = infx∈Qf(x)• global optimal value is f⋆= Φmin(Qinit)Prof. S. Boyd, EE364b, Stanford University 4Lower and upper bound functions• we’ll use lower and upper bound functions Φlband Φub, that sa tisfy, forany rectangle Q ⊆ Qinit,Φlb(Q) ≤ Φmin(Q) ≤ Φub(Q)• bounds must become tight a s rectangles shrink:∀ǫ > 0 ∃δ > 0 ∀Q ⊆ Qinit, size(Q) ≤ δ =⇒ Φub(Q) − Φlb(Q) ≤ ǫwhere size(Q) is diameter (length of longe st edge of Q)• to be practical, Φub(Q) and Φlb(Q) should be cheap to computeProf. S. Boyd, EE364b, Stanford University 5Branch and bound algorithm1. compute lower a nd upper bounds on f⋆• set L1= Φlb(Qinit) and U1= Φub(Qinit)• terminate if U1− L1≤ ǫ2. partition (split) Qinitinto two rectangles Qinit= Q1∪ Q23. compute Φlb(Qi) and Φub(Qi), i = 1, 24. upda te lower a nd upper bounds on f⋆• update lower bound: L2= min{Φlb(Q1), Φlb(Q2)}• update upper bound: U2= min{Φub(Q1), Φub(Q2)}• terminate if U2− L2≤ ǫ5. refine partition, by splitting Q1or Q2, and repeat ste ps 3 and 4Prof. S. Boyd, EE364b, Stanford University 6• can assume w.l.o. g. Uiis nonincre asing, Liis nondec r easing• at each step we have a partially developed binar y tree; childrencorrespond to the subrectangles form ed by splitting the parent rectangle• leaves give the current partition of Qinit• need rules for c hoosing, at each step– which rectangle to split– which edge (variable) to split– where to split (what value of variable)• some good rules: split re ctangle with smallest lower bound, alonglongest edge, in halfProf. S. Boyd, EE364b, Stanford University 7Examplepar titioned rectangle in R2, and associated binary tree, af ter 3 iterationsProf. S. Boyd, EE364b, Stanford University 8Pruning• can eliminate or prune any rectangle Q in tree with Φlb(Q) > Uk– every point in rec tan gle is worse than cur r ent upper bound– hence cannot be optimal• does not affect algorithm, but does reduce storage requirements• can track progress of algorithm via– total pruned (or unpruned) volume– number of pruned (or unprune d) leaves in partitionProf. S. Boyd, EE364b, Stanford University 9Convergence analysis• number of rectangle s in partition Lkis k (without pruning)• total volume of these rectangles is vol(Qinit), sominQ∈Lkvol(Q ) ≤vol(Qinit)k• so for k large, at lea st one rectangle has small volume• need to show that sm all volume implies small size• this will imply that one rectangle has U − L small• hence Uk− Lkis smallProf. S. Boyd, EE364b, Stanford University 10Bounding condition number• condition number of rectangle Q = [l1, u1] × · · · × [ln, un] iscond(Q) =maxi(ui− li)mini(ui− li)• if we split rectangle along longest ed ge, we havecond(Q) ≤ max{cond(Qinit), 2}for any rectangle in partition• other rules (e.g., cycling over variables) also guara ntee bound oncond(Q)Prof. S. Boyd, EE364b, Stanford University 11Small volume implies small sizevol(Q ) =Yi(ui− li) ≥ maxi(ui− li)mini(ui− li)m−1=(2 size(Q))mcond(Q)m−1≥2 size(Q)cond(Q)mand so size(Q) ≤ (1/2)vol(Q)1/mcond(Q)therefore if cond(Q) is bounded and vol(Q) is sma ll, size(Q) is smallProf. S. Boyd, EE364b, Stanford University 12Mixed Boolean-convex problemminimize f0(x, z)subject to fi(x, z) ≤ 0, i = 1, . . . , mzj∈ {0, 1}, j = 1, . . . , n• x ∈ Rpis called continuous variable• z ∈ {0, 1}nis calle d Boolean variable• f0, . . . , fnar e convex in x and z• optimal value denoted p⋆• for each fixed z ∈ {0, 1}n, reduce d problem (with var ia ble x) is convexProf. S. Boyd, EE364b, Stanford University 13Solution methods• brute force: solve convex problem for each of the 2npossible values ofz ∈ {0, 1}n– possible for n ≤ 15 or so, but not n ≥ 20• branch and bound– in worst case, we end up solving all 2nconvex problems– hope that branch a n d bound will actually work much betterProf. S. Boyd, EE364b, Stanford University 14Lower bound via convex relaxationconvex relaxationminimize f0(x, z)subject to fi(x, z) ≤ 0, i = 1, . . . , m0 ≤ zj≤ 1, j = 1, . . . , n• convex with (continuous) variables x and z, so easily solved• optimal value (denoted L1) is lower bound on p⋆, optimal value oforiginal problem• L1can be +∞ (w hich implies original problem infeasible)Prof. S. Boyd, EE364b, Stanford University 15Upper bounds• can find an uppe r bound (de note d U1) on p⋆several ways• simplest method: round each relaxed Boolean var iab le z⋆ito 0 or 1• more sophisticated method: round each Boolean variable, then solve theresulting convex problem in x• randomized method:– generate random zi∈ {0, 1}, with Prob(zi= 1) =