Paperlane

no. 3 · Tuesday 27 October 2026

Ellipsoid Separation in Data-Dependent Time via Infimal Displacement Vectors

Matthew Hough and Stephen A. Vavasis

math.OC

Abstract

The infimal displacement vector of the nonexpansive operator underlying the primal-dual hybrid gradient algorithm (PDHG) is known to encode useful information for infeasible optimization problems. In particular, for the ellipsoid separation problem (ESP), where the goal is to find a separating hyperplane between two collections of ellipsoids, the infimal displacement vector corresponding to an infeasible second-order cone program (SOCP) encodes a separating hyperplane. We show FISTA computes a sequence of approximations to the dual component of the infimal displacement vector and establish that a solution to the ESP can be obtained in $\mathcal{O}(δ_{\mathcal{A}}^{-2})$ iterations. Here $δ_{\mathcal{A}}$ denotes the distance between the convex hulls of the two ellipsoid collections.

fields
Optimization and Control
pdf ↗ page arXiv:2610.33902 ↗