The exhaustive box quadratic solve returns the unique minimizer in finite time

The box is compact and $\varphi$ is continuous, so [F2] supplies a minimizer $x_{\ast }$. If ${\mathrm{\ell }}_i<u_i$ and $x_{\ast ,i}={\mathrm{\ell }}_i$, the feasible right derivative is $g_i\ge 0$; if $x_{\ast ,i}=u_i$, the feasible left derivative gives $g_i\le 0$; and if ${\mathrm{\ell }}_i<x_{\ast ,i}<u_i$, both signs of perturbation are feasible, so $g_i=0$. For a fixed coordinate with ${\mathrm{\ell }}_i=u_i$, assign lower status if $g_i\ge 0$ and upper status if $g_i\le 0$ (either if $g_i=0$).

Assign each nonfixed coordinate of $x_{\ast }$ its lower, upper, or free status according as it is at the lower bound, at the upper bound, or strictly between them; assign fixed coordinates as in step 1.1. Every nonempty principal block $H_{FF}$ is positive definite: for $0\mathrm{\ne }y\in {\mathbb{R}}^F$, extend $y$ by zeros to $x\in {\mathbb{R}}^n$ to get $y^T{H}_{FF}y=x^{T}Hx>0$. Hence $H_{FF}$ is nonsingular; if $F=\mathrm{\varnothing }$, its system is vacuous. The free subsystem has the unique solution $x_{\ast ,F}$ by its zero free gradient. Thus the algorithm recovers $x_{\ast }$, whose free coordinates are strictly interior by their assignment and whose gradient signs hold by step 1.1. It is retained by [F1], so the algorithm terminates within $3^n$ checks.

Let $x$ be a retained candidate and $g=Hx+c$. For any feasible $y$, the checked coordinate signs give $g_i(y_i-x_i)\ge 0$ on lower-active coordinates, the same inequality on upper-active coordinates, and zero on free coordinates; hence $g^T(y-x)\ge 0$. The exact expansion $\varphi (y)-\varphi (x)=g^T(y-x)+\frac{1}{2}(y-x{)}^{T}H(y-x)$ is nonnegative, and is strictly positive when $y\mathrm{\ne }x$ because $H$ is positive definite. Thus every retained candidate is the unique minimizer, so the first one returned by the algorithm is.