Query-only optimization from weak separation by centroid cuts

Let $P$ be a full-dimensional compact convex body and $X$ uniform on $P$. For any unit $a$, the survival function $S(t)=\mathrm{Pr}(⟨a,X⟩\ge t)$ is log-concave on the open projection interval: the Minkowski interpolation of the two caps at $t_0,t_1$ lies in the cap at their interpolated threshold, so [F1] gives concavity of $S^{1\mathrm{/}n}$, and the increasing concave logarithm gives concavity of $\log S$. Slices and [F3] show that the projected distribution has continuous strictly increasing cumulative distribution on that interval and no atoms. Consequently $S(⟨a,X⟩)$ is uniform on $(0,1)$, by inverting this strictly monotone continuous function. Thus $\mathbb{E}[-\log S(⟨a,X⟩)]={\int }_0^1-\log tdt=1$. Jensen [F2] yields $S(⟨a,\mathbb{E}X⟩)\ge e^{-1}$. Applying this to $-a$ shows that either halfspace through the centroid contains at least $1\mathrm{/}e$ of the volume.

If $P$ contains a radius-$s$ ball, its width in every direction is at least $2s$. The projected density is at most $n\mathrm{/}(2s)$. Indeed, for $n\ge 2$ the $(n-1)$-slice area to the power $1\mathrm{/}(n-1)$ is concave by [F1]. A slice of area $A$ at position $t$ therefore gives cone lower bounds $A((v-a)\mathrm{/}(t-a){)}^{n-1}$ to its left and $A((b-v)\mathrm{/}(b-t){)}^{n-1}$ to its right, where $[a,b]$ is the projection interval. Integrating gives $\mathrm{vol}(P)\ge A(b-a)\mathrm{/}n$. Taking limits at endpoints proves the density bound for every interior slice. For $n=1$ the density is $1\mathrm{/}(b-a)$ directly. A slab of thickness $h$ thus has relative volume at most $nh\mathrm{/}(2s)$.

Choose a rational vector $v$ with $\mathrm{\parallel }v-c\mathrm{\parallel }\le \zeta \mathrm{/}(64R)$, so $\mathrm{\parallel }v\mathrm{\parallel }\le 2$. For a rational threshold $\gamma$, initialize a localization polytope $P=[-R,R{]}^n$ and make at most $T$ iterations. If it is empty or lower-dimensional, return FAIL. Otherwise compute its exact centroid $p_0$ and round to a fixed-point rational $p$ with $\mathrm{\parallel }p-p_0\mathrm{\parallel }\le \eta$. If $⟨v,p⟩<\gamma$, keep $P\cap \{x:⟨v,x⟩\ge ⟨v,p⟩\}$ without an oracle call. Otherwise query weak separation at $p$: IN returns $p$ as a witness; on an OUT answer in rational direction $u$, keep $P\cap \{x:⟨u,x⟩\le ⟨u,p⟩+\eta N\}$. After $T$ iterations without a witness, return FAIL. All constraints are rational. Every retained polytope contains $F_{\gamma }=B(K,-\eta )\cap \{x:⟨v,x⟩\ge \gamma \}$ whenever the oracle answers succeed. The oracle cut has geometric displacement at most $3\eta$ from the true centroid, including point rounding; the objective cut has displacement at most $\eta$. Common fixed-point query registers can therefore be chosen from the bounded initial box and this explicit rounding precision, despite growth of the internal exact centroid denominators.

This is a finite arithmetic procedure. Vertices of a bounded rational polytope are found by enumerating all subsets of $n$ defining hyperplanes, solving each nonsingular linear system, and retaining feasible solutions. A nonempty full-dimensional bounded polytope has vertices, since successively minimizing coordinates on a minimizing face eventually gives a zero-dimensional face. Supporting facets can be enumerated from its finite vertex list and checked by rational sign tests. Triangulate a facet inductively by choosing one vertex and coning its nonincident boundary facets; then cone the resulting boundary simplices to a rational interior point such as the average of all vertices. This partitions $P$ up to common faces. A simplex has volume $\mathrm{\mid }\det (v_1-v_0,\dots ,v_n-v_0)\mathrm{\mid }\mathrm{/}n!$ and centroid $(v_0+\cdots +v_n)\mathrm{/}(n+1)$: the first identity is [F3], and the second follows by permutation symmetry of barycentric coordinates and their sum being one. The volume-weighted average of these simplex centroids is the exact rational centroid of $P$. Dimensions, incidences, and zero determinants are decided by finite rational elimination. No efficiency of this enumeration is asserted.

