Resolvent Ellipsoid for Minty Set Inclusions

We study Minty set inclusion on a compact convex set $\mathcal{X}\subseteq {\mathbb{R}}^d$ with a set-valued operator $A:\mathcal{X}\rightrightarrows {\mathbb{R}}^d$. Under the Minty promise, the goal is to compute $x\in \mathcal{X}$ and $u\in A(x)$ such that $\sup \_y\in \mathcal{X}⟨u,x-y⟩\le \epsilon$. Our approach is geometric. We work in the fixed-scale constrained-resolvent oracle model, where a query at anchor $a$ is assumed to return a resolvent point $x^{+}$ together with the Yosida vector $g_{\eta }(a)=(a-x^{+})/\eta$. We prove that each oracle response yields a sharp dichotomy: either the returned point provides an $\epsilon$-SVI certificate, or the Yosida vector defines a strict separating normal for the Minty set. Thus, a single black-box resolvent query supplies either a certified candidate solution or a valid geometric cut. Combining this separation principle with the ellipsoid method, we obtain Resolvent-Ellipsoid, an algorithm that computes an $\epsilon$-SVI in $\mathcal{O}\left(\mathrm{poly}(d,\log (1/\epsilon ))\right)$ black-box oracle calls to the fixed-scale constrained resolvent. For monotone inclusions, our algorithm gives, to our knowledge, the first $\mathcal{O}\left(\mathrm{poly}(d,\log (1/\epsilon ))\right)$ black-box guarantee in the fixed-scale resolvent model.