Binary search converts certified SDP thresholds to additive optimization

By [F1], the first threshold $R+e$ exceeds the optimum, so [F2] cannot return HIGHER on its good event. It supplies a stored feasible vector with objective $B\le R+2e$. Thus the invariant $lo\le \mathrm{O}\mathrm{P}\mathrm{T}\le hi$ and $B\le hi+2e$ holds initially. At a LOWER midpoint, $\mathrm{O}\mathrm{P}\mathrm{T}\le B_{new}\le \alpha +e$; replacing $hi$ by its minimum with $\alpha +e$ keeps the optimum bracketed. If that endpoint changes, $B_{new}\le hi$; if clamping leaves it unchanged, $B_{new}\le \alpha +e\le hi+e$. Thus storing the new vector still gives $B\le hi+2e$. At HIGHER, $\alpha <\mathrm{O}\mathrm{P}\mathrm{T}$, so the lower-endpoint update preserves the bracket and changes no stored certificate.

With $W=hi-lo$, either update gives $W_{new}\le W\mathrm{/}2+e$. Induction gives $W_j\le 2e+2R{2}^{-j}$. At $j=L$ this is at most ${\epsilon }_0\mathrm{/}4+{\epsilon }_0\mathrm{/}32<{\epsilon }_0\mathrm{/}2$. While the stopping test fails, $W>4e$, so $W_{new}\le W\mathrm{/}2+e<3W\mathrm{/}4<W$; clamping cannot prevent contraction. Hence every good execution reaches the stopping width within the fixed cap without refinement. At exit the stored vector remains feasible and $B-\mathrm{O}\mathrm{P}\mathrm{T}\le hi-lo+2e\le 3{\epsilon }_0\mathrm{/}4<{\epsilon }_0\le \epsilon$. Since ${\epsilon }_0>\epsilon \mathrm{/}2$, its call cap is $O(1+\log (R\mathrm{/}\epsilon ))$. This includes the case of only HIGHER midpoint responses, using the initial certificate.

Condition on each reached history before the first bad complete threshold call. Until then steps 1.1–2.1 show there are at most $L+1$ calls and no refinements. Summing their conditional probabilities gives first-bad-call probability at most $(L+1)\delta \mathrm{/}(L+1)=\delta$. Additional operations on an already bad path do not add a second probability for that same bad event. This is valid without independence. A declared unresolved numerical failure is not interpreted as a threshold exclusion; the final high-probability conclusion requires the supplied complete oracle's good-event contract.

Since $\mathrm{\parallel }C\mathrm{\parallel }\le 1$, $I-C⪰0$ and $e_1$ is dual feasible with objective $R$. For $\epsilon \ge 2R$, [F1] gives $R\le \mathrm{O}\mathrm{P}\mathrm{T}+\epsilon$. For $R=0$, the identity constraint and nonnegative eigenvalues force every feasible primal $X$ to be zero; weak duality and the feasible zero-objective vector $e_1$ give optimum zero directly. For dimension zero, primal nonemptiness implies $b_j\ge 0$, so the zero vector is feasible and optimal. These branches establish the remaining cases without using the positive-$R$ formulas.