Put $h={\max }_{x\in K}⟨v,x⟩$ and take a maximizer $x_{\ast }$. If $\gamma \le h-\tau$, let $\alpha =\tau \mathrm{/}(8R)$ and $z=(1-\alpha )x_{\ast }$. Convexity gives $B(z,\alpha r)\subset K$. Since $s=\alpha r\mathrm{/}2$ and $\eta \le s$, the ball $B(z,s)$ lies in $B(K,-\eta )$. Also $⟨v,z⟩\ge h-\alpha \mathrm{\mid }h\mathrm{\mid }\ge h-\tau \mathrm{/}4$, and its value on that ball drops by at most $2s\le \tau \mathrm{/}8$. Therefore $F_{\gamma }$ contains this radius-$s$ ball.

Under this condition, every localization polytope contains the ball from step 2.2. The rounded-centroid objective and oracle cuts remove at least $1\mathrm{/}e-n(3\eta )\mathrm{/}(2s)=1\mathrm{/}e-3\mathrm{/}200>1\mathrm{/}4$ of the volume by step 1.1 and step 1.2. Thus each nonterminating iteration leaves at most $3\mathrm{/}4$ of the volume. But the radius-$s$ ball contains a cube of side $2s\mathrm{/}n$, whereas after $T$ cuts the volume is less than $(2s\mathrm{/}n{)}^n$ by the defining rational test for $T$. This is impossible. Hence FAIL implies $\gamma >h-\tau$ on successful oracle answers; IN returns a witness in $B(K,\eta )$ with $⟨v,p⟩\ge \gamma$.

Maintain an upper bound $H=2R\ge h$, a lower threshold $L=0$, and its witness $y=0$. Repeatedly test $\gamma =(L+H)\mathrm{/}2$. A witness sets $L=\gamma$ and saves it. FAIL sets $H=\min \{H,\gamma +\tau \}$, preserving $H\ge h$ by step 3.1. Stop when $H-L\le 4\tau$, and in any event after $B$ iterations. The width obeys $w_{j+1}\le w_j\mathrm{/}2+\tau$; hence $w_B\le 2R\mathrm{/}{2}^B+2\tau <4\tau$. A saved witness satisfies $⟨v,y⟩\ge L\ge h-4\tau$ and $y\in B(K,\eta )$. If a successful witness threshold exceeds $h$, the same conclusion holds and early stopping is valid; no assumption $L\le h$ was used. There are at most $BT$ separation calls, and $T=O(n\log (nR\mathrm{/}s))$, $B=O(1+\log (R\mathrm{/}\zeta ))$ follow from their geometric tests.

The failure probability of any successful-answer guarantee among these adaptive calls is at most $BT\cdot \nu \mathrm{/}(2BT)=\nu \mathrm{/}2$, conditioning on previous outputs and using a union bound. On the complement, $\mathrm{\parallel }y\mathrm{\parallel }\le R+\eta \le 2R$, so changing from $v$ to $c$ costs at most $3R\mathrm{\parallel }v-c\mathrm{\parallel }\le 3\zeta \mathrm{/}64$ in the difference between the optimum and output objective. The remaining gap is at most $4\tau =\zeta \mathrm{/}2$. Thus $y\in B(K,\zeta )$ and $⟨c,y⟩\ge {\max }_K⟨c,x⟩-\zeta$ with probability at least $1-\nu$. All omitted operations are the explicitly charged arithmetic of step 2.1 and the oracle encoding; they are not hidden query calls.