Local search versus branch and bound

A one-hidden-layer ReLU network with 17 units, so the surrogate is piecewise linear with one kink per unit. Where is its minimum?

or click the plot to start there

Local search follows the slope downhill from each start and stops in the first valley it reaches.

Branch and bound splits the input at a kink, bounds each piece from below, and discards pieces that cannot beat the best point found.

Branch-and-bound node log

node	interval	lower bound	best found	action