Ellipsoid Separation in Data-Dependent Time via Infimal Displacement Vectors

arXiv:2610.33902 · math.OC · Submitted 2026-10-24 · Read on arXiv

math.OC

Submitted: 2026-10-24

Updated: 2026-10-24

License: http://creativecommons.org/licenses/by/4.0/

The gist: 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.

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 O(δ A-2) iterations. Here δ A denotes the distance between the convex hulls of the two ellipsoid collections.

Related papers