The sample CPO update has a well-defined proposal and finite backtracking search

First consider $d\ge 1$ and symmetric positive definite $H$. By homogeneity, [F2] gives $x^{T}Hx\ge c\mathrm{\parallel }x{\mathrm{\parallel }}_2^2$ for all $x$, with zero handled directly. Put $C={\sum }_{a,b}\mathrm{\mid }{H}_{ab}\mathrm{\mid }$. Coordinate bounds in [F6] and the identity $x_a{x}_b-y_a{y}_b=(x_a-y_a)x_b+y_a(x_b-y_b)$ give $\mathrm{\mid }{x}^{T}Hx-y^{T}Hy\mathrm{\mid }\le C\mathrm{\parallel }x-y{\mathrm{\parallel }}_2(\mathrm{\parallel }x{\mathrm{\parallel }}_2+\mathrm{\parallel }y{\mathrm{\parallel }}_2)$, so the quadratic form is continuous. The ellipsoid $E=\{x:x^{T}Hx\mathrm{/}2\le \delta \}$ is therefore closed and contained in the ball of radius $\sqrt{2\delta \mathrm{/}c}$, hence compact by [F3]. Each linear functional $x\mapsto v^{T}x$ is continuous because $\mathrm{\mid }{v}^T(x-y)\mathrm{\mid }\le \mathrm{\parallel }v{\mathrm{\parallel }}_2\mathrm{\parallel }x-y{\mathrm{\parallel }}_2$. Thus the feasible set $F=E\cap {\bigcap }_i\{x:q_i+u_i^{T}x\le 0\}$ is a closed subset of $E$, and is compact.

If $F$ is nonempty, [F4] gives an attained maximum $M$ of $g^{T}x$ on $F$. Its maximizer set $K_0=\{x\in F:g^{T}x=M\}$ is nonempty and compact by closedness and [F3]. Successively for coordinates $h=1,\dots ,d$, let $a_h$ be the minimum of coordinate $h$ on $K_{h-1}$ and set $K_h=\{x\in K_{h-1}:x_h=a_h\}$. Each minimum exists by [F4], and each restriction remains nonempty and compact by [F3]. After $d$ restrictions all coordinates are fixed, so $K_d$ is a singleton. For any other maximizer, the first coordinate where it differs from this singleton must be greater, by the construction of that coordinate's minimum. The singleton is therefore exactly the unique lexicographically least maximizer. As a member of $F$, it satisfies all stated constraints.

If $Hz=0$, then $z^{T}Hz=0$ and positive definiteness forces $z=0$. Thus [F5] supplies $H^{-1}$. In the single-cost recovery branch write $u=u_1\mathrm{\ne }0$, $v=H^{-1}u$. Then $v\mathrm{\ne }0$, $Hv=u$ and $a=u^{T}v=v^{T}Hv>0$. For every $x\in E$, nonnegativity of the quadratic form at $x-(u^{T}x\mathrm{/}a)v$ gives $0\le x^{T}Hx-(u^{T}x{)}^2\mathrm{/}a$, using symmetry. Consequently $u^{T}x\ge -\sqrt{2\delta a}$. For $x^{\ast }=-\sqrt{2\delta \mathrm{/}a}v$, direct substitution gives $(x^{\ast }{)}^{T}H{x}^{\ast }=2\delta$ and $u^T{x}^{\ast }=-\sqrt{2\delta a}$, attaining the bound. If another point attains it, equality in the preceding inequalities gives $(x-(u^{T}x\mathrm{/}a)v{)}^{T}H(x-(u^{T}x\mathrm{/}a)v)=0$, hence $x=(u^{T}x\mathrm{/}a)v=x^{\ast }$ by positive definiteness. The recovery proposal is therefore unique, and its linearized cost is $q_1-\sqrt{2\delta a}$. Since it is the minimum over $E$, infeasibility implies that this last value is strictly positive, rather than implying feasibility.

The remaining proposal branches are the explicit returns in [F1]: non-positive-definite $H$, infeasible single-cost problem with $u_1=0$, and infeasible problem with $m>1$ all return no-step. If $d=0$, the only parameter displacement is the zero vector, so a feasible program has that unique maximizer, and in the infeasible case all $u_i=0$ and one of the specified no-step branches applies. Thus zero dimension introduces no missing proposal case. Together with steps 2.1 and 2.2, every branch either gives one uniquely specified proposal or returns no-step.

For a proposal $x^{\ast }$, the candidates ${\theta }_k+{\beta }^j{x}^{\ast }$ for integer $j=0,\dots ,L$ form a prescribed ordered list of $L+1$ points. The parameter-domain check precedes evaluation of the policy tests, so no value outside the domain is required. On the domain, the finite common-support policy probabilities define the empirical KL and surrogates in [F1]. Either there is a least passing index in this finite list, or there is none; [F1] returns its candidate or no-step, respectively. Inspecting successive indices therefore terminates in at most $L+1$ candidate tests. The definition of passing supplies exactly the stated sample inequalities. All choices and returns are single-valued by steps 2.1, 2.2 and 3.1 and this least-index rule, establishing the asserted output and finite-search properties. No step in this argument compares the sample estimates to population expectations.