Global optimization and certified branch and bound — Examples

Here $K_{aa}=1$, $K_{ba}=0$, and $C=K_{aa}+1=2>0$. Conditioning on the observation $y(a)=0$ gives $\mu (a)=0$, $v(a)=1-1\mathrm{/}2=1\mathrm{/}2$, $\mu (b)=0$, and $v(b)=1$.

The two acquisition values are $a_1(a)=\sqrt{1\mathrm{/}2}<1=a_1(b)$. The exact least-index finite scan therefore selects $b$, with maximization error ${\delta }_1=0$.

The procedure calls the observation oracle at $b$; if it returns a finite real value, that value is appended. The new observed covariance is $C_2=2I_2$, so the algorithm computes the posterior at history length $N=2$ and returns complete. These posterior and acquisition values are conditional on the chosen kernel and noise model. They do not state a regret bound, a global guarantee for the biological simulator, or that the actual simulator is distributed as the surrogate GP.

The true infimum on $[0,1]$ is $f^{\ast }=0$, attained at $x=0$, whereas the reported value $1\mathrm{/}2$ is not a lower bound because $1\mathrm{/}2>0=f^{\ast }$.

After the single root call, the procedure computes the spurious gap $U-\mathrm{\ell }=0\le 1\mathrm{/}4$ and returns its midpoint witness without further search, although that witness has error $f(1\mathrm{/}2)-f^{\ast }=1\mathrm{/}2>1\mathrm{/}4$. The root containing the true minimizer has therefore been discarded from further search on an invalid certificate.

The claimed certificate contradicts the explicit objective difference, so the stated robustness to invalid lower bounds is false. This does not contradict A spatial branch-and-bound gap certificate proves global epsilon-optimality, whose hypothesis [F1] is violated.

The identity $f(x)=(x^2-\frac{1}{2}{)}^2-\frac{1}{4}$ shows $f(x)\ge -\frac{1}{4}$, with equality at $x=\pm \sqrt{1\mathrm{/}2}$. If $s=\sqrt{1\mathrm{/}2}$, then $s\ge 0$ and $s^2=1\mathrm{/}2$ by [F2], so $s>0$. We have $s<1$: otherwise either $s=1$, contradicting $s^2=1\mathrm{/}2$, or $1<s$, which by strict monotonicity of squaring on nonnegatives gives $1<s^2=1\mathrm{/}2$, also impossible. Hence both minimizers lie in $[-1,1]$, and they are distinct because $s>0$. Squaring is monotone on the nonnegatives

At the root box, the DAG product $t=x\times x$ encloses as $[-1,1]$ under ordinary interval multiplication; then $u=t\times t$ also encloses as $[-1,1]$, so $f=u-t$ encloses as $[-2,2]$. The root midpoint is $0$, with exact feasible value $f(0)=0$; its initial gap is $0-(-2)=2>9\mathrm{/}10$, so the root cannot yet be closed as a global certificate.

The root uses the first call. Bisect at zero and evaluate the lower child on the second call and the upper child on the third call, completing both reports within $N=3$. On each child $[-1,0]$ and $[0,1]$, ordinary interval multiplication gives $t=x\times x\in [0,1]$, then $u=t\times t\in [0,1]$, so $f=u-t$ has lower bound $-1$. The child midpoints are $-1\mathrm{/}2$ and $1\mathrm{/}2$, and both give $f=1\mathrm{/}16-1\mathrm{/}4=-3\mathrm{/}16$, so the incumbent becomes $U=-3\mathrm{/}16$ and the global lower bound is $L=-1$.

The gap is $U-L=13\mathrm{/}16<9\mathrm{/}10$. The feasible midpoint and the complete two-leaf ledger therefore certify epsilon-global optimality. Its actual objective is $1\mathrm{/}16$ above the minimum, within the declared tolerance.

For each fixed $z\in \{0,1,2\}$, the square $(x-z\mathrm{/}2{)}^2$ is nonnegative, so $F(z,x)\ge (z-2{)}^2\mathrm{/}10$. The point $x=z\mathrm{/}2$ belongs to $[0,1]$ and attains equality. Thus the exact fixed-integer minima are $2\mathrm{/}5$, $1\mathrm{/}10$, and $0$, respectively.

After the root mixed-relaxation call, the three remaining calls are allocated one to each assignment in lexicographic order. For $z=0,1,2$, the exact continuous root report gives the lower bound $2\mathrm{/}5,1\mathrm{/}10,0$, respectively, and the feasible point $x=z\mathrm{/}2$ attains it. Thus the complete fallback ledger has $L=0$, and $(z,x)=(2,1)$ gives $U=0$. The total gap is exactly zero, which is at most $\epsilon$.

Therefore $(2,1)$ is globally optimal and is a zero-gap mixed-integer certificate. The proof uses finite enumeration and exact values; it makes no complexity claim for larger integer ranges.